Ingegneria edile in base 2

[SkZ]

abbiamo (considerando solo collegamenti che non portano a stanze gia' visitate)
$ \displaystyle 2\rightarrow 3\rightarrow 7\rightarrow 5\rightarrow 13\rightarrow 29\rightarrow $ $ \displaystyle\left\{\begin{array}{l}31\rightarrow 23\rightarrow 19\rightarrow 17| \\ 61\rightarrow 53\rightarrow 37 \hookleftarrow \end{array}\right. $
dalla stanza 17 si puo' andare solo nella 19 e dalla stanza 37 si puo' andare solo nella 5 o 53.
quindi la 11 non si puo' raggiungere

[jim]

Attento!! Dalla stanza $ 37_{10}=100101_2 $ si puo' andare nella $ 101_{10}=1100101_2 $ applicando la ii)!!! E dalla 101 in poi l'albero inizia ad avere troppi rami per essere controllato a mano....

[SkZ]

ho fatto 37+64=111

sono contento del mio errore! Ora non e' preclusa la strada alla possibilita' che tutte le stanze siano raggiungibili

[jim]

UPPpo ancora quest'ultima volta, e metto la mia soluzione in bianco rimpicciolito, nel remoto caso in cui ci fosse ancora qualcuno interessato al problema...

I primi tre termini sono: 10,11,111. dal terzo termine in avanti, se non si torna indietro ad uno dei primi due, si nota questa proprietà:
Sia p un termine della successione (esclusi 10 e 11)
Sia p==A(p) (mod 3), A(p) appartenente a {1,2}
Sia N(p) la somma dei bit di p, calcolata in base 10
Allora ==> A(p)+N(p) e pari, per ogni p

Dimostrazione:
-La parità di N(p) cambia ad ogni passo (o aggiungao 1 o tolgo 1)
-La parità di A(p) cambia ad ogni passo: infatti, notiamo che 2^k==1 (mod 3) V 2^k==2 (mod 3) (se fosse ==0 (mod 3)sarebbe div per 3, e non si scriverebbe più 2^k...). Notiamo anche che applicare la i) o la ii) implica aggiungere o togliere 2^k
Allora passando da una stanza all'altra:
-La congruenza mod3 non può restare invariata: se così fosse, si avrebbe 2^k==0 (mod 3) impossibile,per ciò che s'è detto
-Non possiamo neppure trovare una stanza il cui numero è==0 (mod 3), poiche non sarebbe primo, contro l'ipotesi.

Abbiamo visto che le parità di A(p) e N(p) mutano simultaneamente ad ogni passo, il che implica che la loro somma non muta mai.
Poichè A(111)=1 e N(111)=3, si ha che 1+3=4 (pari), e in generale, A(p)+N(p) è pari, per ogni p della successione.

E' quindi facile ora affermare che 1011 non sarà raggiungibile, dal momento che A(1011)+N(1011)=2+3=5 (dispari). C.V.D