Soluzione al quizzino del sabato sera (in cui si mostra come, a volte, si possano davvero sfruttare evidenti ragioni di simmetria)

Il problema chiedeva di colorare una scacchiera quadrata con due colori, in modo tale che qualunque rettangolo contenuto in essa (non degenere) abbia i quattro angoli colorati con entrambi i colori.

Per scacchiere piccole ci si riesce, il post forniva degli esempi. Per scacchiere grandi, invece, che succede?

Primo fatto: se per un certo valore di n la scacchiera n×n non è colorabile, allora non lo sono nemmeno quelle il cui lato ha una lunghezza maggiore di n, dato che non siamo in grado di colorarne nemmeno una loro parte. Quindi il problema diventa: n può essere grande quanto si vuole, oppure esiste un valore massimo?

Bene, si dimostra che se n = 5 la scacchiera non è colorabile come richiesto, e se invece n = 4 ci si riesce.

Prima la parte facile: ecco una possibile colorazione di una scacchiera 4×4:

Ora vediamo cosa succede con una scacchiera 5×5. Essa è composta da 25 caselle, quindi se la colorazione richiesta fosse possibile, dovremmo essere in grado di colorarne almeno 13. Questa affermazione è giustificata da evidenti ragioni di simmetria: se non fossimo in grado di colorare 13 caselle di giallo quel colore che ho usato nel disegno qua sopra, ce ne sarebbero almeno 13 bianche. Bene, allora coloriamo quelle bianche e facciamo diventare bianche le altre, e siamo da capo.

E quindi il problema si è ridotto a questo: riusciamo a colorare almeno 13 caselle?

Se nella prima riga ne colorassimo cinque (ricordiamo che non è importante che sia proprio la prima riga):

nella seconda ne potremmo mettere soltanto una, e così pure nella terza, nella quarta e nell'ultima: se ne mettessimo di più, avremmo dei rettangoli con gli angoli monocolore. In questo modo saremmo in grado di colorare solo 5 + 1 + 1 + 1 + 1 = 9 caselle, poche.

Proviamo con quattro caselle colorate nella prima riga:

In questo caso potremmo colorarne due nelle righe successive, e non di più. In questo modo otterremmo 4 + 2 + 2 + 2 + 2 = 12 caselle: troppo poche.

Se poi la prima riga avesse solo tre caselle colorate, ne potremmo inserire tre anche nella seconda:

e poi però nelle righe successive non potremmo inserirne più di due, una in una delle prime tre caselle, e l'altra in una delle altre due. Se ne inserissimo di più, formeremmo un rettangolo con gli angoli monocolore.

Quindi in questo caso il massimo numero di caselle colorate sarà 3 + 3 + 2 + 2 + 2 = 12, ancora troppo poche.

Fine della dimostrazione: 13 caselle non si possono colorare, quindi le uniche scacchiere colorabili nel modo richiesto sono quelle aventi n uguale a 2, 3 oppure 4.

Quizzino del sabato sera

Data una scacchiera n×n, siete capaci di colorare, utilizzando solo due colori, le sue caselle in modo tale che tutti i rettangoli di dimensione a×b (con a e b compresi tra 2 e n) che si possono formare al suo interno abbiano le caselle d'angolo colorate con entrambi i colori? Fino a che valore di n riuscite ad arrivare?

Per esempio, se la scacchiera è 2×2, queste due colorazioni vanno bene:

Questa, invece, va bene per una scacchiera 3×3:

Insomma, non devono esistere rettangoli con le caselle d'angolo colorate dello stesso colore.