Page 44 - progetto alice

S. Capparelli, P. Maroscia Alcuni problemi di matematica discreta linguaggio matematico. Tuttavia, con un po’ di concretezza e di buon senso, si può osservare che, fissati arbitrariamente 3 nodi sul nostro foglio, certa- mente 2 di essi hanno uno stesso colore. Potrebbe sembrare un’osservazione banale, quasi irrilevante, ma come vedremo, è proprio quello che ci servirà per il “decollo”. Ebbene, prendiamo tre nodi consecutivi A, B, C disposti su una linea ver- ticale, per fissare le idee, diciamo l 0 e consideriamo le linee orizzontali della quadrettatura, o meglio le semirette orizzontali (a destra) uscenti da A, B, C, che indichiamo rispettivamente con a, b, c. Consideriamo poi le terne di nodi (A 1, B 1, C 1), (A 2, B 2, C 2), (A 3, B 3, C 3), ecc. ottenute intersecando via via le semirette a, b, c con le linee verticali parallele a l 0, diciamo l 1, l 2, l 3, ecc., come illustrato qui sotto: A A A A A A A A A 1 2 3 4 5 6 7 8 a B 1 B B 3 B 4 B B 6 B 7 B 8 5 2 B b C 1 C C 3 C 4 C C 6 C 7 C 8 2 5 C c l 0 l 1 l 2 l 3 l 4 l 5 l l 7 l 8 6 Fig. 8 Ora, in quanti modi è possibile colorare una terna di punti, utilizzando solo 2 colori? La risposta non è difficile, poiché si tratta essenzialmente di 3 scelte indipendenti da fare, ciascuna con 2 possibilità. Dunque vi sono esattamente 2 × 2 × 2 = 8 modi possibili. Ma allora, se consideriamo 8 linee verticali l 1, l 2, … l 8 parallele alla linea l 0 di partenza, basta ricorrere al Prin- cipio delle gabbie dei piccioni (che abbiamo già utilizzato per risolvere il Problema 2) per concludere che almeno 2 tra le 9 terne di punti in questio- ne: (A, B, C), (A 1, B 1, C 1), (A 2, B 2, C 2), …, (A 8, B 8, C 8), sono colorate ordinatamente nello stesso modo. Resta così individuato un rettangolo con i lati disposti lungo le linee della quadrettatura e avente come vertici nodi di uno stesso colore, ciò che fornisce la soluzione del nostro problema.