Newsgroup: it.hobby.enigmi
Titolo: Un telefono con infiniti tasti.

In un paese i telefoni hanno infiniti tasti, numerati 0,1,2,3,...
Per fare una telefonata bisogna dunque premere alcuni dei tasti numerati 
e quindi premere il tasto R per dare conferma.
In questo paese ci sono infinite case, numerate 1,2,3,4,5,... come
facciamo ad associare ad ogni casa un numero di telefono (ovvero una
sequenza di numeri) in modo che qualunque sequenza di tasti numerati
mi metta in contatto con una casa e che sequenze diverse mi diano case
diverse?
NB:
  le sequenze di tasti che compongono i numeri telefonici sono sequenze
finite... senno' non finirei mai di fare il numero! (inoltre il problema
non sarebbe risolubile)

...

E neanche la centrale saprebbe cosa fare. Il piccolo grande switch :-)
-- 
Alessandro

non sarebbe risolubile)
Non sono sicuro di aver capito bene il problema.
Mi pare che parlando di sequenze finite si intenda che e' noto il numero
max. di tasti che possono essere battuti in una sequenza.
Per semplicita' suppongo che non siano permessi gli zeri iniziali(come nei
normali telefoni)
Se e' cosi', posso ordinare le infinite sequenze possibili secondo i criteri
seguenti (in ordine di priorita'):
a) in base al valore max. contenuto nella sequenza; ossia per prime tutte le
sequenze formate solo dalle cifre zero ed uno, poi quelle formate da zero,
uno e due (con almeno una volta la cifre due) ecc.
b) in base alla disposizione delle cifre all'interno delle sequenze, viste
come numeri in una base opportuna (per es. nelle sequenze con valore max uno
numeri binari, in quelle con valore max. 2 numeri in base 3 ecc.)
Supponendo per esempio che il n. max. sia di 4 battute, l'ordinamento e' il
seguente (gli zeri a sinistra, NON significativi, sono messi solo per
facilita' di rappresentazione ma NON devono essere digitati):
0001,0010,0011,0100,0101,0110,0111,
1000,1001,1010,1011,1100,1101,1110,1111,
cioe' tutti i numeri binari fino a 4 cifre rappresentano le case da 1 a 15
(2^4-1)
poi passo ai numeri in base tre, escludendo quelli gia' considerati:
0002,0012,0020,0021,0022,0102,0112,0120,0121,.........2222
cioe' tutti i numeri in base 3 fino a quattro cifre, contenenti almeno una
volta la cifra 2, rappresentano le case da 16 (2^4) a 80 (3^4-1)
eccetera...
in questo modo ho stabilito una corrispondenza biunivoca tra le possibili
sequenze e i numeri delle case, anche se non e' agevole ne' immediato
passare dal numero alla sequenza o viceversa.
Magari ci sara' un modo piu' semplice, resto in attesa
ciao
paolo

 seguenti (in ordine di priorita'):
Si', per come l'avevi interpretato tu e' giusto... e direi che con poche
modifiche lo puoi adattare anche al caso che intendevo io, mettendo invece
i seguenti criteri di ordinamento:
1) ordino innanzitutto con la lunghezza delle sequenze
2) metto in ordine lessicografico
ottenendo quindi il seguente ordine:
0 - 1 - 2 - 3 - 4 - ... - 9 - 0,0 - 0,1 - 0,2 - ... - 0,9 - 1,0 -....
.... 9,9 - 0,0,0 - ....
Ma c'e' una soluzione piu' elegante che ti permette di calcolare in modo
semplice il numero di telefono di una casa e viceversa il numero di casa
sapendo il numero di telefono.
ciao,
	Em. 

 Em.
ciao
paolo

 Non mi sembra che funzioni.
Hai ragione! Allora si potrebbe enumerare in ordine lessicografico prima
tutte le sequenze lunghe non piu' di uno che contengono numeri fino all'1,
poi quelle lunghe non piu' di due (tranne le precedenti) che contengono
numeri fino al due, ecc, questa mi pare dovrebbe funzionare... si avrebbe
quindi:
0 - 1 - 0,0 - 0,1 - 0,2 - 1,0 - 1,1 - 1,2 - 2 - 2,0 - 2,1 - 2,2 - 0,0,0 -
0,0,1 - ....
Comunque la soluzione a cui avevo pensato la potete trovare qua sotto...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Sia p1=2, p2=3, p3=5, p4=7, ... la sequenza dei numeri primi.
Un numero n si scrive quindi in modo unico nella forma
	n= p1^a1 * p2^a2 * p3^a3 * ...
Dunque associo alla casa n il numero di telefono (a1,a2,a3,....).
Ad esempio la casa 84 avra' il numero 2,1,0,1
ciao,
	Em.

 Em.
ciao
paolo

         Em.
Però secondo me non funziona! Se il numero è 2^13*3^14 o se è
2^1*3^3*5^1*7^4 cosa succede???
Io avevo pensato di digitare il numero della casa... alla casa n associo
il numero n...tanto sono numerabili (...non so bene cosa sto
dicendo...stupidate?)
Ciao
Marco

...
|[...]
|>NB:
|>  le sequenze di tasti che compongono i numeri telefonici sono sequenze
|>finite... senno' non finirei mai di fare il numero! (inoltre il problema
|>non sarebbe risolubile)
|
|Non sono sicuro di aver capito bene il problema.
|Mi pare che parlando di sequenze finite si intenda che e' noto il numero
|max. di tasti che possono essere battuti in una sequenza.
Credo che ?manu* intenda: battuta comunque una sequenza di tasti non
infinita (che abbia sempre un ultimo numero), corrisponda una e una sola
casa e che ogni casa abbia una e una sola sua sequenza corrispondente...
insomma, la domanda sarebbe: e' numerabile una infinita' di infinita'
numerabili?
|Per semplicita' suppongo che non siano permessi gli zeri iniziali(come nei
|normali telefoni)
Io ho pensato al metodo diagonale del buon vecchio Cantor (si poteva
evitare?).
Numeriamo le possibili sequenze di k numeri.
Con k=1, la numerazione e' naturale.
0 -> 1° sequenza
1 -> 2° sequenza
2 -> 3° sequenza
...
con k>1, interviene Cantor...
          |  1°  |  2°  |  3°  |  ...
---------------------------------------
    1°    | *1°* | *2°* | *4°* | *7°*
-----------------/------/------/-------
    2°    | *3°* | *5°* | *8°* |  ...
-----------------/------/------/-------
    3°    | *6°* | *9°* |  ...
---------------------------------------
Nella colonna d'intestazione ci metto il 1°, 2°, etc. della sequenza gia'
numerata k-1; nella riga d'intestazione ci metto il 1°, 2°, etc. della
sequenza con k=1.
Nella casella (c°, r°) ci metto le sequenza formata dai k-1 numeri della
c°-esima sequenza con l'aggiunta del r°-esimo numero (che vale poi r-1).
Per esempio, con k=2:
         |  0  |  1  |  2  |  ...
---------------------------------------
    0    |  00 |  01 |  02 |  03
---------------/-----/-----/-------
    1    |  10 |  11 |  12 |  ...
---------------/-----/-----/-------
    2    |  20 |  21 |  22 |  ...
---------------/-----/-----/-----------
E adesso, diagonalizzando, numero le sequenze di due tasti.
00 -> 1°
01 -> 2°
10 -> 3°
02 -> 4°
e cosi' via...
con k=3:
         |  0  |  1  |  2  |  ...
---------------------------------------
   00    | 000 | 001 | 002 | 003
---------------/-----/-----/-------
   01    | 010 | 011 | 012 |  ...
---------------/-----/-----/-------
   10    | 100 | 101 | 102 |  ...
---------------/-----/-----/-----------
000 -> 1°
001 -> 2°
010 -> 3°
002 -> 4°
e cosi' via...
Adesso posso riempire la prima tabella mettendo nella prima riga le sequenze
di un numero, nella seconda quelle con due numeri... e con la solita
diagonalizzazione, le numero. Questa numerazione corrispondera' alla casa
che voglio chiamare.
|[...]
|in questo modo ho stabilito una corrispondenza biunivoca tra le possibili
|sequenze e i numeri delle case, anche se non e' agevole ne' immediato
|passare dal numero alla sequenza o viceversa.
Il metodo di Cantor non e' molto diverso da quello che hai fatto tu, solo
che vale per qualsiasi sequenza (anche con zeri iniziali).
|Magari ci sara' un modo piu' semplice, resto in attesa
Boh! in effetti non ho idea se sia possibile trovare una formula semplice
che faccia corrispondere le sequenze alle case... io ne ho trovata una
strapiena di sommatorie di sommatorie di sommatorie... assolutamente
impraticabile per me, ma forse per chi e' abituato ad avere a che fare con
un numero infinito di tasti del telefono la cosa e' banale!
Ciao ciao
Claudio

 2^1*3^3*5^1*7^4 cosa succede???
Attenzione!
Nel primo caso si digiteranno due tasti, il tredicesimo ed il
quattordicesimo, nel secondo 4: il primo, il terzo, ancora il primo ed
infine il quarto.
Il problema e' come battezzare i tasti dal decimo in poi, e' evidente che
anche usando un simbolo nuovo per ogni tasto qualsiasi alfabeto finito puo'
fare ben poco...
Ciao, Silv:o)

 solo).
Che dire? Hai ragione!..  Pero' se qualcuno riuscisse a trovare una forma
decente (e piu' corretta) di esposizione, forse non sarebbe male come
indovinello!
ciao,	Em.

ciao, Em.
ciao
paolo

 non sarebbe risolubile)
Lo diceva anche Cantor.
Non sono sicuro d'averlo capito. Ho visto una buona risposta basata sulla
scomposizione in numeri primi. Ho una proposta diversa, che occupa
meno spazio: metto tutte le case su di un segmento di lunghezza 1!
In altre parole do a ogni casa un numero razionale, tra 0 e 1,
rappresentabile
in base 10 con una stringa di lunghezza finita (arbitrariamente grande),
con al max n zeri, dove n e' la massima lunghezza di una sequenza.
Dato il numero di una casa, sostituite 0 con una virgola, aggiungete una R
in fondo ed ecco la sequenza da premere.
Es. numero .1012340560708 -> sequenza 1,1234,56,7,8,R
Se lo 0 e' un tasto valido, come pure valgono sequenze che iniziano con 0
(es, c'e' un tasto 1230 e un altro 0123), rappresento il numero in
base 11 e il vincolo diventa che non abbia piu' di n "A" (A rappresenta 10,
in base 11).
Poi le A diventano virgole etc.
Pero' il telefono con 'sta tastiera diventa ingombrante...
Ciao
Mauro Fiorentini

 [...]
Ok, in pratica stai dicendo che l'insieme delle case e quello dei numeri
di telefono hanno la stessa cardinalita'... e' una risposta corretta, solo
che non mi sai dire che numero di telefono ha la casa 4125 e che casa
risponde se chiami il 2,1,0,4.
Ciao!
Em. 

Ciao
?manu* wrote:

Togli lo 0, cosi' lavoriamo in base 10.
La casa 4125 non esiste: i numeri vanno da 0 a 1.
La casa 0.4125 ha numero 4125 (un tasto). La casa 0.41025 ha numero
41,25 (due tasti).
Se chiamo il 2,1,9,4, risponde la casa 0.2010904.
Se rimettiamo lo 0 bisogna lavorare in base 11, che e' appena piu' scomodo.
In alternativa, possiamo usare convenzioni piu' complesse, restando in
base 10. Es. 0 seguito da un altro 0 nel numero della casa rappresenta un
singolo 0 nel numero di telefono (non un tasto, parte del codice di un tasto),
mentre 0 seguito da altra cifra (da ignorare) rappresenta il separatore di
tasti.
In questo caso la casa 0.4125 ha numero 2125, mentre telefonando allo
2,1,0,4 risponde la casa 0.20X10X004. (Possiamo fissare X da 1 a 9,
arbitrariamente, ma una volta per tutte).
La numerazione delle case con i razionali ha il vantaggio che tra due numeri ne
posso
sempre inserire un altro, quando costruisco una casa nuova. Questa proprieta'
resta valida anche con le limitazioni che la mia codifica impone.
Lo svantaggio e' avere targhe dei numeri civici enormemente grandi.
Ho solo proposto un mapping su un sottoinsieme dei razionali.
Nota che si generalizza facilmente a citta' bi (tri-, n-) dimensionali, dando
due
numeri (razionali) per le coordinate e digitando alternativamente i tasti
dell'uno e dell'altro (serve un altro separatore per identificare la fine,
quando una
coordinata si indica con meno tasti dell'altra).
Continuo a non voler comprare il tuo telefono. Ho tasche finite e la tastiera
non ci entra :)
Ciao
Mauro Fiorentini