Cioccolatisti morigerati
Jacopo e Cecilia hanno trovato una tavoletta di cioccolato di dimensioni m×n (sia m che n sono maggiori di 1) e intendono mangiarsela. Però hanno promesso al loro papà (io) di non essere troppo ingordi, e quindi hanno inventato un modo piuttosto peculiare per dividersela. A turni alterni un bambino divide la tavoletta in due parti su una delle suddivisioni. La divisione deve lasciare due parti di dimensioni diverse, quindi non è permesso tagliarla a metà: a questo punto il bambino si mangia la parte più piccola. Quando non è più possibile fare una suddivisione di questo tipo, chi rimane col cerin… ehm, con la tavoletta in mano perde, e l’altro si prende tutta per sé la seconda tavoletta che mi ero dimenticato di dire che i due avevano trovato: morigerati sì, ma non molto.
Tanto per fissare le idee, il gioco termina quando si arriva a una tavoletta 2×2, che può essere solo divisa in due parti 1×2 che però sono uguali: non è mai possibile arrivare a una tavoletta 1×n, perché una tavoletta 2×n non può essere divisa a metà e in una m×n con m≥3 un taglio sulle righe ne lascia almeno 2. Avete idea di come trovare le tavolette vincenti, senza leggere la soluzione qui sotto?
Per la cronaca, il gioco è stato proposto su Stack Exchange, dove potete trovare due risposte equivalenti. La mia soluzione procede alla rovescia per semplicità espositiva. Ricordo a chi non è avvezzo alle dimostrazioni di strategie vincenti nei giochi a due di questo tipo – dove cioè chi non ha più mosse a disposizione perde – che una posizione è vincente quando esiste una mossa che lascia l’avversario in una posizione perdente ed è perdente quando tutte le mosse possibili lasciano l’avversario in una posizione vincente.
Sappiamo che 2×2 è una posizione perdente: vediamo cosa possiamo dire per un generico 2×n. 2×3 è vincente: si mangia un pezzo 2×1 e si lascia 2×2. 2×4 è perdente: l’unica possibilità ammessa è mangiare un pezzo 2×1 e quindi si lascia l’avversario in una posizione vincente. Quindi le posizioni da 2×5 a 2×7 sono vincenti (si lascia all’avversario la tavoletta 2×4), la 2×8 è perdente (si deve lasciare una di quelle da 2×5 a 2×7), e penso sia abbastanza chiaro a tutti che si può dimostrare per induzione che tutte le posizioni 2×2k, con k≥1, sono perdenti mentre le altre 2×n sono vincenti.
Ora andiamo avanti: possiamo supporre senza perdita di generalità che m≤n. 3×3 è evidentemente perdente, perché l’unica mossa possibile manda in 2×3 che è vincente. 3×4 e 3×5 sono pertanto vincenti, visto che si può arrivare a 3×3; 3×6 è perdente perché si può andare a 2×6 (che abbiamo visto prima essere vincente) oppure 3×4 o 3×5 che sono anch’esse vincenti; da 3×7 a 3×11 si può arrivare a 3×6 e quindi tutte quelle sono posizioni vincenti. Immagino che non abbiate problemi a dimostrare – sempre per induzione – che le posizioni 3×(3·2k) siano perdenti e le altre 3×n vincenti, e forse a questo punto siete anche pronti a immaginare la regola generale: le posizioni m×(m·2k) sono perdenti, le altre vincenti. Qui sotto uno sketch of proof, sono troppo pigro per mettere tutti i dettagli.
Innanzitutto, da una posizione m×m con m>2 si può solo arrivare a una posizione r×m e l’avversario può giungere a r×r, lasciandoci quindi in una posizione perdente per ipotesi induttiva. Nel caso di una posizione m×(m·2k) i casi sono due: se si tolgono delle colonne arrivando a m×w il nostro avversario può sempre passare a m×(m·2k−1) (perché?) che è perdente sempre per ipotesi induttiva: se invece si tolgono delle righe arrivando a r×(m·2k) il nostro avversario può sempre passare a r×(r·2k) (perché?) che di nuovo è perdente per ipotesi induttiva. Tutto qua.
Morale della favola? Se si inizia con calma a provare i casi facili magari può venire un’idea della soluzione. Tentar non nuoce :-)
Leave a comment