Il gioco della vita di Conway

[Studente Anonimo]

C'è una scacchiera infinita. La scacchiera è divisa da una linea orizzontale che si estende indefinitamente. Sopra la linea di separazione le celle della scacchiera devono restare vuote. Al di sotto potete posizionare quante pedine volete nel modo che preferite. Per muovere una pedina si esegue la seguente mossa, una pedina salta scavalcando una pedina adiacente all'interno di una cella vuota. La pedina che è stata scavalcata viene mangiata e sparisce dalla scacchiera mentre quella che salta può muoversi solamente orizzontalmente o verticalmente ma non diagonalmente. Evidentemente non ci possono essere due pedine per cella. Inoltre una pedina non può muoversi se non ne mangia un'altra.

L'obiettivo è quello di fare arrivare una pedina il più in alto possibile sopra la linea orizzontale di divisione.
Se fosse possibile raggiungere una certa riga sopra la linea di separazione dare una sequenza di mosse che lo permetta.
Se non fosse possibile raggiungere una certa riga dimostrarlo.

[Studente Anonimo]

Soluzione parziale

Costruttivamente si può mostrare (più o meno facilmente) che è possibile raggiungere la prima, la seconda, la terza e la quarta riga.
Bisogna dimostrare invece che non è possibile trovare un numero finito di mosse che permetta di raggiungere la quinta riga o una riga successiva.

[Studente Anonimo]

Mi ero dimenticato di aver posto questo indovinello, ecco la soluzione integrale:

Le mosse da fare per arrivare in quarta posizione lo lascio a voi. Invece qui di seguito la dimostrazione che non si può raggiungere la quinta riga. Sia $F_n$ l'n-esimo numero di fibonacci.
Con un po' di immaginazione possiamo assegnare un valore ad ogni casella della scacchiera:
Scusate ma non ho idea di come fare qui con LaTeX una tabella, quindi immaginate

|$F_{n}$ |$F_{n+1}$ | $F_{n+2}$ | $F_{n+1}$ | $F_{n}$|
-----------------------------------------
|$F_{n-1}$ |$F_{n}$ | $F_{n+1}$ | $F_{n}$ | $F_{n-1}$|
----------------------------------------- > questa è la linea di separazione, le pedine vengono messe sotto
|$F_{n-2}$ |$F_{n-1}$ | $F_{n}$ | $F_{n-1}$ | $F_{n-2}$|
-----------------------------------------
$|F_{n-3}$ |$F_{n-2}$ | $F_{n-1}$ | $F_{n-2}$ | $F_{n-3}$|
-----------------------------------------

Diremo che una pedina ha il valore corrispondente al valore della cella in cui è posizionata. Mentre il valore della scacchiera in un certo momento è uguale alla somma del valore di tutti le pedine. Le mosse possibili sono quelle di muoversi orizzontalmente oppure verticalmente. Abbiamo dunque che per la proprietà dei numeri di Fibonacci $F_{k-2} + F_{k-1} = F_k$
- Mi sposto orizzontalmente oppure verticalmente e il valore della scacchiera rimane invariato:
Una pedina con valore $F_{k-2}$ mangia una pedina con valore $F_{k-1}$ e giunge su una cella con valore $F_k$
$F_{k-2}+F_{k-1}=F_{k} = F_{k}$

- Mi sposto orizzontalmente oppure verticalmente e il valore della scacchiera diminuisce:
Una pedina con valore $F_{k}$ mangia una pedina con valore $F_{k-1}$ e giunge su una cella con valore $F_{k-2}$
$F_{k-1}+F_{k}=F_{k+1} > F_{k-2}$

- Mi sposto orizzontalmente in modo simmetrico rispetto all'asse centrale e il valore della scacchiera diminuisce:
Una pedina con valore $F_{k-1}$ mangia una pedina con valore $F_{k}$ e giunge su una cella con valore $F_{k-1}$
$F_{k-1}+F_{k}=F_{k+1} > F_{k-1}$

Abbiamo appena mostrato che il valore della scacchiera o rimane invariato oppure diminuisce, in altre parole non aumenta mai. Supponiamo per assurdo che una pedina riesca ad arrivare sulla quinta riga, significa che il valore della scacchiera $V_s \geq F_{n+5}$

Dimostriamo dunque che la somma dei valori del triangolo di Fibonacci centrato in $F_n$ è sempre minore di $F_{n+5}$, $\forall n \in \mathbb{N}$

Sia $S_0$ la somma dei valori della colonna centrale
$S_0 = \sum_{k=1}^{n} F_k = F_1 + F_2 + \ldots + F_{n-1} + F_n = F_3 + F_5 + \ldots + F_{n+1} $

Sommando e sottraendo uno alla sommatoria $S_0$ abbiamo che:
$S_0= S_0 + 1 - 1 = F_3+1 + F_5 + \ldots + F_{n+1} -1= F_4 + F_5 + \ldots + F_{n+1} -1 = F_n + F_{n+1} -1 = F_{n+2} -1 $

La somma $S_1$ dei valori della colonna adiacente a quella centrale ha valore:
$S_1 =\sum_{k=1}^{n-1} F_k = F_{n+1} -1 $

Cosi via per ogni colonna $S_i$
$ S_i = \sum_{k=1}^{n-i} F_k = F_{n+2-i} -1 $

Abbiamo dunque che la somma della configurazione iniziale (se ogni casella è occupata da una pedina):
$S= F_{n+2} -1 + 2 (F_{n+1} -1) + 2 (F_{n} -1) + \ldots + 2(F_3 -1) $

$= F_{n+2} + 2 F_{n+1} + 2 F_{n} + \ldots + 2F_3 - (2n+1)$

$=-(2n+1+2F_3) + \sum_{k=1}^{n+2}F_k + \sum_{k=1}^{n+1} F_k$

$=F_{n+4} + F_{n+3} - (2n+3+2F_3) = F_{n+5} - (2n+3+2F_3) < F_{n+5} $
Assurdo!

C.V.D.