In una tabella 5x16 ogni quadratino puo' essere colorato scegliendo tra tre colori possibili: blu, giallo e rosso. Un sottoinsieme rettangolare della tabella formato da axb (a per b) quadratini lo chiamiamo RETTANGOLO (a e b devono essere entrambi maggiori o uguali a 2 e possono essere uguali). Un rettangolo si dice MONOCOLORE se i quattro quadratini che stanno ai vertici del rettangolo hanno lo stesso colore.

Il problema da risolvere consiste di due parti:
1) trovare una colorazione della tabella con il massimo numero di quadratini blu che non contenga rettangoli monocolore blu,
2) trovare una colorazione della tabella che renda minimo il numero di rettangoli monocolore.

Per fare qualche esperimento potrebbe essere utili la seguente applicazione javascript (puoi memorizzarla sul tuo computer e usarla anche off-line).
Cliccando su un quadratino della tabella puoi cambiargli colore . Premendo ripetutamente 'Vedi' verranno evidenziati i vertici dei rettangoli monocolore. Per contare il numero di rettangoli monocolore premi 'Conta'.

Ecco le soluzioni e una spiegazione "informale" delle due risposte!

1) Il massimo numero di quadratini blu che una colorazione della tabella puo' avere senza che ci siano rettangoli monocolore blu e' uguale a 26.
Un lato verticale di un rettangolo monocolore blu e' identificato da due quadratini blu lungo una colonna. Dato che ogni colonna contiene 5 quadratini, il numero di coppie possibili di quadratini blu e' 5*4/2=10. Per avere almeno un rettangolo monocolore blu e' sufficiente che una delle 10 coppie possibili si presenti in due colonne diverse. Quindi per massimizzare il numero di quadratini blu senza formare rettangoli monocolori blu basta distribuire le 10 coppie sulle prime 10 colonne e mettere un quadratino blu nelle restanti 6 colonne per un totale di 2*10+6=26 quadratini blu.

2) Il minimo numero di rettangoli monocolore e' uguale a 2.
Premendo uno dei tasti qui sotto vedrete alcune colorazioni con 2 rettangoli monocolore che ho ricevuto mentre il tasto RANDOM ne genera una partendo da una colorazione a caso e seguendo un algoritmo di ottimizzazione:

Ora vediamo di provare che il numero di rettangoli monocolore non puo' essere inferiore a 2. Dato che ci sono 5*16=80 quadratini i tre colori potranno essere distribuiti in due modi: ci sono due colori con 27 quadratini oppure almeno un colore con 28 quadratini. Nel primo caso, dato che 27-26=1, allora ci sara' almeno un rettangolo monocolore per ciascuno dei colori con 27 quadratini. Nel secondo caso dato che 28-26=2 ci saranno almeno due rettangoli monocolore del colore con almeno 28 quadratini. Notate che le soluzioni proposte da ABBY, MANCUSO e MARCHETTI rientrano nel primo caso mentre le altre nel secondo.

Questo problema ha un'interpretazione nel linguaggio della teoria dei grafi. Ogni quadratino della tabella rappresenta un lato di un grafo bipartito completo K_(5,16). Il primo quesito chiede di calcolare il numero di Zarankiewicz rispetto al grafo bipartito K_(2,2) che rappresenta un rettangolo monocolore. Il secondo quesito e' in relazione con la teoria di Ramsey per grafi bipartiti. Rispondere ai due quesiti proposti per tabelle piu' grandi puo' diventare molto complicato e in diversi casi la risposta e' ancora sconosciuta. Un caso di media difficolta' e' la tabella 7x13. Per i piu' curiosi consiglio di provare a dare un'occhiata alla seguente pagina di wikipedia: the Zarankiewicz problem.