Il principio dei cassetti - 19. Rettangolo con vertici dello stesso colore

Forum dedicato ai quesiti irrisolti presenti nella collezione di Base5, nel vecchio forum ed in quello attuale.

Moderatori: Gianfranco, Bruno

Rispondi
Admin
Amministratore del sito
Amministratore del sito
Messaggi: 869
Iscritto il: mer apr 20, 2005 3:47 pm
Località: Benevento

Il principio dei cassetti - 19. Rettangolo con vertici dello stesso colore

Messaggio da Admin »

Admin ha scritto:
sab dic 03, 2005 5:09 pm
Dalla sezione "Il principio dei cassetti"

19. Rettangolo con vertici dello stesso colore

Supponiamo che ciascun punto di un piano sia colorato di rosso o di blu.
I colori sono assegnati a caso, senza alcuna regolarità.
Dimostrare che esiste qualche rettangolo che ha tutti i vertici dello stesso colore.
Consideriamo una griglia quadrettata nel piano, e consideriamo come punti i soli nodi di questa griglia.
Indichiamo con $R$ e $B$, rispettivamente i vertici rossi e blu.
Utilizziamo una notazione a colonne per descrivere un generico reticolo della griglia.
Ad es. la notazione

$$ r = \left [ \begin{matrix} \vdots \\ \cdots \\ \cdots \\ \cdots \\ \vdots \end{matrix} \right ] \left [ \begin{matrix} \vdots \\ R \\ R \\ B \\ \vdots \end{matrix} \right ] \left [ \begin{matrix}\vdots \\ R \\ B \\ R \\ \vdots \end{matrix} \right ] \left [ \begin{matrix} \vdots \\ R \\ B \\ R \\ \vdots \end{matrix} \right ] \left [ \begin{matrix} \vdots \\ \cdots \\ \cdots \\ \cdots \\ \vdots \end{matrix} \right ]$$

corrisponderà al seguente reticolo:
grid.png
grid.png (8.13 KiB) Visto 23835 volte
Il ragionamento iniziale per la dimostrazione è il seguente:
consideriamo una colonna iniziale, avente almeno $2$ punti dello stesso colore, ed affianchiamo ad essa, via via altre colonne, sempre aventi $2$ punti dello stesso colore,
fino a che non sia possibile individuare nel reticolo che si viene a formare, un rettangolo con vertici dello stesso colore.

Tale ragionamento lo implementiamo con il principio dei cassetti.

Applichiamo una prima volta il principio dei cassetti per determinare la colonna in modo che abbia almeno $2$ punti dello stesso colore.
Banalmente la colonna dovrà avere almeno $3$ vertici per essere sicuri che ne abbia almeno $2$ dello stesso colore.
Pertanto consideriamo colonne di $3$ punti.

Si nota che le possibili differenti colonne aventi almeno $2$ punti di colore rosso sono
$$\left [ \begin{matrix} R \\ R \\ - \end{matrix} \right ], \left [ \begin{matrix} R \\ - \\ R \end{matrix} \right ], \left [ \begin{matrix} - \\ R \\ R \end{matrix} \right ]$$
Analogamente le possibili differenti colonne aventi almeno $2$ punti di colore blu sono
$$\left [ \begin{matrix} B \\ B \\ - \end{matrix} \right ], \left [ \begin{matrix} B \\ - \\ B \end{matrix} \right ], \left [ \begin{matrix} - \\ B \\ B \end{matrix} \right ]$$

Bene, queste $6$ colonne saranno i nostri cassetti.
I nostri oggetti (o piccioni che dir si voglia) invece saranno le infinite colonne con $3$ punti (essendo il piano infinito).

Applicando quindi nuovamente il principio dei cassetti, appare chiaro che essendo infinite le colonne (ne bastano $7$ in realtà), sicuramente vi sarà un cassetto con almeno $2$ colonne.
Quindi vi saranno sicuramente $2$ colonne uguali e che hanno almeno $2$ punti dello stesso colore.
E quindi le $2$ colonne individuano proprio un rettangolo con vertici dello stesso colore.

SE&O
Admin
Pietro Vitelli (Amministratore del Forum)
"Un matematico è una macchina che converte caffè in teoremi" Paul Erdös
www.pvitelli.net

Rispondi