Di tutti i colori

[franco]

Un quadrato 10x10 è diviso in cento caselle 1x1.
Ogni casella è colorata in maniera che ogni riga ed ogni colonna contengano al massimo 4 colori distinti.
Qual è il numero massimo di colori distinti utilizzabili per le 100 caselle?

www.diophante.fr
G2824

Un carré 10x10 est divisé en 100 cases 1x1.
Chaque case est coloriée de façon que chaque ligne et chaque colonne contienne au plus 4 couleurs distinctes.
Quel est le nombre maximum de couleurs distinctes utilisables pour les 100 cases ?

[NothIng]

Prendo un pennellone e in un colpo solo dipingo tutte le 100 caselle con lo stesso colore: n=1; un colore per ogni riga e ogni colonna.
Con un pennellino coloro le caselle sulla diagonale principale con altri 10 colori diffenti: n=11; due colori per ogni riga e ogni colonna.
Poi coloro una parallela alla diagonale con altri 10 colori diffenti, quando arrivo sul bordo riavvolgo e riparto dall'altro lato: n=21; tre colori per ogni riga e ogni colonna.
Stessa cosa con un'altra parallela: n=31; quattro colori per ogni riga e ogni colonna.

Sicuramente quindi deve essere: 31 <= n < 100

[franco]

Prendo un pennellone e in un colpo solo dipingo tutte le 100 caselle con lo stesso colore: n=1; un colore per ogni riga e ogni colonna.
Con un pennellino coloro le caselle sulla diagonale principale con altri 10 colori diffenti: n=11; due colori per ogni riga e ogni colonna.
Poi coloro una parallela alla diagonale con altri 10 colori diffenti, quando arrivo sul bordo riavvolgo e riparto dall'altro lato: n=21; tre colori per ogni riga e ogni colonna.
Stessa cosa con un'altra parallela: n=31; quattro colori per ogni riga e ogni colonna.

Sicuramente quindi deve essere: 31 <= n < 100

Grazie per la risposta
Avevo idea che 31 fosse effettivamente il numero massimo di colori utilizzabili per risolvere il quesito ma ho preferito attendere la pubblicazione delle soluzioni sul sito francese www.diophante.ft da cui avevo preso il problema.

Qui sotto riporto anche la soluzione dell'autore del problema (Raymond Bloch) che dimostra l'impossibilità di usarne 32.
La traduzione è di Google ma mi sembra abbastanza comprensibile ...

Il numero massimo di colori distinti su una griglia 10x10 è 31.
Per dimostrarlo, supponiamo per assurdo che vi siano 32 colori distinti. Sia $R_i$ l'insieme dei 4 colori distinti presenti nella riga $i$ (per $i=1, 2, \dots, 10$), con $|R_i|=4$.
Se tutti i dieci insiemi $R_i$ avessero un colore in comune con ciascuna delle altre 9 righe, allora ogni riga avrebbe un colore in comune con $R_1$; di conseguenza, le restanti 9 righe potrebbero contenere al massimo altri 3 colori ciascuna. Ciò porterebbe a un numero massimo di $4 + 9 \times 3 = 31$ colori distinti, il che contraddice la nostra ipotesi iniziale di 32 colori.
Esistono dunque almeno 2 righe i cui colori sono tutti distinti tra loro: in ognuna delle 10 colonne, le 2 caselle appartenenti a queste 2 righe presentano colori differenti. Ogni colonna può quindi introdurre al massimo 2 colori aggiuntivi non presenti nelle 2 righe considerate. Le 2 righe contengono complessivamente al massimo 8 colori, mentre le 10 colonne possono aggiungerne al massimo altri 20: il numero totale di colori distinti è dunque pari, al massimo, a $8 + 20 = 28$, il che costituisce un'ulteriore contraddizione rispetto all'ipotesi di 32 colori.
È così dimostrato che il numero massimo di colori distinti su una griglia 10x10 è 31.
Numerando le caselle di ciascuna riga da 0 a 9, da sinistra verso destra, un modo per selezionare 30 caselle con colori distinti è il seguente: 012/123/234/345/456/567/678/789/019/089; tutte le restanti caselle vengono riempite, in modo uniforme, con il 31° colore.