Problema carino!
Lo faccio prima nel caso $MCD(x,y,z)=1$. Mostro che posso arrivare ad avere $x+y+z$ mucchietti da un sassolino. Mostro per induzione che dati $n$ mucchietti c'è sempre una sequenza di mosse che me ne fa fare $n+1$.
Con 3 mucchietti faccio il caso base. Se ce n'è uno pari lo divido in due e ottengo 4 mucchietti e fine. Se sono tutti dispari faccio questo giochetto: ne unisco due e poi divido il mucchio totale in altri due mucchi. In poche parole $(x,y,z) \Rightarrow (\dfrac{x+y}{2},\dfrac{x+y}{2},z)$ [Edit: Attenzione! Qui bisogna controllare delle ipotesi che non sempre sono verificate e che rendono sbagliato questo procedimento. Vedi i messaggi più in basso]. Se ora ce n'è uno pari lo divido in due e ottengo 4 mucchietti e fine. Altrimenti rifaccio il giochetto di prima. Continuando a fare il giochetto, vorrei che ad un certo punto, quando divido in due, un mucchietto ottenuto fosse pari. Suppongo per assurdo che non sia così e che possa fare il gioco all'infinito ottenendo sempre interi dispari. In realtà così non è perché col crescere di $n$ quei termini "si avvicinano sempre di più" sfiorandolo $\dfrac{x+y+z}{3}$, facendo sì che sia impossibile che quei termini rimangano sempre interi (posso scrivere più formalmente questa parte, ma l'idea è che scegliendo $n$ opportunamente grande quei numeri vengono schiacciati su $\dfrac{x+y+z}{3}$ e quindi non possono essere interi). Dunque dopo un certo numero di volte che è stato fatto questo gioco, si otterranno due mucchietti pari e quindi dividendo in due si ottengono 4 mucchietti e fine.
Per il passo induttivo se fra gli $n$ ce n'è uno pari splitto e ce ne ho $n+1$. Altrimenti se sono tutti dispari ne prendo $3$ e faccio il gioco di prima.
In questa maniera riesco a fare sempre più mucchietti, fino al massimo possibile che è x+y+z. La somma, infatti, è invariante facendo le mosse e quindi rimane costante. Inoltre non può esistere un mucchietto che ha 0 sassi dunque il massimo è x+y+z che si riesce a raggiungere, finendo con x+y+z mucchietti di 1.
Nel caso $MCD(x,y,z) = d \neq 1$, col procedimento di prima riesco a finire con $\dfrac{x+y+z}{d}$ mucchietti da $d$ ciascuno.
Per il caso generale (con $(a_1,...,a_n)=1$) basta ordinare $a_1\leqa_2\leq...\leqa_n$. Poi si prendono gli ultimi 3 e si riducono a $a_{n-2}+a_{n-1}+a_{n}$ uni. Alcuni di questi si possono aggiungere a $a_{n-3}$ per raggiungere la potenza di due più vicina e poi quella potenza di due si può smembrare facendola diventare tutti 1...e così via si riesce ad avvere tutti 1.
Questo è possibile perché $a_{n-3}=2^k+s$ con $0\leq s\leq2^k-1$ e voglio mostrare che $a_{n-2}+a_{n-1}+a_n \geq 2^k-s$. Questo è vero perché $a_{n-2}+a_{n-1}+a_n > a_{n-2} \geq a_{n-3} =2^k+s \geq 2^k-s$. Nel caso $(a_1,...,a_n)\neq 1$ è identico.
Spero sia chiaro e giusto
