Consideriamo una griglia quadrettata nel piano, e consideriamo come punti i soli nodi di questa griglia.Admin ha scritto: ↑sab dic 03, 2005 5:09 pmDalla 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.
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:
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