Disfida Matematica 2008

Soluzione del problema 21

21.

Il poker ineffabile.    Innanzitutto osserviamo che, se un'entità si sposta da un posto $A$ ad un posto adiacente $B$ e l'entità in $B$ si sposta in $C$, il posto adiacente a $B$ diverso da $A$, allora quella che si trova in $C$ dovrà spostarsi nel posto successivo $D$ e così via, dunque si otterrebbe la configurazione iniziale a meno di una rotazione. Bisogna quindi contare in quanti modi le entità possono scambiarsi a coppie, ovvero determinare il numero di modi per scegliere un certo numero di coppie disgiunte (almeno una); è facile vedere che in questo caso non si ottengono delle configurazioni uguali a meno di una rotazione.
Sia $x_n$ il numero di modi per scegliere un certo numero di coppie disgiunte (almeno una) in un "cerchio" di $n$ entità (ovvero nel caso del problema) e $y_n$ la stessa cosa però in una "striscia" di $n$ entità (senza quindi che le due agli estremi siano vicine tra loro). Allora considerando un cerchio di $n+1$ entità si può prenderne una e distinguere due casi:

• Questa entità non fa parte di nessuna coppia, e allora il numero di modi per scambiare a coppie le altre entità sarà $y_n$;
• Questa entità fa parte di una coppia, e allora ci sono ancora $y_{n-1}$ modi per scambiare le entità rimanenti, con l'aggiunta di un caso perché le altre entità possono anche non scambiarsi in quanto c'è già stato uno scambio, e moltiplicato per due perché l'entità che abbiamo considerato può far parte di una coppia in due modi diversi (insieme a quella alla sua destra oppure alla sua sinistra). In totale avremo $2(y_{n-1}+1)$ casi.

Quindi abbiamo trovato che $x_{n+1}=y_n+2(y_{n-1}+1)$.

Ora, considerando una striscia di $n+1$ entità, quella che si trova a uno dei due estremi può o non far parte di nessuna coppia, e quindi ci sono $y_n$ casi per scambiare le entità rimanenti, oppure può far parte di una coppia, e allora le entità rimanenti possono scambiarsi in $y_{n-1}$ modi, con l'aggiunta di uno poiché possono anche non scambiarsi. In totale ci sono quindi $y_n+y_{n-1}+1$ casi.

Quindi abbiamo trovato le seguenti due relazioni:

$$\left\{ \begin{array}{ll} x_{n+1}=y_n+2(y_{n-1}+1) \\ y_{n+1}=y_n+y_{n-1}+1 \end{array} \right.$$

A questo punto è sufficiente osservare che $y_2=1$, ovvero c'è un solo modo per scambiare almeno una coppia di entità se queste sono due, mentre $y_3=2$, perché se le tre entità sono in fila possono scambiarsi solo in due modi. Quindi $y_4=y_3+y_2+1=4$ e così via, calcolando attraverso la relazione $y_{n+1}=y_n+y_{n-1}+1$ tutti i valori della successione $y_i$ fino a $y_9$:

$$y_5 = 7$$

$$y_6 = 12$$

$$y_7 = 20$$

$$y_8 = 33$$

$$y_9 = 54$$

Ora, dato che $x_{n+1}=y_n+2(y_{n-1}+1)$, troviamo che $x_{10}=122$, che è la soluzione del problema. Quindi la risposta è .

È inoltre possibile scrivere per $x_n$ una formula chiusa, dimostrabile anche per induzione, utilizzando la teoria delle equazioni alle differenze:

$$x_n = \left( \frac{1+\sqrt{5}}{2} \right) ^n + \left( \frac{1-\sqrt{5}}{2} \right) ^n -1$$

che per $n=10$ dà proprio come risultato $122$.