17. Tagliando quadretti

[Toadino2]

Due amici, Alice e Bob, fanno questo gioco:
Dopo aver preso un foglio di carta quadrettata ed averne ritagliato un rettangolo $m*n$, a turno ognuno di loro, a partire da Alice, taglia ulteriormente questo rettangolo in due rettangoli secondo una linea orizzontale o verticale rispettante i quadretti, dopodiché ne scartano uno e passano l'altro all'avversario perché ripeta lo stesso procedimento: il primo che riceve un quadratino di 1x1, non potendo così più tagliare, perde.
Determinare il vincitore, la svolgimento del gioco (ovviamente si presuppone che il vincitore utilizzi la strategia giusta e che non faccia mosse a caso), ed il vincitore nel caso venga imposta come ulteriore condizione l'essere obbligati a non scegliere il rettangolo da scartare e scartare, appunto, il più piccolo.

[mr96]

Nel caso si possa scegliere il quadrato da scartare penso diventi: vince chi inizia nel caso [tex]m \neq n[/tex], vince l'altro altrimenti. La strategia vincente sarà lasciare l'altro con un foglio quadrato.

L'altro caso penso sia analogo, ma non sono sicuro e ora sono in macchina da cellulare e non posso provare

[Toadino2]

Scusa il ritardo, me ne ero dimenticato XD
Quando torno ti dico

[aetwaf]

$Parte$ $1$
Vince A se $m\ne n$ e B in caso contrario
Supponiamo $m=n$
Qualunque mossa faccia il primo a giocare non otterrà mai un quadrato, infatti un lato resterà più lungo
Il secondo può ora ottenere un quadrato operando la stessa mossa del primo sull'altro lato
Quindi alla fine sarà il secondo a vincere dando all'altro il quadrato $1x1$ non ottenibile dal primo

Ora, se $m=n$ vince B per quanto appena detto
Se $m\ne n$ A può ottenere un quadrato con la prima mossa e diventando il secondo a giocare del primo caso
Quindi in questo caso vince A


$Parte$ $2$
Questo non è altro che il $Problema$ $15$ di questa staffetta in $2$ dimensioni

Notiamo che se si ottiene un quadrato, da quel punto in poi vince il secondo a giocare
Infatti il primo non otterrà un quadrato di sicuro con la sua mossa non potendo stare fermo
Inoltre il lato corto del rettangolo che si ottiene deve essere maggiore o uguale alla metà del lato lungo
Perciò il secondo a giocare potrà operare la stessa mossa sull'altro lato come nella $Parte$ $1$
Se $m=n$ vince quindi B

Sia ora $m\ne n$
Supponiamo $WLOG$ $m<n$
Definiamo la successione $a_p=2a_{p-1}+1\forall p\in \mathbb Z$ con $a_0=m$
Definiamola quindi anche sui negativi, cioè ad esempio $a_{-1}=\frac {a_0-1} 2$
A questo punto abbiamo $2$ casi

$Caso$ $1$, $n=a_p$
In questo caso vince B

$Proof$

Se A modifica il lato di $n$, B lo può portare a $a_{p-1}$ mentre A non poteva farlo
Infatti A poteva togliere al più $a_{p-1}$ portandolo a $a_{p-1}+1$
Inoltre B può sempre arrivare a $a_{p-1}$
Infatti A deve togliere almeno $1$, dunque $a_{p-1}$ diventa maggiore o uguale alla metà della lunghezza ottenuta, che sarà al più $2a_{p-1}$

Se invece A modificasse il lato di $m$, non potrebbe, per quanto detto prima, portarlo a un numero minore o uguale a $a_{-1}$
Quindi si otterrà un nuovo numero $b_0$
Definiamo ora $a_n$ con $a_0=b_0$
Di certo $n\ne a_p\forall p\in \mathbb Z$

Infatti $n$ appartiene alla successione precedente ma non a quella nuova

$Proof$
Il termine generico della successione è $2^na_0+2^n-1=2^n(a_0+1)-1$
Se $1$ valore appartenesse a $2$ successioni distinte varrebbe $2^p(a_0+1)=2^q(b_0+1)$
Con $p\ne q$ ($WLOG$ $p>q$)
Ma allora $b_0=2^{p-q}a_0+2^{p-q}-1\ge 2a_0+1$
Quindi $b_0$ non sarebbe ottenibile da $a_0$ in $1$ mossa, perchè il primo elemento a ritroso la cui successione contiene $n$ sarebbe $a_{-1}$ per quanto appena detto

Ma allora B può portare il lato di $n$ da $n$ a un valore appartenente alla nuova successione
Vale infatti $a_p<n<2a_p+1$ cioè $n\le 2a_p$ $(1)$

Quindi B può sempre mettere i lati in successione in questo modo e A mai
Ma allora prima o poi otterrà un quadrato e sarà il secondo a giocare e, per quanto detto prima, vincerà
Infatti se A porta il lato piccolo a $1$ B otterrà $1$ procedendo di elemento in elemento della successione sul lato lungo
Se invece non arriva a $1$ allora si fermerà a un certo valore $c_0$
A questo punto B fa valere $a_p$, con $a_0=c_0$, il lato lungo e procedendo di nuovo elemento per elemento arriverà a $c_0$ ottenendo un quadrato
Quindi vince B

Se invece $n\ne a_p\forall p\in \mathbb Z$, con $a_0=m$ vince A
Infatti, come mostrato in precedenza nella $(1)$, A può con $1$ mossa portare il lato di $n$ a un elemento della successione invertendo l'ordine



Ora bisognerebbe provare a portarlo a $n$ dimensioni!!

[Toadino2]

Mi sembra sia tutto giusto puoi andare!