I grafi non vanno in vacanza

[Tess]

Sono dati $n$ punti a coordinate intere nel piano e 2 colori (facciamo rosso e blu). Vogliamo colorare i punti dati con questi colori in modo che in ogni retta verticale od orizzontale la differenza tra i punti colorati di un colore e l'altro sia più piccola di 2 in valore assoluto.
È possibile farlo per qualunque disposizione dei punti dati?

[Loara]

Ad ogni configurazione di $n$ punti assogiamo un grafo $G$ definito come segue:

• Ciascuno dei suoi vertici appartiene ad uno dei due insiemi disgiunti $A$ e $B$;
• Ogni vertice appartenente ad $A$ corrisponde ad una linea orizzontale;
• Ogni vertice appartenente a $B$ corrisponde ad una linea verticale;
• Se una linea verticale e una orizzontale si incontrano in un punto colorato, allora i due vertici corrispondenti sono collegati da un lato, colorato di rosso o blu anch'esso.

Vogliamo ottenere una colorazione dei lati tale che:

• Nei vertici di grado pari il numero di lati rossi sia uguale a quello dei lati blu
• Nei vertici di grado dispari il numero di lati rossi e quello dei lati blu differisce di $1$

Poiché ogni vertice di $A$ è collegato solo ad un vertice appartenente a $B$, allora tutti gli eventuali cicli sono di lunghezza pari. Ciò ci permette di effettuare una nuova colorazione, stavolta colorando i vertici di due colori, ad esempio bianco e nero, in modo tale che ad ogni vertice bianco sono collegati solo vertici neri, ed ad ogni vertice nero sono collegati solo vertici bianchi.
Analizziamo due casi ora:

• Esiste in $G$ un percorso (non necessariamente chiuso) che passa una sola volta per tutti i lati. Allora possiamo colorare i lati, durante la nostra "passeggiata", nel modo seguente:
  • se si passa da un vertice bianco ad uno nero, si colora il lato di rosso
  • se si passa da un vertice nero ad uno bianco, si colora il lato di blu
  Tale colorazione soddisfa le condizioni del problema, in quanto in un vertice di grado pari siamo entrati tante volte quante ne siamo usciti, e quindi il numero lati rossi è uguale a quello dei lati blu, mentre nei vertici di grado dispari il loro numero differisce di $1$.
• Non esiste in $G$ alcun percorso che passa una sola volta per tutti i lati. Quindi il numero di vertici di grado dispari è pari e $>2$. Ri-coloriamo i vertici come nel punto precedente, e stavolta costruiamo un percorso che inizi e termini in vertici di grado dispari e che passi per più lati possibili. Quindi effettuiamo la colorazione dei lati come nel punto precedente. Ora eliminiamo dal grafo tutti i lati colorati, ottenendo un nuovo grafo (non necessariamente connesso). I gradi dei vertici durante la trasformazione precenteranno le seguenti caratteristiche:
  • I vertici di grado pari avranno un grado pari
  • $2$ vertici di grado dispari avranno un grado pari
  • Tutti gli altri vertici di grado dispari avranno il grado dispari.
  Quindi il numero di vertici dispari diminuisce ogni volta di $2$. Dopo aver fatto tale operazione, si costruiscono altri percorsi, sempre partendo da un vertice di grado dispari, e si rieffettuerà la colorazione dei lati. Si continua così finché tutti i lati sono colorati. Alla fine la colorazione risultante rispetterà le condizioni del problema.

Si può dunque dedurre che, comunque si dispongano gli $n$ punti, è sempre bossibile effettuare una colorazione che soddisfi le condizioni del problema.

[Tess]

Bene ci siamo!
Faccio qualche piccolo commento alla tua dimosteazione.

• La tua distinzione tra vertici bianchi e neri è inutile, anzi meglio, l'hai già fatta suddividendo i vertici in due insiemi $A$ e $B$. Nota che la condizione che dici tu della bicolorazione è equivalente alla bipartizione (fatto interessante e abbastanza di base, che qualcuno dei più giovani potrebbe cimentarsi a dimostrare, anche tu stessa se non lo sai ancora fare) e, osservazione generale, colorare le cose è lo stesso che dire "divido tutto in scatole" o anche "costruisco degli insiemi disgiunti a partire da questi elementi".
• Nel secondo punto ci sono un paio di cose che non sono spiegate troppo bene. La prima è che il fatto che tu dici di ripetere una certa operazione "finché non accade che tutti i vertici sono colorati" ma sarebbe stato molto più chiaro e più formale se dicevi "finché i vertici dispari sono spariti, quindi ho colorato tutti i vertici", in generale consiglio prima di dire cosa fai, e prima di dare per scontato che riesci ad avere una certa cosa per usarla per il ragionamento successivo è meglio dimostrarla o giustificare di averla. La seconda questione è che non dici perché alla fine "la colorazione risultante rispetterà le condizioni del problema" visto che colori più di una volta i vertici con grado dispari, quindi non puoi cavartela semplicemente dicendo che è lo stesso del punto precedente.
• Infine, dato che la dimostrazione che proponi è una costruttiva, ti consiglierei di improntare la dimostrazione in modo costruttivo, in particolare secondo me potrebbe essere utile impostare un'induzione. Questo per dire che ti consiglio di scrivere per bene una dimostrazione che usi questa tecnica; fattela anche pure per te, tanto per metter in chiaro le idee, senza doverla postare per forza.

[Tess]

Ultimo piccolo commento al problema.
Questo è l'IMO 6 del lontano 1986.