Problem 1615

Solution:

Supponiamo che, più in generale, un giocatore si trovi a dover effettuare una mossa con una fila di $n$ cioccolatini numerati da 1 a $n$; denoteremo con effettuare la mossa $k$, per il giocatore di turno, l'atto di mangiare i cioccolatini $\{1, \ldots, k\}$. Diremo che la mossa $k$ è legale se $1 \leq k \leq n$ e se fra i cioccolatini $\{1, \ldots, k\}$ ve n'è un numero dispari del gusto di 1. Diremo che una sequenza di $n$ gusti è vincente se il giocatore di turno, messo davanti a cioccolatini con i gusti in tale sequenza, possiede una strategia vincente; la sequenza verrà detta perdente in caso contrario. Il problema chiede di determinare il numero di sequenze perdenti di lunghezza 15.

Incominciamo con due semplici osservazioni:

Osservazione 1. Se una sequenza contiene un numero dispari di occorrenze del gusto 1, allora è vincente (la mossa $L$, dove $L$ è la lunghezza della sequenza, è legale e vincente per il giocatore di turno).

Osservazione 2. Sia data una sequenza di lunghezza $2n+1$ con un numero pari di occorrenze del gusto 1. Se questa è vincente, allora qualunque strategia vincente per il giocatore di turno deve cominciare con una mossa della forma $2k$, dove $0 < k \leq n$ è tale che il gusto $2k+1$ sia diverso dal gusto 1. In effetti, se il giocatore di turno effettuasse una mossa (legale) della forma $2h+1$, lascerebbe un numero dispari di cioccolatini di ciascun gusto, e dunque il giocatore successivo vincerebbe mangiando tutti i cioccolatini rimanenti. D'altra parte, poiché il numero di cioccolatini del gusto 1 avanzati dal giocatore di turno è in ogni caso dispari, è necessario perché la sequenza lasciata al giocatore successivo sia perdente che il gusto $2k+1$ sia diverso dal gusto 1.

Troveremo conveniente considerare per ciascuna sequenza di gusti di lunghezza $n$ una sequenza corrispondente di zeri e uni $x_{1} x_{2} \ldots x_{n}$, così costruita: $x_{i}=0$ se il numero di cioccolatini in $\{1, \ldots, i\}$ dello stesso gusto di 1 è pari, $x_{i}=1$ altrimenti. Si noti che $x_{1}=1$ e che a ciascuna sequenza $x_{1} x_{2} \ldots x_{n} \in \{1\} \times \{0,1\}^{n-1}$ corrispondono esattamente due sequenze di gusti, entrambe vincenti o entrambe perdenti (dunque parleremo di sequenze di zeri e uni a loro volta vincenti o perdenti).

Le sequenze che finiscono per 1 sono tutte vincenti. Supponiamo che una sequenza di lunghezza dispari finisca per 0 e suddividiamola in blocchi come segue:

Per l'osservazione 2, se questa è vincente il giocatore di turno deve effettuare una mossa di tipo $2k$, dove il $k$-esimo blocco riquadrato è del tipo 11 (si deve avere $x_{2k}=1$ affinché la mossa sia legale e $x_{2k+1}=x_{2k}$ perché il gusto di $2k+1$ sia diverso da quello di 1). Tale mossa lascia al giocatore successivo una sequenza del tipo
$$\begin{array}{|l|l|l|} \hline y_{2} y_{3} & y_{4} y_{5} & \cdots \\ y_{2n-2k} 0 \\\hline \end{array}$$
in cui, poiché è stato mangiato un numero dispari di cioccolatini di ciascun gusto, $y_{i}=x_{i+2k}$ per $i$ dispari e $y_{i} \neq x_{i}$ per $i$ pari. In altre parole, la sequenza $y_{i}$ è ottenuta dalla sequenza $x_{i}$ cancellando i primi $k$ blocchi riquadrati e, nei blocchi successivi, scambiando $00,01,10,11$ con $10,11,00,01$ rispettivamente. Fra le sequenze di lunghezza dispari che finiscono per 0 distinguiamo tre casi:

(i) non vi sono blocchi 11; allora la sequenza è perdente per l'Osservazione 2;

(ii) l'ultimo blocco 11, diciamo il $k$-esimo, non ha blocchi 01 alla sua destra; allora la sequenza è vincente: la mossa $k$ è legale e lascia all'avversario una sequenza del tipo (i) (che finisce anch'essa per 0 e ha lunghezza dispari);

(iii) l'ultimo blocco 11 ha un blocco 01 alla sua destra; allora la sequenza è perdente, perché qualunque scelta di un blocco 11 lascia all'avversario una sequenza di tipo (ii), che è vincente.

Riassumendo, dobbiamo contare le sequenze di tipo (i) e (iii) di lunghezza 15. Si tratta di scegliere il contenuto di 7 blocchi fra le possibilità $\{\boxed{00}, 01,10,11\}$ rispettando le condizioni date. Vi sono sempre due possibilità per l'ultimo blocco, che è del tipo $10$ o $00$. Le sequenze in cui non compare né 11 né 01, che sono perdenti, sono $2^{7}$. Fra le sequenze in cui compare almeno un blocco 11 o 01 e tali che l'ultimo blocco sia 10 o 00, quelle di tipo (i) o (iii) sono esattamente la metà: questo perché una sequenza è del tipo (i) o (iii) se e solo se la sequenza ottenuta cambiando i blocchi 11 in 01 e viceversa non lo è. Dobbiamo dunque aggiungere $\frac{2 \times 4^{6}-2^{7}}{2}=2^{12}-2^{6}$ sequenze perdenti.

Ricordando che a ciascuna sequenza perdente di zeri e uni corrispondono due sequenze perdenti originali, abbiamo dunque un totale di $2\left(2^{7}+2^{12}-2^{6}\right)=2\left(2^{6}+2^{6}+2^{12}-2^{6}\right)=2^{7}+2^{13}$ sequenze perdenti.

Visto che il problema riguarda una sequenza di 15 cioccolatini, e che 15 è un numero dispari, possiamo supporre che la sequenza sia costituita da $n=2k+1$ cioccolatini.

Osserviamo che se il tipo di cioccolatino che compare per primo a sinistra compare in totale un numero dispari di volte, allora Alberto vince mangiando tutti i cioccolatini alla prima mossa.

Supponiamo dunque che il cioccolatino più a sinistra compaia un numero pari di volte, che corrisponde a $2^{2k}$ casi, e supponiamo che tra essi $a_{k}$ sia il numero di volte in cui Alberto ha una strategia vincente e $b_{k}$ sia il numero di volte in cui Barbara ha una strategia vincente.

Con una verifica immediata si trova $b_{0}=0$ e $b_{1}=4$. Supponiamo ora $k \geq 2$ e quindi $n=2k+1 \geq 5$. Consideriamo dapprima il caso in cui la sequenza di cioccolatini termini con due cioccolatini dello stesso tipo, ossia LL oppure $FF$, quindi complessivamente in un numero di casi uguale a $2^{n-2}$. In questo caso è chiaro che colui che riesce a effettuare l'ultima mossa per mangiare i primi $n-2$ cioccolatini può anche mangiare anche gli altri due, e quindi ci sono $2b_{k-1}$ casi in cui Barbara vince.

Supponiamo ora che gli ultimi due cioccolatini siano di tipo diverso, per esempio LF, e consideriamo il tipo del primo e del terzultimo dei cioccolatini. Nel caso in cui questi tipi siano diversi, LF o FL, Alberto vince se fa la mossa (lecita) di mangiare tutti i cioccolatini salvo gli ultimi 3. Se invece il primo e il terzultimo dei cioccolatini sono dello stesso tipo, per esempio LL, Alberto, che non può mangiare tutti i cioccolatini, deve lasciare a Barbara una sequenza non vuota di cioccolatini. Se la sequenza rimasta comincia con L, Barbara può mangiare tutti i rimanenti, e quindi vince. Se la sequenza rimasta comincia con $F$, allora o il numero di F rimasto è dispari, e quindi Barbara vince mangiando tutti i cioccolatini rimanenti, oppure il numero di $F$ rimasto è pari, e allora Barbara vince lasciando ad Alberto gli ultimi 3 cioccolatini. Il caso in cui il primo e il terzultimo cioccolatino siano del tipo FF è analogo.

In conclusione, Barbara vince in tutti i casi in cui il primo e il terzultimo cioccolatino siano dello stesso tipo e gli ultimi due di tipo diverso. Poiché stiamo considerando solo il caso in cui il numero di cioccolatini dello stesso tipo del primo è pari, questo dà luogo a $2^{n-3}=2^{2k-2}$ possibilità.

Questo fornisce la formula ricorsiva
$$b_{k}=2b_{k-1}+2^{2k-2}$$
e quindi permette di calcolare in pochi passaggi $b_{7}=8320$, che è il numero cercato.