Quando si ferma l'algoritmo?

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
ant.py
Messaggi: 140
Iscritto il: 18 set 2011, 11:36

Quando si ferma l'algoritmo?

Messaggio da ant.py » 15 nov 2014, 00:31

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 :D
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "

Lev
Messaggi: 8
Iscritto il: 21 ott 2014, 21:10

Re: Quando si ferma l'algoritmo?

Messaggio da Lev » 17 nov 2014, 17:56

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
Messaggi: 140
Iscritto il: 18 set 2011, 11:36

Re: Quando si ferma l'algoritmo?

Messaggio da ant.py » 18 nov 2014, 16:28

Molto bello! Ottimo lavoro :D

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
Anti-intellectualism has been a constant thread winding its way through our political and cultural life. Nurtured by the false notion that democracy means that "My ignorance is just as good as your knowledge. "

Rispondi