OliForum Matematico

Il minimo $k$ è $7$.
Prima di cominciare la dimostrazione, enuncio dei lemmi banalissimi:
Lemma $1$: se in una tabella $3\times m$ non verifica la proprietà per cui esiste un rettangolo con tutti i vertici dello stesso colore, allora cambiando di colore esattamente una casella di ogni eventuale colonna bicromatica si ottiene una nuova tabella $3\times m$ che non verifica la proprietà.

Lemma $2$: se una tabella non ha colonne monocromatiche allora esiste un rettangolo con i vertici dello stesso colore sse due colonne sono uguali.

Siccome le possibili colorazioni bicromatiche di una colonna sono $6=2^3 -2$, per il lemma $2$ è possibile costruire una tabella $3\times 6$ che non verifica la proprietà richiesta (basta prendere una tabella con $6$ colonne bicromatiche colorate tutte in maniera diversa).

Invece, siccome per Pidgeonhole, presa una qualsiasi tabella $3\times 7$ a colonne bicromatiche, ci saranno sempre due colonne uguali, per il lemma $1$ tutte le tabelle $3\times 7$ verificano la proprietà, e quindi $k=7$.