il gioco del salto

[frengo]

forse a qualcuno questo problema ricorderà qualcosa.....

Su una scacchiera infinita vi sono $ n^2 $ pedine, disposte una per casella in un quadrato $ n $x$ n $.Una mossa consiste in un "salto" di una pedina (in orizzontale o in verticale) sopra una casella occupata da una pedina su una casella libera immediatamente successiva. La pedina "sopra cui" è stato effettuato il salto viene rimossa. Determinare per quali n è possibile concludere il gioco con una sola pedina rimasta.

ciao ciao

ps una volta risolto il problema un'altra questione si apre:spiegarlo......

EDIT:DIFFICILE...lo paragonerei al 6 di cesenatico, forse leggermente sopra.

[Simo_the_wolf]

Ci vorrebbero un migliaio di disegni...

Cmq si può fare per i non multipli di 3.

Induttivamente : si fa per 2 e per 4. Poi si trova il modo di levarne 3 di fila in modo che sia tutto libero da una parte e almeno una pedina sotto... Ehm cerco di spiegarmi:

? X X X ?
? 1 2 3 ?
? 4 ? ? ?

dove le X sono le caselle per forza libere, i numeri sono le pedine e ? quello che si vuole.
Con 3 mosse [4 mangia 1, 3 mangia 2 e 4 mangia 3] si levano le 3 pedine sopra.

In questo modo si riesce a levare il "contorno" di 3 cioè pertendo ad esempio da un 7x7 posso arrivare a un 4x4 "smussando" due lati (spero di essere stato chiaro...).

Per i multipli di 3 non si può fare. Coloriamo le infinite caselle con 3 colori in diagonale (una diagonale fucsia una marrone e una beige). In ogni mossa io tolgo 1 pedina da 2 colori e ne aggiungo una al restante colore (provare per credere) e quindi le differenze tra i colori rimangono invariate modulo 2.

Ma all'inizio abbiamo che le differenze sono tutte 0 mentre alla fine dovremmo avere che le differenze sono 1, 1, 0 da cui l'assurdo.

[Marco]

Istanbul, IMO 1993, First day, Problem 3, 6 punti [eh.... quanti ricordi...]

@Simo: In verità per eliminare le caselle che dici, basta un po' meno: serve una sola casella libera.

? X ? ? ?
? 1 2 3 ?
? 4 ? ? ?

Le altre due caselle non servono, difatti.