Gioco del Tris

[Enrico Leon]

Avete presente il Gioco del Tris? Quello con 9 caselle, le X e le O? Bene!
Quante X (oppure O) posso collocare al massimo nella griglia senza che si formi alcun tris?

[Sonner]

Avete presente il Gioco del Tris? Quello con 9 caselle, le X e le O? Bene!
Quante X (oppure O) posso collocare al massimo nella griglia senza che si formi alcun tris?

6?

[SkZ]

allora dato che si puo' finire in patta, almeno 5 di certo
le mosse possibili sono 3
1) al centro (coinvolge 4 tris possibili)
2) sull'angolo (3 tris possibili)
3) sul lato (2 tris possibili)

quindi posti prima quelli sui lati (4), inizi a mettere sugli angoli. per non fare tris devi mettere sui 2 angoli opposti.

quindi 6, come diceva Sonner

[Enrico Leon]

Bene, ora supponiamo che la griglia sia n*n......

[SkZ]

e non devi averne quanti in file? n?
se n, un'idea puo' essere:
1) riempi le casella con un lato in comune col bordo [$ ~4(n-2) $]
2) riempi il quadrato centrale lasciando una diagonale libera [$ ~(n-2)^2-(n-2)=(n-2)(n-3) $]
3) riempi gli estremi di quella diagonale [2]
tot=$ ~(n-2)(n+1)+2 $

[Enrico Leon]

Ma io dicevo per ridere!!
Tuttavia, già che ci siamo... Se $ n $ è dispari probabilmente basta riempire tutto tranne una diagonale. Se $ n $ è pari... boh... una casella ancora in meno?[/tex]

[SkZ]

e' circa quello che ho scritto. solo con uno scambio di caselle
riscriviamolo meglio
Dato un quadrato $ ~n\times n $, per colorarlo in modo che ogni colonna, riga e diagonale abbia solo $ ~m $ caselle colorate basta colorare con un certa sequenza $ ~m $ casella della prima riga. Poi quando si colorano le caselle delle righe successive si sposta ogni volta di 1 casella il pattern sempre nella stessa direzione.

[SkZ]

no, questo metodo non va bene per i quadrati di lato pari
vabbe. rimane quello detto inizialmente