Quando si ferma l'algoritmo?

[ant.py]

Per ogni $n \in \mathbb N$, definiamo $a_0 = 0$, $$\begin{cases} a_{i+1} = 2a_i + 1 \pmod {2^n}, &\text{se non è mai apparso} \\ a_{i+1} = 2a_i \pmod {2^n},& \text{altrimenti}\end{cases}$$

Se sia $2a_i + 1 \pmod {2^n}$ che $2a_i \pmod {2^n}$ sono già nella sequenza, l'algoritmo si ferma.

Per esempio con $n=3$, otteniamo $$0, 1, 3, 7, 6, 5, 2, 4$$
Con $n=4$, si ha $$0, 1, 3, 7, 15, 14, 13, 11, 6, 12, 9, 2, 5, 10, 4, 8$$

Dimostrare che, per ogni $n$, ogni numero tra $0$ and $2^n - 1$ sarà generato

(Ovviamente ogni numero generato sarà distinto, bisogna dimostrare che l'algoritmo non si fermi prima di averli generati tutti)

Bonus per la dimostrazione più elegante

[Lev]

Testo nascosto:

Con $ + $ indico composizione di due stringhe.
Considerando la scrittura in base 2 dei numeri della successione, la regola equivale a: prendere l'ultima stringa, aggiungere una cifra 1 o 0 a destra e considerarne le ultime $ n $ cifre(equivale a prendere il resto modulo $ 2^n $). Si parte dalla stringa fatta di n zeri. Ad esempio con $ n=3: 000\rightarrow001\rightarrow011\rightarrow111\rightarrow110\rightarrow101\rightarrow010\rightarrow100 $.

1)Non ci possono essere tre numeri che terminano con le stesse $ n-1 $ cifre, perchè due avrebbero anche la prima cifra uguale e sarebbero uguali.

2)L'ultimo numero è formato da $ 1 $ seguito da $ n-1 $ zeri.
Infatti se l'algoritmo termina con una certa sequenza $ S $ di $ n-1 $ cifre vuol dire che $ S + 1 $ e $ S + 0 $ sono entrambe comparse nelle posizioni che chiamiamo $ a $ e $ b $, $ a<b $. Ma le stringhe nelle posizioni $ a-1 $ e $ b-1 $ terminano con la sequenza $ S $ che così compare tre volte nella successione. L'unica alternativa è una tra le stringhe in $ a $ e $ b $ non abbia precedente e quindi sia la prima. Quindi le ultime $ n-1 $ cifre sono zeri, preceduti da 1(perchè altrimenti si ripeterebbe la prima).

3)L'algoritmo produce tutti i risultati possibili:
Un numero di cifre $ a_{1}a_{2}...a_{n} $ è generato da un numero che termina per $ a_{1}a_{2}...a_{n-1} $.
Supponiamo che nella successione non compaia un certo numero $ N=a_{1}a_{2}...a_{n-1}a_{n} $. Allora c'è al massimo un numero che comincia per $ a_{2}...a_{n} $(quello eventualmente generato da $ \bar{a_{1}}a_{2}...a_{n} $) e quindi si tratta del numero $ a_{2}...a_{n} + 1 $. Quindi se non compare $ a_{1}a_{2}...a_{n-1}a_{n} $ non compare $ a_{2}...a_{n} + 0 $. Ripetendo il ragionamento arriviamo a dire che non compare il numero $ a_{i}...a{n} + (i-1 \: zeri) $, dove $ a_{i} $ è l'ultima cifra 1 di $ N $: quindi non compare il numero 1 seguito da $ n-1 $ zeri. Questa contraddizione al punto 2 permette di concludere che tutte le sequenze possibili sono presenti.

[ant.py]

Molto bello! Ottimo lavoro

L'avevo dimostrato in modo molto simile in effetti, con le sequenze di numeri binari.

Avevo postato questo problema su math.stackexchange, se ti va di scrivere la tua risposta li! (se sei registrato)

http://math.stackexchange.com/questions ... efore-time