Ammucchiata di pietre

[Marco]

All-Russian Tournament of Math Fights 2005 [pescato ravanando su Mathlink]...

Abbiamo due mucchi di pietre. Facciamo il seguente gioco: ad ogni passo scegliamo una pila con un numero pari di pietre, ne prendiamo la metà esatta, e mettiamo le pietre prese sull'altro mucchio.

Trovare tutte le coppie di valori iniziali del numero di pietre per cui il gioco non può continuare all'infinito.

[enomis_costa88]

Claim: è possibile continuare il gioco all'infinito sse $ a=2^{i+k}(2t+1) $ e $ b=2^{k}(2j+1) $ (o viceversa) con $ i\not=0 $

Sia $ 2^k $ la massima potenza di due tale che $ 2^k|MCD(a,b) $

Siano a,b il numero di pietre contenuto in ciascun mucchio inizialmente.
Siano $ a_i $ e $ b_i $ il numero di pietre contenuto in ciascun mucchio dopo i mosse.

Allora considerando a,b modulo $ 2^{k+1} $ posso avere:
$ (2^k,2^k);(0,2^k);(2^k,0) $
WLOG posso considerare solo i primi due casi.

Step 1: può essere possibile continuare il gioco all'infinito solo se $ a=2^{i+k}(2t+1) $ e $ b=2^{k}(2j+1) $ (o viceversa)

Sia $ a \equiv 2^k \equiv b (mod 2^{k+1}) $ allora in qualsiasi modo io applichi la mossa consentita ottengo $ a_1\equiv 2^{k-1}\equiv b_1 (mod 2^k) $ dove $ a_1 $ e $ b_1 $ sono le pile dopo avere applicato la mossa.
Se è possibile continuare all’infinito con $ a \equiv 2^k \equiv b (mod 2^{k+1}) $ allora lo sarà anche con $ a_1\equiv 2^{k-1}\equiv b_1 (mod 2^k) $ e quindi per discesa anche con $ a_i\equiv 1 \equiv b_i (mod 2) $.
Ma in quest’ultimo caso non posso proprio applicare la mossa consentita quindi non è possibile andare avanti all’infinito se $ a \equiv 2^k \equiv b (mod 2^{k+1}) $ per qualsiasi k.

Step 2: è possibile continuare il gioco all'infinito se $ a=2^{i+k}(2t+1) $ e $ b=2^{k}(2j+1) $ (o viceversa)

Sia $ a \equiv 0 (mod 2^{k+1}) $ e $ b \equiv 2^k (mod 2^{k+1}) $
La somma di $ a_i+b_i $ è invariante (perché non posso buttare via pietre)
$ a+b \equiv a_i+b_i \equiv 2^k (mod 2^{k+1}) $
quindi se $ a_i \equiv 2^k (mod 2^{k+1}) $ allora $ b_i \equiv 0 (mod 2^{k+1}) $ e viceversa.
Se divido per due la pila $ a \equiv 0 (mod 2^{k+1}) $ ottengo $ a_1 \equiv 0 $ oppure $ a_1 \equiv 2^k (mod 2^{k+1}) $.
Di conseguenza ottengo rispettivamente $ b_1 \equiv 2^k $ oppure $ b_1 \equiv 0 (mod 2^{k+1}) $ .
Considerando modulo $ 2^{k+1} $ posso quindi sempre passare da una situazione $ (a,b) (0,2^k) $ ad una $ (a_1,b_1) (0,2^k) $ oppure $ (a_1,b_1) (2^k,0) $ e reiterare il procedimento all’infinito.

Quindi le coppie di valori iniziali del numero di pietre per cui il gioco non può continuare all'infinito sono date da: $ 2^k(2c+1);2^k(2d+1) $.

[Marco]

Ok. Bravo, niente da dire.

Detto in forma semplice, il gioco continua all'infinito sse la potenza di 2 che divide esattamente a è diversa dalla potenza di 2 che divide esattamente b.

Come notazione, "divide esattamente" si scrive anche $ 2^k \| a $ (che vuol dire: $ 2^k | a, 2^{k+1} \nmid a $).

Solo una nota sul LaTeX:

invece di $ x \equiv y (mod 2^{k+1}) $ è meglio scrivere $ x \equiv y \pmod{2^{k+1}} $.