Colorazioni del piano

[dario2994]

Questo problema dovrebbe essere facile... ma io non sono riuscito a risolverlo:

Coloriamo i punti del piano con due colori; dimostrare che esiste un
rettangolo coi vertici dello stesso colore.

Questo problema l'ho trovato in questa interessante raccolta di esercizi di combinatoria ;)
http://www.mat.uniroma1.it/~gewurz/esercizi.pdf

[Tibor Gallai]

Sono vere cose mooolto più forti di questa.
Hint: prendi un qualsiasi insieme di 21 punti disposti a griglia 3x7, e cerca i 4 vertici tra questi punti.
Bonus: prendi 20 punti comunque disposti nel piano, e mostra che puoi colorarli in modo che non contengano un rettangolo coi veritici di un solo colore.

[dario2994]

Ok ho dimostrato la questione della griglia 3x7
Assumo wlog che il colore più presente sia il rosso, quindi ci sono almeno 11 punti rossi. Perchè non siano presenti rettangoli le colonne dove sono presenti 2 pallini devono essere tutte differenti, altrimenti si creerebbe un rettangolo. Le disposizioni possibili di 2 elementi su 3 sono ovviamente 3, quindi si può ammettere che ci siano massimo 3 colonne da 2 elementi e perciò 4 da 1... a questo punto risulta che il massimo dei punti è 10 mentre deve essere almeno 11. Se si ammette che non ci sono colonne da 2 allora se ne può mettere 1 da 3 e 6 da 1... che fa 9 ed è un assurdo.
Penso che sia valida come dimostrazione.
Il bonus non l'ho ben capito...

[Tibor Gallai]

Il bonus non l'ho ben capito...

Infatti ho misspellato "vertici".
Il senso era questo: siccome bastano 21 punti opportunamente disposti per trovare un rettangolo monocromatico, viene naturale chiedersi se si possa fare di meglio. Ovvero, è possibile prendere 20 punti (o meno), disposti in modo opportuno, che contengano un rettangolo monocromatico qualunque sia la colorazione? Risposta: no, perché...

La tua dimostrazione trascura qualche caso (o lo tratta in modo un po' implicito), ma l'approccio va bene e funziona.

Il modo in cui l'ho risolto io è un po' diverso: la prima riga ha almeno 4 punti rossi (wlog). In corrispondenza di questi 4 punti, nella seconda riga vi sono almeno 3 punti bianchi (o si formerebbe un rettangolo). In corrispondenza di questi 3 punti, nella terza riga vi sono almeno 2 punti di uno stesso colore. Se sono rossi, formano un rettangolo con la prima riga; se sono bianchi, formano un rettangolo con la seconda riga.