Ci sono 6 scatole, in fila, numerate da 1 a 6, ciascuna contenente un certo numero di monete (più tardi chiariremo quante). Sono disponibili queste 2 mosse:
A) Scegliere una delle prime 5 scatole, togliere una sua moneta (se ce l'ha) e aggiungerne 2 nella scatola successiva;
B) Scegliere una delle prime 4 scatole, togliere una sua monera (se ce l'ha) e scambiare il contenuto delle 2 scatole successive.
Punto 1 Mostrare che, utilizzando solo mosse del tipo A, per qualsiasi configurazione iniziale, sono possibili solo un numero finito di mosse. Punto 2 Mostrare che, utilizzando mosse di entrambi i tipi, per qualsiasi configurazione iniziale, sono possibili solo un numero finito di mosse.
Fissiamo ora come configurazione iniziale: una moneta per ogni scatola.
Punto 3 Mostrare che, con un'opportuna sequenza di mosse, si può ottenere la configurazione con tutte le scatole vuote eccetto l'ultima, che ne contiene 64. Punto 4 Mostrare che, con un'opportuna sequenza di mosse, si può ottenere la configurazione con tutte le scatole vuote eccetto l'ultima, che ne contiene almeno quanti sono gli atomi nell'universo (almeno $10^{81}$).
Qualcuno riesce a farne stare esattamente $2014^{2014^{2014}}$?
Chi offre di più?
P.S. visto che non è un problema del tutto sconosciuto, pregherei quelli che già l'hanno visto di non spoilerarlo subito.
Sono riuscito a fare i primi tre punti, intanto li posto.
Notazione Definisco $A_i$ la mossa A applicata scegliendo la scatola $i$, quindi ad esempio sula configurazione $(1,2,3,4,5,6)$ la mossa $A_3$ produce $(1,2,2,6,5,6)$. Analogamente chiamo $B_i$ la mossa B fatta scegliendo la scatola $i$. Chiamo $n_i$ il numero di monete nell' $i$-esima scatola.
Punto 1 Osservo che $n_1$ non può aumentare. Ora, ipotizzando che il numero di mosse possibili sia infinito, avremo una sequenza infinita di $A_i$. Visto che $A_1$ può apparire al massimo $n_1$ volte, da un certo punto in poi non apparirà mai (eventualmente dall'inizio). Altrimenti, ad ogni apparizione ne seguirebbe un'altra e quindi apparirebbe infinite volte.
Da questo momento in poi $n_2$ non può aumentare, e analogamente si arriverà ad un momento dopo il quale $A_2$ non appare più.
Ragionando così fino ad $A_5$, otteniamo che esiste un momento in cui nessuna mossa da $A_1$ ad $A_5$ viene effettuata, ossia che la sequenza si arresta, il che contraddice l'ipotesi che sia infinita.
Punto 2. Sperando di non essermi sbagliato, la dimostrazione del punto 2 è simile a quello precedente. Anche stavolta $n_1$ non può aumentare, mentre $n_2$ aumenta se si esegue $A_1$ o $B_1$ con $n_3 > n_2$. Come prima, si arriverà ad un punto dopo il quale né $A_1$ né $B_1$ vengono eseguite. Ora $n_2$ non può aumentare più e si procede come prima.
Punto 3 Osservo che eseguendo tutte e sole le mosse A possibili si ottengono sulla $i$-esima scatola $2^i - 1 $ monete, quindi sulla sesta se ne ottengono 63. Dopo aver provato invano a guadagnare quell'1 senza stravolgere tutto, vedo che posso passare dalla configurazione $(a,0,0)$ alla $(a-x, 2^x, 0)$ oppure, eseguendo altre A, alla $(a-x,0, 2^{x+1})$. Questo si ottiene eseguendo una A sulla prima (di queste tre) e poi alternamente spostando tutta la seconda sulla terza e eseguendo una B sulla prima.
Devo quindi arrivare alla configurazione $(0,0,0,5,0,0)$. Per ottenere lo 0 sull'ultima, posso solo ottenerlo sulla penultima e applicare $B_4$. Per ottenerlo sulla penultima posso o fare lo stesso (svuotare quella prima e applicare $B_3$), o spostare la quinta sulla sesta. Adesso, in maniera molto brutta, ho fatto qualche tentativo a logica col secondo metodo e ho ottenuto questa sequenza di mosse (e configurazioni):
$(1,1,1,1,1,1) \\
A_5 (1,1,1,1,0,3) \\
B_4 (1,1,1,0,3,0) \\
B_3 (1,1,0,3,0,0) \\
B_1 (0,0,1,3,0,0) \\
A_3 (0,0,0,5,0,0) $
Ora applico $(a,0,0) \rightarrow (0,0, 2^{a+1})$ ottenendo la configurazione finale voluta.
Sì, bene. Io per il primo punto avevo pensato più ad una classica "invariante", diciamo, qualcosa del tipo $Q=\sum n_i 3^i$ è una quantità che cala sempre. (Perché proprio 3?)
Ora sono convinto che con un po' di impegno riuscirai anche a fare il punto successivo!
Per il primo andrebbe anche $\sum n_i (2^i-1)$ però numerando le scatole al contrario e partendo da $i=0$. Diminuisce sempre di $1$. E si può dimostrare che non è possibile fare una sola mossa B) per ottere 64 palle nell'ultima scatola. (In quanto bisognerebbe fare una mossa B) che aumenta di 2 quella quantità ma non è possibile perchè può aumentare solo di un numero dispari facendo mosse B).
Non ho ancora avuto modo di provare ad ottimizzare la quantità ottenibile.
Però ad esempio ho visto che accumulando una certa quantità $k$ in quarta posizione, poi basta far oscillare un elemento tra la quinta e la sesta posizione (applicando mosse A e B in modo alternato) e quando la quarta colonna si svuota si riesce ad accumulare in quinta posizione un valore che è circa $2^k$
Dopodichè si rimanda quel valore in quarta posizione con una mossa B e si ripete il procedimento arrivando fino a ${2^2}^k$... e la cosa può andare avanti un bel po' di volte finchè si riesce ad invertire la quarta colonna con la quinta... Quindi non dovrebbero esserci problemi a superare $10^{81}$.
Azzarderei che per massimizzare la quantità ottenibile conviene ripetere quel procedimento di prima finchè si riesce a farlo senza esaurire la seconda colonna. Quando la seconda colonna rimane con solo un $1$ conviene mandare la quantità (già gigantisisma) ottenuta fino a quel punto in terza colonna.. (esaurendo la seconda) E a quel punto ripartire dall'inizio... Cioè mandare una certa quantità $k$ in quarta e far di nuovo oscillare un'unità tra la quinta e la sesta..
Alla fine verrà una torre gigante di 2? O ho fatto confusione e basta? xD
A ripensarci mi sa che non si ottimizza in quel modo E forse è più difficile del previsto, ma per arrivare a $10^{81}$ non dovrebbe servire troppa cura.
$(1,1,1,1,1,1)$
$(0,2,2,2,3,1)$
$(0,2,2,2,0,7)$
$(0,2,2,1,7,0)$
$(0,2,2,1,0,14)$
$(0,2,2,0,14,0)$
$(0,2,1,14,0,0)$
$(0,2,1,0,2^{14},0)$ Applicando mosse A e B in modo alternato sulla quarta e quinta scatola.
$(0,2,0,2^{14},0,0)$
$(0,2,0,0,{2^2}^{14},0)$
E infine basta portare tutto alla sesta scatola.
Ottimo, quindi sei riuscito a farne stare almeno $10^{81}$! E secondo me non sei neanche troppo distante dall'altro valore! Ma riuscirai ad ottenerlo esattamente?
Sicuramente si può superare di parecchio E penso di aver trovato un algoritmo per ottenere tutti i multipli di $4$ entro un certo limite.
L'idea in sostanza è che cerco di accumulare una certa quantità gigante in terza posizione, lasciando vuote sia la quarta sia la quinta sia la sesta.
Dopodichè scompongo ${2014}^{2014^{2014}}$ in binario come somma di potenze di $2$. Passo dopo passo lavorando sulle ultime 3 caselle cerco di ricomporre la scrittura binaria di quel numero nella sesta casella.
E ora è un po' lungo e scomodo spiegare formalmente come funziona
- Si parte accumulando una quantità gigante in terza posizione lasciando vuoto tutto il resto
- Sposto una certa quantità dalla terza alla quarta raddoppiandola.. La quantità che devo mettere in quarta posizione mi serve precisa in modo che al termine del procedimento si annulla totalmente. Questa quantità me la posso calcolare in anticipo, quindi so esattamente già da prima quanto devo spostare. Se la quantità necessaria era dispari mi basterà applicare una mossa B a vuoto sulla quarta casella.
- Adesso procedo così: sposto $1$ dalla quarta alla quinta che diventa $2$ e poi porto $4$ in sesta. Inverto quinta e sesta. Ripeto questo procedimento tante volte quanto è la distanza in termini di esponente tra la più grande potenza di 2 che compare scomponendo in binario ${2014}^{2014^{2014}}$ e la seconda potenza più grande. Quando raggiungo il valore della seconda potenza più grande, metto un altro $2$ nella quinta casella. E ripeto l'operazione: raddoppiando ogni volta ed aggiungendo $2$ se serve.
Il concetto è che così facendo sto ricomponendo ${2014}^{2014^{2014}}$ scritto come somma di potenze di $2$.
- Finito il passaggio di sopra (dove non si sarà capito niente ) avrò ${2014}^{2014^{2014}}$ in sesta casella, la quinta vuota e la quarta vuota (perchè mi ero calcolato già da prima la quantità giusta da mettere in quarta affinchè si svuotasse). La terza contiene ancora il numero enorme. Ma la svuoto applicando mosse B a vuoto sulla terza.
Per portare una quantità gigante a sufficienza in terza posizione (per poter applicare quell'algoritmo) posso procedere così:
$(1,1,1,1,1,1)$
$(1,1,1,0,0,7)$
$(1,1,0,2,0,7)$
$(1,1,0,1,7,0)$
$(1,1,0,0,9,0)$
$(1,0,2,0,9,0)$
$(1,0,1,9,0,0)$
$(1,0,1,0,2^9,0)$
$(1,0,0,2^9,0,0)$
$(1,0,0,0,2^{2^9},0)$
$(0,1,2,0,2^{2^9},0)$
$(0,1,1,2^{2^9},0,0)$
$(0,1,1,0,2^{2^{2^9}},0)$
$(0,1,0,2^{2^{2^9}},0,0)$
$(0,0,2^{2^{2^9}},0,0,0)$
Notare: è più che sufficiente, visto che se voglio ottenere $n$ in sesta posizione mi basta mettere in terza $2log(n)$.
Oh, molto bene! Finalmente ce l'abbiamo fatta!
Diciamo che potresti lavorare un po' di più sulla formalizzazione dei tuoi ragionamenti e a tal proposito ti consiglierei di usare più formule e meno parole. Ma al succo della dimostrazione ci siamo.
Passo ora a qualche commento.
1) per ottenere esattamente un certo valore $A$ multiplo di 4 in posizione 6, basta ottenere $A/4$ in posizione 4 e poi spostare con la mossa 1. Quindi il trucco è portare un sacco di monete in posizione 4. Tra l'altro questo ragionamento semplifica un poco il tuo sul dover portare una potenza di 2 alla volta.
2)riguardo alla torre di 2 che dicevi in qualche post fa, si riesce ad ottenere facilmente ripetendo l'utilizzo della sequenza di mosse che permette $(a,0,0)\to (0,2^a,0)$, su 4 caselle consecutive, in questo modo: $(a,0,0,0)\to (a-1,2,0,0)\to (a-1,0,2^2,0)\to (a-2,2^2,0,0)\to (a-3,2^{2^2},0,0)\to (0,2^{\dots^2},0,0)$ dove la torre di 2 è alta $a$.
3) il topic l'ho intitolato così perché era un problema in cui bisognava costruire la soluzione "a mano" facendo parecchie prove finché non si arrivava da qualche parte.
4) il problema era l'IMO 5 del 2010 ed è stato uno dei più tosti negli ultimi anni; anche se l'Italia in quel problema ha totalizzato parecchi punti rispetto le altre nazioni, tanto da essere la 5 in ordine secondo i punti realizzati in questo problema.
Si hai ragione Chissà perchè mi è venuto in mente di fare quella cosa strana... D: Trall'altro la torre gigante sulla 4 ce l'avevo, solo che non stavo considerando di ridurla facendo mosse B fino ad arrivare alla quantità desiderata.
E forse è più difficile del previsto, ma per arrivare a $10^{81}$ non dovrebbe servire troppa cura.