Rettangoli di carta
Ciao ragazzi, avrei bisogno di aiuto con questo problema.
Alice e Bob fanno un gioco molto divertente. Da un foglio di carta quadrettata ritagliano un rettangolo $m × n$, dopodiché a turno (iniziando da Alice) ognuno di loro deve tagliare il rettangolo in due rettangoli (il taglio deve essere orizzontale o verticale, e rispettare i quadretti), scartarne uno e passare l’altro al giocatore successivo. Chi riceve il rettangolo $1×1$ perde. 1. Chi vince, e come? 2. Come cambia il gioco se sono costretti a scartare il rettangolo più piccolo?
Per il primo punto ci sono: se $m=n$, allora Alice perde; se $m\ne n$, allora Alice vince, perché può formare un quadrato da dare all'avversario e destinarlo alla sconfitta.
Ma per il secondo punto? Sono arrivato a dire solo che, nuovamente, se Alice comincia con un quadrato, perde e che, se Alice comincia con un rettangolo tale che $m\leq 2n$, vince (perché in questo caso può trasformarlo in un quadrato). Però non riesco a trattare bene il caso $m>n$.
Alice e Bob fanno un gioco molto divertente. Da un foglio di carta quadrettata ritagliano un rettangolo $m × n$, dopodiché a turno (iniziando da Alice) ognuno di loro deve tagliare il rettangolo in due rettangoli (il taglio deve essere orizzontale o verticale, e rispettare i quadretti), scartarne uno e passare l’altro al giocatore successivo. Chi riceve il rettangolo $1×1$ perde. 1. Chi vince, e come? 2. Come cambia il gioco se sono costretti a scartare il rettangolo più piccolo?
Per il primo punto ci sono: se $m=n$, allora Alice perde; se $m\ne n$, allora Alice vince, perché può formare un quadrato da dare all'avversario e destinarlo alla sconfitta.
Ma per il secondo punto? Sono arrivato a dire solo che, nuovamente, se Alice comincia con un quadrato, perde e che, se Alice comincia con un rettangolo tale che $m\leq 2n$, vince (perché in questo caso può trasformarlo in un quadrato). Però non riesco a trattare bene il caso $m>n$.
Risposte
Parti dall'idea che, a gioco corretto, vince chi da un quadrato 2x2 all'altro/a (perché?)
Perché in questo modo, se non ci sono imbrogli, chi riceve il quadrato 2x2 non può che ritagliarne metà, così che il suo avversario riceve un rettangolo 2x1 e, ritagliandone nuovamente metà, dà il quadratino 1x1 al primo giocatore e vince. Alla prima domanda ho risposto, è con la seconda che mi sono incartato (pun not intended) 
Perdonami, non avevo letto
Quando si arriva al quadrato, perde sempre chi lo riceve: questo accade in entrambe le modalità.
Nella seconda modalità, Alice quindi vince se il rettangolo iniziale è mx2m. Partendo da ciò, se il rettangolo iniziale è mx(2m+1), allora vince Bob. Se invece è mx(2m+k) con k=2,3,... allora vince Alice.
Quando si arriva al quadrato, perde sempre chi lo riceve: questo accade in entrambe le modalità.
Nella seconda modalità, Alice quindi vince se il rettangolo iniziale è mx2m. Partendo da ciò, se il rettangolo iniziale è mx(2m+1), allora vince Bob. Se invece è mx(2m+k) con k=2,3,... allora vince Alice.
Potresti darmi qualche indizio per capire il ragionamento che porta a questo risultato?
Sono andato ad intuito 
Adesso ci ho pensato su e funziona.
Prova i seguenti rettangoli:
1x3 1x7 1x15
2x5
3x7
4x9
5x11
....
mx(2m+1)
Il punto è che Alice non può mai tagliare in verticale altrimenti Bob le restituisce un quadrato.
Mentre se Alice taglia in orizzontale, allora Bob può sempre costringerla ad entrare in una delle suddette combinazioni.
Per esempio, dato 3x7, Alice può dare un 2x7 e vedersi restituire un 1x7 e infine un 1x3 (indipendentemente dal taglio).
Dato 4x9, il gioco potrebbe proseguire con 3x9 e Bob le restituisce il 3x7...e via come sopra.
Oppure Alice da un 2x9 e Bob le restituisce un 2x5.
Insomma Bob vince nella casistica mx(2m+1).
P.S. Mentre mi appisolavo guardando un video ho pensato che la generalizzazione dev'essere qualcosa del tipo che Bob vince se si parte con un quadrato e se il rettangolo è di dimensioni $mxx(2^im+2^(i-1))$ con i= 1,2,3,...
Vedi se tutto torna e la cosa ha senso.
Adesso ci ho pensato su e funziona.
Prova i seguenti rettangoli:
1x3 1x7 1x15
2x5
3x7
4x9
5x11
....
mx(2m+1)
Il punto è che Alice non può mai tagliare in verticale altrimenti Bob le restituisce un quadrato.
Mentre se Alice taglia in orizzontale, allora Bob può sempre costringerla ad entrare in una delle suddette combinazioni.
Per esempio, dato 3x7, Alice può dare un 2x7 e vedersi restituire un 1x7 e infine un 1x3 (indipendentemente dal taglio).
Dato 4x9, il gioco potrebbe proseguire con 3x9 e Bob le restituisce il 3x7...e via come sopra.
Oppure Alice da un 2x9 e Bob le restituisce un 2x5.
Insomma Bob vince nella casistica mx(2m+1).
P.S. Mentre mi appisolavo guardando un video ho pensato che la generalizzazione dev'essere qualcosa del tipo che Bob vince se si parte con un quadrato e se il rettangolo è di dimensioni $mxx(2^im+2^(i-1))$ con i= 1,2,3,...
Vedi se tutto torna e la cosa ha senso.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo