Consideriamo il triangolo di Tartaglia e sostituiamo ogni numero con $0$ o $\pm 1$ a seconda del resto nella divisione per $3$. Chiamiamo $x_n$ e $y_n$ i numeri definiti come nel testo del problema in funzione di $n$: essi indicano rispettivamente quanti $+1$ e quanti $-1$ ci sono nella riga $n+1$. Si verifica facilmente che
$x_0-y_0=2^0$
$x_1-y_1=2^1$
$x_2-y_2=2^0$
Prima di procedere raggruppiamo i numeri in triangoli di lato $3$ (su ogni lato ci sono tre numeri) rivolti verso l'alto (per essere più chiaro: partendo dalle righe con $3k$ elementi facciamo $k$ gruppi di $3$ e procedendo verso l'alto costruiamo $k$ triangoli) e a ciascuno di essi assegniamo il numero che si trova sulla sua "punta": possiamo osservare che:
1) Questo raggruppamento esclude dei numeri che formano triangoli di lato $2$ rivolti verso il basso: essi sono tutti pari a $0$ (quindi non ci interessano per la risoluzione del problema)
2) Se a due triangoli è assegnato lo stesso numero, essi sono identici
3) I triangoli si possono "sommare" come i singoli numeri (nel senso che se a ogni triangolo si sostituisce il numero a esso assegnato, ignorando quelli del punto
(1), si ottiene un nuovo triangolo di Tartaglia identico a quello iniziale)
A questo punto ragioniamo per induzione: supponiamo che per un certo $n$ si abbia $x_i-y_i=2^k$ con $k$ naturale $\forall 0 \le i \le 3n-1$ e dimostriamo che lo stesso vale per $n+1$, ovvero per le tre righe successive:
- la riga $3n+1$ contiene le "punte" dei triangoli di lato $3$ (tutti gli altri numeri sono nulli per la
(1)): per la
(3), "saltando" da una punta all'altra troviamo la stessa sequenza che si avrebbe leggendo normalmente la riga $n+1$, per cui $x_{3n}-y_{3n}=x_n-y_n=2^k$ per ipotesi induttiva;
- come abbiamo visto nella dimostrazione della
(2), i due numeri situati al "secondo piano" di un triangolo sono uguali a quello in cima, quindi $x_{3n+1}-y_{3n+1}=2x_{3n}-2y_{3n}=2 \cdot 2^k=2^{k+1}$;
- analogamente, alla base di un triangolo $"x"$ ci sono due $x$ e un $-x$: se in ognuna eliminiamo due numeri opposti la differenza rimane invariata e a ogni base rimane un solo numero, uguale a quello sulla cima del triangolo corrispondente, da cui ricaviamo $x_{3n+2}-y_{3n+2}=x_{3n}-y_{3n}=2^k$
Spero che sia corretta ma soprattutto comprensibile...
Ecco il problema della staffetta (non ne avevo di migliori e ho messo questo).