Bicromatico

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Mattysal
Messaggi: 161
Iscritto il: 06 feb 2018, 14:54
Località: Oria (BR)

Bicromatico

Messaggio da Mattysal » 07 mag 2020, 12:11

Determinare il minimo [math] con la seguente proprietà.
Per ogni griglia [math]x[math] con [math], tale che ogni casella sia colorata di rossa o di blu, esiste un rettangolo che ha i vertici dello stesso colore. (Considerare le caselle come vertici).

TeoricodeiNumeri
Messaggi: 37
Iscritto il: 14 lug 2019, 09:58

Re: Bicromatico

Messaggio da TeoricodeiNumeri » 15 mag 2020, 09:53

Testo nascosto:
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$.

Rispondi