Quesito di logica

[Edo95]

Salve a tutti, mi chiedevo se poteste aiutarmi a risolvere questo quesito:

Dato un computer con 2 tasti viene richiesto di codificare una serie di numeri naturali, ciò è possibile, ad esempio, esprimendli in modo quantitativo con il primo tasto e separandoli con il secondo: 6=01111110 3=01110, quindi i numeri 6 e 3 corrispondono a 011111101110, 6 3 5 = 011111101110111110, ecc. Nel momento in cui si rompe un tasto devo poter esprimere i numeri con uno solo, come ci riesco? Non sono possibili espedienti di carattere fisico-meccanico, si tratta di una soluzione logica.

Grazie, ciao.

[vict85]

Dubito che sia possibile differenziare i numeri tra di loro. Soprattutto se non puoi usare metodi del tipo codice morse.

nel senso che l'unico codice possibile è 11111111111111111111 ora, in che modo questa successione sia divisa non si può sapere. Secondo me non ci riesci e penso sia anche dimostrabile.

[xXStephXx]

C'è un limite di grandezza a questi numeri? O possono essere arbitrariamente grandi? Perchè se esiste un limite allora conosco un metodo carino.. Però ora che ci penso, o il limite non è troppo alto, o escono numeri di lunghezza stratosferica.

[ant.py]

se non mi sbaglio, si può fare per qualsiasi numero.. mettiamoci d'accordo su un numero \( \displaystyle {l} \) prima di usare il computer, che è noto..

ora, preso un numero qualsiasi, facciamo così:
la prima cifra da sinistra, che chiamiamo \( \displaystyle {a}_{{0}} \), fa ripetere il simbolo (che è 0, per esempio) un numero pari a \( \displaystyle {\left({a}_{{0}}+{1}\right)}\cdot{\left({{l}}^{{0}}\right)} \)
il secondo, \( \displaystyle {a}_{{1}} \), fa ripetere il simbolo usato un numero pari a \( \displaystyle {\left({a}_{{1}}+{1}\right)}\cdot{\left({{l}}^{{1}}\right)} \) e così via..

per esempio, se \( \displaystyle {l}={15} \), il numero \( \displaystyle {11} \) lo possiamo trasformare così:

il primo numero da sinistra è \(\displaystyle 1 \), quindi lo \(\displaystyle 0 \) (il simbolo usato) si ripete per \(\displaystyle (1+1)*(15^0) = 2 \) volte
il secondo è ancora \( \displaystyle {1} \), quindi lo \(\displaystyle 0 \) si ripete per \(\displaystyle (1+1)*(15^1) = 30 \) volte

quindi:

\(\displaystyle 00000000000000000000000000000000 \) lunghezza = 32

si vede che ogni numero da via a stringhe di lunghezza diversa, fintantochè si ha \( \displaystyle {l}\gt{10} \); (per esempio se \( \displaystyle {l}={4} \), i numeri 01 e 40 danno via a stringhe di uguale lunghezza); quindi basta scegliere un numero \( \displaystyle {l} \) adeguato ed è fatta

[xXStephXx]

Però poi come si distingue uno \( \displaystyle {01010} \) da \( \displaystyle {0111111111110} \)?

[ant.py]

Però poi come si distingue uno \( \displaystyle {01010} \) da \( \displaystyle {0111111111110} \)?

non ho capito.. cosa sono i due numeri che hai postato? da codificare o già codificati? (in quest'ultimo caso, non ho capito perchè ci sono due simboli )

[xXStephXx]

Da codificare. Forse ho capito male il testo iniziale. Ma da quanto ho capito se tu hai il numero 11 da solo, e due numeri 1 accostati tra loro dovresti ottenere un risultato che permette di distinguere i due casi.
Cioè : \( \displaystyle {01010} \) rappresenta due numeri 1 accostati tra loro e \( \displaystyle {0111111111110} \) rappresenta il numero 11.

[ant.py]

io veramente avevo capito che non esiste il numero '11', cioè i numeri che posso rappresentare come un tutt'uno vanno da 0 a 9, e quelli che in base 10 si scrivono in due cifre vanno rappresentati come due numeri accostati.. boh aspettiamo l'OP

cmq posta anche il tuo modo, così copriamo tutte le possibilità

[xXStephXx]

Mi son reso conto che è scomodamente applicabile il mio metodo.. (E richiede dei limiti).. Ad esempio.. è possibile scrivere un numero in modo che modulo n restituisca un valore che indica il numero di numeri che compongono la serie.. Così sappiamo quanti sono i numeri da trovare.. Poi modulo (n+ un certo valore) restituisca il primo numero.. e così via incrementando ogni volta n secondo un criterio prestabilito.. Infatti i numeri con cui otteniamo i resti delle divisioni devono essere tutti primi tra loro, altrimenti c'è il rischio che non esiste alcun numero che soddisfi il sistema di congruenze..
Così ho pensato di prendere tutti i numeri primi a parire da un certo valore... Ad esempio.. Con i dovuti limiti...
prendendo il resto della divisione per 911 otteniamo quanti sono i numeri nella successione. Poi col resto della divisione per 919 prendiamo il primo numero della successione, poi col resto della divisione per 929 prendiamo il secondo numero della successione... (e così via, usando ogni volta il numero primo successivo)..

In questo modo per rappresentare una serie di numeri bisogna fare un sistema di congruenze trovando un numero che sia congro al numero di elementi modulo 911, congruo al primo numero della serie modulo 919, congro al secondo numero della serie modulo 929... (E questo se nessuno dei numeri supera 911,919,929 e così via....)
Quindi dai... mi rendo conto.. che sempre che si sia capito qualcosa di quello che ho scritto (non ho avuto tempo per formulare bene le frasi), il metodo è improponibile..

[Gaussman]

Dubito che sia possibile differenziare i numeri tra di loro. Soprattutto se non puoi usare metodi del tipo codice morse.

nel senso che l'unico codice possibile è 11111111111111111111 ora, in che modo questa successione sia divisa non si può sapere. Secondo me non ci riesci e penso sia anche dimostrabile.

si, non si può ed è dimostrabile.
A grandi linee il discorso è questo:
1) se A è l'insieme delle sequenze di simboli che dobbiamo poter rappresentare, allora \( \displaystyle {\left|{A}\right|}={\left|{\mathbb{{N}}}\right|}+{\left|{{\mathbb{{N}}}}^{{2}}\right|}+{\left|{{\mathbb{{N}}}}^{{3}}\right|}\ldots \) perchè dobbiamo contare tutte le k-uple di naturali. Si vede facilmente che l'insieme delle parti di \( \displaystyle {\mathbb{{N}}} \) è sottoinsieme di A, quindi A non è numerabile.
2) se B è l'insieme delle sequenze di simboli che possiamo utilizzare per rappresentare gli elementi in A, questo insieme è formato solo da sequenze di simboli uguali, di lunghezza a piacere n con n naturale, quindi \( \displaystyle {\left|{B}\right|}={\left|{\mathbb{{N}}}\right|} \).

Il problema diventa quindi trovare una funzione bigettiva da B ad A, ma questo è impossibile perchè B è numerabile mentre A non lo è