Rettangolo da cancellare

milizia96
Alberto e Barbara fanno un gioco che si svolge su un rettangolo composto da $n\times m$ caselle unitarie.
Iniziando da Alberto, il giocatore di turno deve scegliere una casella $C$, che viene cancellata. Inoltre, ogni casella che non si trovi più in basso o più a sinistra rispetto a $C$ viene cancellata allo stesso modo. Ogni casella cancellata, chiaramente, non potrà più essere scelta. Dopo di che il gioco passa all'altro giocatore.

Chi cancella l'ultima casella perde.
In base alle dimensioni iniziali del rettangolo, quale dei due giocatori ha una strategia vincente?

Risposte
xXStephXx
Ho un dubbio sulle mosse :-D Se il primo giocatore cominciasse cancellando la seconda casella più a sinistra dell'ultima riga, poi resterebbe una sola casella?

milizia96
Scusa, mi ero espresso in modo sbagliato, ora ho corretto

xXStephXx
Ah bello! Anche così dovrebbe bastare una considerazione, ma più sottile della precedente, giusto? :D

milizia96
Molto più sottile, direi :)

milizia96
Va beh, vi dico la risposta, provate a dimostrarla:

axpgn
Eh, vabbè, fino a lì c'ero arrivato (più o meno), è il resto che mi manca ... :-D

Cordialmente, Alex

xXStephXx
Non ero riuscito a trovare una strategia vincente :D Ma in qualche modo è la struttura stessa del gioco che consente di dire chi vince. Cioè Alberto vince se con la prima mossa riesce ad ottenere una configurazione perdente (per chi se la ritrova). E Barbara vince se (partendo dalla configurazione che si ritrova) con la sua prima mossa riesce a passare ad Alberto una configurazione perdente... Ora, pure senza sapere quali sono le configurazioni perdenti, magari Alberto può "anticipare" l'eventuale mossa vincente di Barbara :-D Rimane da capire come xD

axpgn
Scusa Steph ma tutti i giochi di questo tipo funzionano così, cioè devi lasciare all'avversario una situazione comunque perdente (se esiste); il problema sta nel trovarla (e questo spesso si può almeno congetturare) ma ancor di più nel dimostrarla :-D, che è quello che vuole milizia ;-)

Cordialmente, Alex

xXStephXx
"axpgn":
Scusa Steph ma tutti i giochi di questo tipo funzionano così, cioè devi lasciare all'avversario una situazione comunque perdente (se esiste); il problema sta nel trovarla

Non so se si deve trovare davvero. In teoria basta capire che c'è :-D Poi sono così tutti i giochi, ma qui ragionando sulle prime due mosse (la prima di Alberto e la prima di Barbara) viene fuori una particolarità che consente ad Alberto di poter sempre trovare la configurazione giusta.

axpgn
Mi spiace ma non riesco a seguirti ... :| ... comunque ho trovato la strategia per i quadrati e per i rettangoli di spessore $1$ e $2$ mentre per gli altri ci sto ancora pensando anche se mi pare di poter congetturare che
isn't it? :D

Cordialmente, Alex

dan952
"xXStephXx":
In fondo le configurazioni che può raggiungere Barbara con la sua prima mossa... non sono troppo diverse da quelle che poteva raggiungere Alberto sin da subito... no?

Esatto Steph, penso che sia proprio questo il punto , se B avesse una strategia vincente, allora A avrebbe potuto giocarla prima di lui. Questo tipo di gioco è a informazione completa, cioè una possibile strategia di A e il vantaggio che ne guadagna ad attuarla è conosciuta anche da B e viceversa.

nino_12
"axpgn":
... mi pare di poter congetturare che
isn't it? :D

Cordialmente, Alex


Ma se uno si trova una configurazione simile:

._. _ ._ . _
|_|_|_|_
|_|

ha vinto.

E lo stesso se il quadratino è sopra, es.:

. _
|_|_._ ._ ._
|_|_|_|_|_

vince lasciando un angolo di 3 quadratini.

O non ho capito le regole?

axpgn
Se ho interpretato correttamente i tuoi disegni quelle situazioni non sono possibili ... O meglio la prima non è possibile in quanto per far sparire l'ultima riga meno il primo quadratino devi far sparire anche la seconda mentre la seconda situazione è possibile ma quando dico che "va lasciato un rettangolo più un quadratino" non intendo "qualsiasi rettangolo con l'aggiunta di qualsiasi quadratino" ma una configurazione scelta di volta in volta ... Spero di essere stato chiaro ... ;-)

Cordialmente, Alex

xXStephXx
Ah ma se hai trovato la strategia nel caso 2xn dovresti aver capito cosa deve fare Alberto come prima mossa no? :-D E ora praticamente è detto tutto...

axpgn
No, perché quando passo allo spessore $3$ non riesco a replicarla "banalmente"; riesco sì a vincere ma diversificando la strategia in funzione della risposta dell'avversario ...
E comunque quello che ho detto prima su "rettangolo+quadratino" non vale ... :-D

Cordialmente, Alex

xXStephXx
Ma non si tratta di replicare la strategia, l'avevo notato che non funziona più... però avrai almeno tentato di applicare la stessa prima-mossa :-D E a quel punto te ne dovresti accorgere.

axpgn
Premesso che tu non sai qual è la strategia std che ho trovato per i rettangoli di spessore $2$ (che tradotto significa "non è che stiamo parlando di due cose diverse?" :-D ), replicare la stessa prima mossa è esattamente quello che ho provato a fare ma purtroppo non funziona sempre ...

Cordialmente, Alex

xXStephXx
"axpgn":
Premesso che tu non sai qual è la strategia std che ho trovato per i rettangoli di spessore $2$ (che tradotto significa "non è che stiamo parlando di due cose diverse?" :-D )

Eheh no, con un po' di veggenza stiamo sicuramente parlando della stessa strategia... :D

dan952
Prendiamo un rettangolo R $n×m$, consideriamo il quadrato Q $2×2$ in basso a sinistra, la prima mossa di A sarà quella di cancellare il qudratino in alto a destra di Q, a questo punto resta una specie di "L" rovesciato o no di altezza $n$ e base $m$, qualunque mossa "conveniente" per non perdere subito faccia B, il giocatore A risponderà riducendo la base (o l'altezza ) della "L" a due, B dunque non potrà fare altro che cancellare un quadratino lungo l'altezza che stia più in alto del secondo o del primo (per evitare di perdere subito, a quel punto A fa la stessa cosa di prima, e quel che si ottiene alla fine è:

\( \begin{matrix}\square \\ \square & \square \end{matrix} \)

axpgn
Non se ho capito bene ma quello che tu dici è solo una delle strategie ma non vale sempre ...

Prendiamo il rettangolo $3 xx 3$ e usiamo una notazione scacchistica.
Il primo giocatore sceglierà $b2$ e l'altro ha perso perché al primo basterà replicare mossa per mossa quelle fatte dal secondo. Questo vale per tutti i quadrati $n xx n$.
Se passiamo al rettangolo $3 xx 4 $ questo non vale più; supponiamo che il primo scelga ancora $b2$ come prima allora al secondo basterà scegliere $d4$ è il primo si troverà nella situazione in cui era il secondo nel caso precedente perciò ha perso.

Cordialmente, Alex

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.