Quesito di logica
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.
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.
Risposte
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.
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.
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.
Però ora che ci penso, o il limite non è troppo alto, o escono numeri di lunghezza stratosferica.
se non mi sbaglio, si può fare per qualsiasi numero.. mettiamoci d'accordo su un numero $l$ prima di usare il computer, che è noto..
ora, preso un numero qualsiasi, facciamo così:
la prima cifra da sinistra, che chiamiamo $a_0$, fa ripetere il simbolo (che è 0, per esempio) un numero pari a $(a_0 + 1) * (l^0)$
il secondo, $a_1$, fa ripetere il simbolo usato un numero pari a $(a_1 + 1) * (l^1)$ e così via..
per esempio, se $l = 15$, il numero $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 $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 $l > 10$; (per esempio se $l = 4$, i numeri 01 e 40 danno via a stringhe di uguale lunghezza); quindi basta scegliere un numero $l$ adeguato ed è fatta
ora, preso un numero qualsiasi, facciamo così:
la prima cifra da sinistra, che chiamiamo $a_0$, fa ripetere il simbolo (che è 0, per esempio) un numero pari a $(a_0 + 1) * (l^0)$
il secondo, $a_1$, fa ripetere il simbolo usato un numero pari a $(a_1 + 1) * (l^1)$ e così via..
per esempio, se $l = 15$, il numero $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 $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 $l > 10$; (per esempio se $l = 4$, i numeri 01 e 40 danno via a stringhe di uguale lunghezza); quindi basta scegliere un numero $l$ adeguato ed è fatta
Però poi come si distingue uno $01010$ da $0111111111110$?
"xXStephXx":
Però poi come si distingue uno $01010$ da $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
)
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è : $01010$ rappresenta due numeri 1 accostati tra loro e $0111111111110$ rappresenta il numero 11.
Cioè : $01010$ rappresenta due numeri 1 accostati tra loro e $0111111111110$ rappresenta il numero 11.
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à
cmq posta anche il tuo modo, così copriamo tutte le possibilità
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..
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..
"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.
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 $|A|=|\mathbb N|+|\mathbb N^2|+|\mathbb N^3|...$ perchè dobbiamo contare tutte le k-uple di naturali. Si vede facilmente che l'insieme delle parti di $\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 $|B|=|\mathbb N|$.
Il problema diventa quindi trovare una funzione bigettiva da B ad A, ma questo è impossibile perchè B è numerabile mentre A non lo è
Ma secondo me non è da risolvere in modo prettamente matematico.. Forse ci può stare anche un accordo sulla strategia da prendere per decodificarlo.. In teoria se ci fossero dei limiti sia come numero di elementi che come grandezza degli interi, il sistema di congruenze potrebbe andare... (anche se verrebbero numeri stratosfericamente alti).
"xXStephXx":
Ma secondo me non è da risolvere in modo prettamente matematico.. Forse ci può stare anche un accordo sulla strategia da prendere per decodificarlo.. In teoria se ci fossero dei limiti sia come numero di elementi che come grandezza degli interi, il sistema di congruenze potrebbe andare... (anche se verrebbero numeri stratosfericamente alti).
scusa cosa significa prettamente matematico? Il problema è "si può con un solo tasto codificare univocamente sequenze di naturali? E se si, come si fa? (posto cosi non mi pare ci siano limitazioni di sorta...)" e la risposta con annessa dimostrazione è "no, non si può"
Nel senso che pensavo potesse esserci qualche trucchetto che faccia uso più che altro del "pensiero laterale". Poi vabbè, sicuramente hai ragione tu
"Gaussman":
1) se A è l'insieme delle sequenze di simboli che dobbiamo poter rappresentare, allora $|A|=|\mathbb N|+|\mathbb N^2|+|\mathbb N^3|...$ perchè dobbiamo contare tutte le k-uple di naturali.
E però...
"Edo95":
... viene richiesto di codificare una serie di numeri naturali ...
Da quanto ho capito lui ha contato il caso in cui la serie ha un solo numero (e quindi ci sono \(\displaystyle \mathbb{N} \) possibilità), il caso in cui la serie ha due numeri (quindi \(\displaystyle \mathbb{N}^2 \) possibilità) e così via.. fino all'infinito.
Non è giusto quello che ha scritto? La cosa che non mi è chiara è se l'autore volesse una soluzione di questo tipo, oppure esiste qualcosa di impensabile per ovviare a ciò.
Non è giusto quello che ha scritto? La cosa che non mi è chiara è se l'autore volesse una soluzione di questo tipo, oppure esiste qualcosa di impensabile per ovviare a ciò.
Intendevo solo questo: non è detto che i numeri da rappresentare siano infiniti, non è detto la serie debba essere arbitrariamente numerosa.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo