Ingegneria edile in base 2

[jim]

Preso dall'ultimo numero di RudiMathematici:

Si vogliono collegare delle stanze in una casa con questo sistema:
Tutte le stanze sono numerate con numeri primi in base $ 2 $

L'ingresso è la stanza $ 10_2 $ (10 in base 2, cioè 2 in base 10).
Una stanza è collegata ad un'altra se, preso il numero della prima stanza (che è primo), potete applicare una delle due regole seguenti ottenendo un numero primo:
i) Cambare uno(e uno solo) dei bit del numero
ii) Aggiungere un $ 1 $ davanti al numero

Attenzione che dovete sempre lavorare in base $ 2 $ e con numeri primi.

Partendo dall'ingresso, sarà possibile raggiungere la stanza $ 11_{10} $ (11 in base 10)?

[SkZ]

le stanze sono uno dopo l'altra?
-> [10],[11],[101],[111],[1011],[1101],....
se ho ben capito
[10]->[11] si puo' per la prima regola
[11]->[101] per la prima e seconda regola
[101]->[111] per la prima e seconda regola
[111]->[1011] per la prima regola
[1011]->[1101] non puoi

[jim]

No, forse non mi sono spiegato bene: le stanze non sono una dopo l'altra, semplicemente parti dalla prima stanza contrassegnata da 10, e poi, applicando una (e solo una) delle due regole, vai in un'altra stanza contrassegnata dal numero che trovi: questa stanza è accettabile (cioè esiste) solo se il numero che trovi è primo. Questo comporta eventualmente che da una stanza sia possibile raggiungere più di una stanza successiva (ad esempio: dalla 11101 puoi andare sia nella 11111 che nella 111101); quello che chiede il problema è se esiste un "percorso" che dalla 10 ti porta nella 11(base 10), cioè nella 1011(base 2).

[SkZ]

non e' possibile perche' 1011:
i) non si puo' ottenere da un numero primo combiando uno dei sui bit
ii)non si puo' ottenere aggiungendo ad un numero primo la minima potenza di 2 maggiore di quel numero (tali numeri hanno i due bit piu' "alti" accesi, ovviamente)

PS: casa fastidiosa: puoi entrare ma non uscire. Da 10 a 11 si puo passare in un senso e nell'altro, da 11 a 111 solo in un senso.

[jim]

Mhmm, attento, SkZ! 1011 si può ottenere togliendo un bit davanti al numero (cioè trasformando un 1 in uno 0, ossia applicando la i)).
Ad esempio, posso ottenere 1011 da 101011 cambiando il primo 1 in 0, quindi
101011 --> 001011=1011, e così via, per qualsiasi numero primo del tipo 10...01011.

PS: casa fastidiosa: puoi entrare ma non uscire. Da 10 a 11 si puo passare in un senso e nell'altro, da 11 a 111 solo in un senso.

Anche questo non è vero: se cambi il primo 1 di 111 ottieni 011=11.

[SkZ]

ritenevo che non fosse cosi', senno la seconda operazione e' gia' contemplata dalla prima:
se $ ~011\equiv 11 \Rightarrow 11\equiv 011 \equiv 0011 $
Se uno zero iniziale si puo' ignorare allora se ne possono ignorare infiniti!
quindi
10<->11
11<->111, 1011
finito

[jim]

Ok... in sostanza dipende da una scelta: sia $ a_2 $ un numero scritto in base 2, allora pui porre:
Assioma 1: $ 0a_2=a_2 ,\forall a \in N $
oppure:
Assioma 2: $ 0a_2 $ e` una scrittura senza senso.

a seconda di quale dei due scegli, ottieni risultati diversi.

[jim]

Ma rendiamo il problema più interessante....: Diciamo che
$ 0...0a $ ha senso ed è $ 0...0a=a $
Quindi il ragionamento che si è fatto prima sull'impossibilità di avere $ 1011 $ non regge più, perchè potremmo avere $ 10...01011 $ che per la $ i) $ diventa $ 1011 $.
Ma poniamo poi un altro vincolo:
dato $ 0...0a $, non possiamo usare la $ ii) $, nè la $ i) $ sugli zeri davanti ad $ a $: questo vuol dire che non potremo più trovare $ 1011 $ come prima, perchè il passaggio $ 011 \rightarrow 1011 $ non è lecito, così come non sarà lecito $ 000011 \rightarrow 001011 $
In sostanza, gli zeri davanti non fanno perdere di senso la scrittura, ma non possiamo manipolarli come le altre cifre.

Con queste ulteriori condizioni, è o non è raggiungibile la stanza $ 1011 $?

[O.T.]
Cennnntooooooooooooo!!!!!!!!!

[SkZ]

Diciamo che
$ 0...0a $ ha senso ed è $ 0...0a=a $

allora ii) e' gia inclusa in i)

[jim]

Non capisco cosa intendi dire... Sono chiare le nuove regole?

[SkZ]

intendo dire che
se $ ~ a\equiv 0...0a $
la regola ii)

a->1a

e' pari a all'uso della regola i)

0a->1a

[jim]

intendo dire che
se $ ~ a\equiv 0...0a $
la regola ii)

a->1a

e' pari a all'uso della regola i)

0a->1a

Si'. Se vuoi, puoi considerare la regola ii) un caso particolare della regola i). Quello che voglio dire, e che e' il fulcro del problema, e' che non e' lecito un passaggio del tipo:
a-->0...0a-->10...0a,
nonostante sia il numero 0...0a=a : quest'ultima affermazione indica che e' invece lecito un passaggio del tipo:
10...0a-->00...0a-->a

Garantisco che il problema ha una soluzione molto carina e breve.

[HumanTorch]

$ 10\to 11=0011\to 1011 $, o no?

[jim]

$ 10\to 11=0011\to 1011 $, o no?

No, come ho detto nei messaggi precedenti: se hai 11 non lo puoi sostituire con la scrittura 0...011, mentre puoi fare il contrario: se hai ottenuto 0...011 da 10...011, allora a 0...011 puoi sostituire 11. Ok?

[jim]

UPPP!!!!!
Niente di niente? Dai che c'è solo un invariantino-ino-ino da scovare ....
Se invece non è chiaro il testo ditelo, che provo a rispiegarlo.