Newsgroup: it.hobby.enigmi
Titolo: Indovina il numero

Un mago ti chiede di pensare un numero tra 5 e 105.
Dividi poi il tuo numero per 3 e gli dici il resto.
Dividi il tuo numero per 5 e gli dici il resto.
Fai infine lo stesso per 7 e gli dici anche qui il resto.
Come fa il mago (senza ovviamente guardare la tabellina
dei resti) ad indovinare il tuo numero?
Nino


Scommetto che il mago si chiama Ling.
Tabel Ling
--
Ciao, Silv:o)


Io l'ho tratto dal capitolo XII del
Liber Abaci...
Ciao, Nino

 Liber Abaci...
Quindi non conosci il teorema cinese dei resti.
La formulazione originale del teorema, contenuta in un libro scritto 
nel III secolo dal matematico cinese Sun Tzu e successivamente 
ripubblicata in un libro del 1247 scritto da Qin Jiushao, è una 
affermazione riguardante le congruenze simultanee. Esattamente il 
sistema del tuo mago.
--
Ciao, Silv:o)


Sono andato a vederlo. Bello.
C'e' una cosa che non mi torna: perche' il problema pone come estremi
5 e 105?
Le soluzioni si ripetono con periodo 105, quindi sono uniche da 1 a
105, oppure da 5 a 109.
Perche' togliere quattro numeri?

 5 e 105?
3x5x7=105
E se lo capisco io... buona camicia a tutti!

 E se lo capisco io... buona camicia a tutti!
Non mi sono spiegato. Non e' 105 in se' che non capisco, e' perche'
abbinarlo a 5.
105 e' la lunghezza dell'intervallo disponibile. Possiamo usare
1..105, oppure 5..109 . L'importante e' che il numero scelto sia fra
105 numeri consecutivi.
Se pero' consideriamo l'intervallo 5..105, i numeri sono solo 101.
Vi risulta ci sia qualche ragione che mi sfugge, oppure e' solo un
fatto scenografico (5..105, con quei due 5 finali, distanti fra loro
100, suona meglio di un 1..105 o di un 5..109) ?



Se c'è qulcuno curioso ma tanto pigro da non risolvero da solo o da
gugolare veso i suggerimenti proposti, posto la soluzione che avevo
preparato giorni fa, così mi svuoto la cartella bozze ;-)
Siano r3, r5, r7 i tre resti
scegliamo tre numeri n3, n5, n7 così fatti:
- n3 ha resto 0 se diviso per 5 e 7 (quindi è multiplo di 35) e ha
resto r3 se diviso per 3
- n5 ha resto 0 se diviso per 3 e 7 (quindi è multiplo di 21) e ha
resto r5 se diviso per 5
- n7 ha resto 0 se diviso per 3 e 5 (quindi è multiplo di 15) e ha
resto r7 se diviso per 7
facciamo una tabellina dei resti nelle tre classi
         |  3  |  5  |  7  |
---------+-----+-----+-----+
      n3 |  r3 |  0  |  0  |
---------+-----+-----+-----+
      n5 |   0 | r5  |  0  |
---------+-----+-----+-----+
      n7 |   0 |  0  | r7  |
=========+=====+=====+=====+
n1+n2+n3 |  r3 | r5  | r7  |
---------+-----+-----+-----+
Facciamo un esempio. Siano 2,2,4 i tre resti.
n3: è multiplo di 35 e ha resto 2 modulo 3. Dato che 35 ha resto 2
modulo 7 direi che 35 va bene.
n5: è multiplo di 21 e ha resto 2 modulo 5. Dato che 21 ha resto 1
modulo 5 direi che 42 va bene.
n7: è multiplo di 15 e ha resto 4 modulo 7. Dato che 15 ha resto 1
modulo 7 direi che 60 va bene.
Allora 35+42+60=137 ha tutti e tre i resti giusti.
Ma se aggiungiamo o togliamo un multiplo qualsiasi di 3,5,7 (quindi un
multiplo del mcm 105) le cose non cambiano.
Allora 137 - 105 = 32 è l'unica soluzione nel range proposto
(legittimi i dubbi del bragozzi su questo punto).
Controlliamo:
32 = 10 * 3 + 2
32 =  6 * 5 + 2
32 =  4 * 7 + 4
--
Ciao, SIlv:o)

"Silvio Sergio"  ha scritto nel messaggio
On Jan 30, 11:22 am, "Nino" wrote:
..
facciamo una tabellina dei resti nelle tre classi
         |  3  |  5  |  7  |
---------+-----+-----+-----+
      n3 |  r3 |  0  |  0  |
---------+-----+-----+-----+
      n5 |   0 | r5  |  0  |
---------+-----+-----+-----+
      n7 |   0 |  0  | r7  |
=========+=====+=====+=====+
n1+n2+n3 |  r3 | r5  | r7  |
---------+-----+-----+-----+
..
Controlliamo:
32 = 10 * 3 + 2
32 =  6 * 5 + 2
32 =  4 * 7 + 4
--
Ciao, SIlv:o)
------------------
---->OK
E' forse ancora piů semplice (puoi fare i calcoli a mente,
senza bisogno della tabellina) se fai cosě:
(70*R3 + 21*R5 + 15*R7) - 105*k
Nel caso del tuo esempio R3=2   R5=2   R7=4
70*2 + 21*2 + 15*4 = 242
 242 - 2*105 = 32
Altro es.  R3=2  R5=0   R7=1
70*2 + 21*0 + 15*1 = 155
 155 - 105 = 50
ecc...
(Il Bragozzi ha ragione, si puň ovviamente scegliere da 1 a 105)
Ciao, Nino

 (70*R3 + 21*R5 + 15*R7) - 105*k
35*(2*R3) + 21*R5 + 15*R7
In pratica potremmo scrivere:
35*(1/35)*R3 + 21*(1/21)*R5 + 15*(1/15)*R7
e le frazioni valgono:
1/35=1/2=2 (mod 3)
1/21=1/1=1 (mod 5)
1/15=1/1=1 (mod 7)
Tu giustamente precalcoli queste frazioni, invece io mi vado a
guardare i resti per cercare il più piccolo numero multiplo ad esempio
di 35 con resto uguale a 2. Che non è 140, ma 35 stesso!
--
Ciao, Silv:o)

 70*2 + 21*2 + 15*4 = 242 = 32
[prima mi è partito un messaggio non riletto, sorry. pulisco e
rimando]
E' più o meno quello che fa il teorema del resto cinese.
Il secondo e terzo addendo coincidono con i miei,
3*7*R5 = 1*R5 = R5 (mod 5)   [21*2 = 2 nell'esempio]
3*5*R7 = 1*R7 = R7 (mod 7)   [15*4 = 4 nell'esempio]
Invece
5*7*R3 = 2*R3 <> R3 (mod 3)
Per mettere a posto le cose dobbiamo trovare un fattore da affiancare
al 2 per ottenere 1 (mod 3). In pratica dobbiamo calcolare 1/2 mod 3
Dato che 2*2 = 1 (mod 3) al fattore 3*5 giustamente affianchi un
fattore 2
5*7*2*R3 = 2*2*R3 = 1*R3 = R3 (mod 3)
In pratica potremmo scrivere:
S = 35*(1/35)*R3 + 21*(1/21)*R5 + 15*(1/15)*R7
e le frazioni valgono:
1/35=1/2=2 (mod 3)
1/21=1/1=1 (mod 5)
1/15=1/1=1 (mod 7)
S = 70 R3 + 21 R5 + 15 R7
Tu giustamente precalcoli il più piccolo multiplo di 35 che abbia
resto 1 (mod 3), e poi lo moltiplichi per il resto, quale che sia.
Invece io ho cercato direttamente il più piccolo multiplo di 35 con
resto uguale allo specifico resto del problema, 2.
--
Ciao, Silv:o)

"Silvio Sergio"  ha scritto nel messaggio
S = 70 R3 + 21 R5 + 15 R7
Tu giustamente precalcoli il più piccolo multiplo di 35 che abbia
resto 1 (mod 3), e poi lo moltiplichi per il resto, quale che sia.
Invece io ho cercato direttamente il più piccolo multiplo di 35 con
resto uguale allo specifico resto del problema, 2.
--
Ciao, Silv:o)
------------
----> OK Si era capito perfettamente anche nell'altro messaggio...
Effettivamente, senza il ragionamento che hai fatto, poteva sembrare
strano moltiplicare R3 per 70 (anzichè per 35, come pareva se si
guardavano gli altri fattori di R5 e R7...)
Ciao, Nino 

Nino ha scritto:

Ho appena letto tutto il thread perchè fino ad adesso ci ho rimuginato 
per conto mio. Senza scomodare il teorema cinese del resto che manco più 
mi ricordavo esistesse :) ho escogitato questo sistema che con un po' di 
pratica permette in pochi secondi di fare il calcolo a mente e di 
stupire le folle :)
Il presupposto è che dato un numero n, che avrà come resti R3 R5 e R7, 
il numero n+1 avrà come resti R3 +1, R5 +1 e R7 +1, dove per R3 
identifichiamo 3=0, e così 5=0 e 7=0 per R5 e R7.
Passo 1:
Sia n il numero incognito con resti R3 R5 R7.
Costruisco un "numero" formato dall'accostamento dei tre resti: R3R5R7 e 
lo tengo lì :)
Passo 2:
Parto dalla rappresentazione di 5 in questo sistema --> 205.
Quello che voglio fare adesso è calcolare n-5. Questo numero è pari al 
numero di "scatti" che devo far fare a 205 per arrivare alla 
rappresentazione di n. Per prima cosa sincronizzo l'ultima cifra, quella 
di R7, ovvero calcolo r7=(R7-5)MOD7 e aumento di questa quantità tutte 
le cifre, ottenendo quindi la rappresentazione 2+r7 0+r7 R7, 
ricordandoci che la prima cifra va calcolata MOD3 e la seconda MOD5.
Passo 3:
Adesso sincronizziamo la prima cifra *lasciando inalterata* la terza. Si 
verifica subito che c'è la simpatica proprietà che (x+7)MOD3 = 
(x+1)MOD3. E in effetti per lasciar inalterata la terza cifra bisogna 
avanzare di 7 in 7. Inoltre la variazione della seconda cifra ogni sette 
scatti segue l'andamento ciclico molto facile da memorizzare 0 2 4 1 3.
Questo significa che per ogni scatto che vogliamo far fare alla prima 
cifra ne avremo fatti in realtà sette e la seconda cifra varia secondo 
la tabellina indicata. Avremo così ottenuto una rappresentazione che 
coincide con quella cercata nella prima e nella terza posizione, manca 
la seconda. (Giuro che dopo faccio un esempio esplicativo).
Passo 4:
Sincronizzo anche la seconda cifra. Adesso dovrò muovermi in modo da non 
toccare più nè la prima nè la terza, il che significa muoversi di 21 
scatti alla volta. Ancora una volta i numeri sono così simpatici da 
dirci che (x+21)MOD5 = (x+1)MOD5, ovvero che avanzare di 21 scatti o di 
21 alla seconda cifra non cambia nulla :)
Passo 5:
Il numero cercato sarà allora il numero di scatti del passo 2 + 7*il 
numero di scatti del passo 3 + 21* il numero di scatti del passo 4 + 5.
Fine (pant pant...)
Esempio pratico: se i resti sono 2,3,6 procediamo così:
da 205 devo arrivare a 236.
Aumento di uno tutte le cifre (e ho un +1 per la ricerca del numero) 
ottenendo 016.
Aumento di due la prima cifra con un contributo di +14 ottenendo 206.
Aumento di 3 la seconda con un contributo di +63. A questo punto sono 
arrivato a 236 e mi fermo.
Il numero cercato sarà allora 1+14+63+5=83
Con un attimo di esercizio è semplicissimo :)
Marco
-- 
know whatahmean, nudge nudge, know whatahmean, say no more?