un pò di ....cinese

da **Valerio Capraro** » 07/04/2004, 16:13

Si abbiano X<200 oggetti tali che, disposti in file di 3, 5 e 7 ne avanzano rispettivamente 1,0,5; determinare il numero degli oggetti. Inoltre, assicuratisi che esso non è univocamente determinato, per ogni possibile soluzione, determinare una condizione di unicità.

ciao, ubermensch

da **karl** » 07/04/2004, 17:15

Ho trovato due soluzioni:
X=40
X=145.
Condizione di unicita' per la prima soluzione : 0<X<41
Condizione di unicita' per la seconda soluzione : 40<X<200
Tutto sbagliato? Vediamo.
karl.

da **Valerio Capraro** » 07/04/2004, 20:48

le soluzioni sono corrette. le condizioni di unicità un pò meno, nel senso che potrebbero essere generalizzate senza imporre una limitazione così "brusca" alla X nel seguente modo.

indico con = la relazione di congruenza

1) imporre, ad esempio, X = -4(mod11)
2) imporre, ad esempio, X = 2(mod11)

è ovvio che queste condizioni sono infinite, in quanto, la prima equivale, ad esempio, a X = 1(mod13) o a X = -5(mod15)...
d'altra parte, non limitano direttamente il dominio della X

ciao, ubermensch

p.s. ho praticamente cambiato tutte le condizioni perchè mi sono accorto di averle trascritte male; forse questo ha causato anche "l'incomprensione" da parte di Tony... scusate

Modificato da - ubermensch il 08/04/2004 11:54:29

da **karl** » 07/04/2004, 21:47

Una piccola giustificazione alla mia soluzione:
Il problema equivale alle tre congruenze:
(il segno "=" sta per congruente)
X=1 mod 3
X=0 mod 5
X=5 mod 7
La soluzione minima e' X=40 e poiche'
i numeri 3,5,7 sono primi tra loro ed il loro
m.c.m. e' 105,per il cosiddetto teorema cinese
dei resti,la soluzione generale risulta essere:
X=40+105*t con t in N
Dovendo essere X<200 le uniche due soluzioni sono:
X=40 per t=0 e X=145 per t=1.
karl.

Modificato da - karl il 07/04/2004 22:50:27

da **Valerio Capraro** » 07/04/2004, 23:10

una curiosità: esistono altri modi per risolvere questi problemi?

ne metto un altro che è carino perchè si può risolvere senza calcoli con un pò di ragionamento.. se ti va di pensarci..:

X<100
X=1(mod2)
X<img src=icon_smile_question.gif border=0 align=middle>0(mod3)
X=0(mod5)
X=1(mod7)

ciao, ubermensch

da **tony** » 08/04/2004, 00:14

scusa, Uebermensch, non capisco bene il tuo testo
<BLOCKQUOTE id=quote>*quote:<hr height=1 noshade id=quote>
...indico con = la relazione di congruenza

1) imporre, ad esempio, X = 4(mod11)
...
la prima equivale, ad esempio, a X = 6(mod13) o a X = 0(mod15)...
<hr height=1 noshade id=quote></BLOCKQUOTE id=quote>
intendi dire che se X = 4(mod11) è anche X = 0(mod15) ?

ciò vale certamente per il 15 [15 = 4(mod11) e anche 15 = 0(mod15)],
ma vale anche per il 26 ?
[direi: 26 = 4(mod11), ma 26 = 11(mod15)]
, etc.?

tony

*Edited by - tony on 08/04/2004 01:24:30

da **Valerio Capraro** » 08/04/2004, 10:51

forse mi sono spiegato male; nel primo caso voglio imporre che l'unico risultato accettabile sia 40; quindi impongo X=-4(mod11) infatti 40 verifica questa condizione, che però, non è verificata da 145; e analogamente negli altri casi...

p.s. mi accorgo ora di aver scritto per sbaglio X=4(mod11) e non X=-4(mod11).. ora correggo.

ciao, ubermensch

da **karl** » 08/04/2004, 16:12

Una soluzione elementare potrebbe essere questa:
(se ci limitiamo alle soluzioni positive,minori di 100)
X deve terminare con la cifra 0 o con 5 (terza
congruenza) ma dovendo essere dispari(prima congruenza)
puo' finire solo col 5.Fra questi X vanno esclusi quelli
divisibili per 3 (seconda congruenza),restano:
5,25,35,55,65,85,95
L'unico che soddisfa la quarta congruenza e' 85.
Una soluzione alternativa usa il T.C.R.
Operando come nel tuo primo esercizio,la soluzione
generale del sistema formato con le congruenze e':
X=15+70k
X non deve essere divisibile per 3 e cio' e' possibile
solo se k e',per esempio, del tipo k=3h+1 e quindi:
X=85+210h da cui (sempre considerando le sole sol.>0 e <100)
X=85.
Non conosco altri metodi a meno di non ridursi
a risolvere la cosa per tentativi ,che possono
variare da esercizio ad esercizio.
Qualcuno sa di altri modi?
karl.

Modificato da - karl il 08/04/2004 17:14:16

da **Valerio Capraro** » 08/04/2004, 16:26

bravo karl.. il ragionamento a cui mi riferivo era proprio il primo che hai fatto.

ciao

da **tony** » 09/04/2004, 02:02

concordo, karl, sul
<BLOCKQUOTE id=quote>*quote:<hr height=1 noshade id=quote>
...Non conosco altri metodi ...
<hr height=1 noshade id=quote></BLOCKQUOTE id=quote>
e riassumo dicendo che un metodo è il crivello, rapidissimo, anche se pesantemente limitato dalle costrizioni di memoria della macchina su cui lo poni.

tony

un pò di ....cinese

un pò di ....cinese

Chi c’è in linea