Fie a un numar natural mai mic decat 300. Stiind ca impartit la 3 da restul 2, la 8 da restul 7 si la 11 da restul 10, sa se afle numarul.

M-ar interesa o rezolvare de clasa a VI-a, dar si o alternativa mai sofisticata, daca exista. Eu n-am in minte altceva decat lema chineza a resturilor.

Multumesc.

Inainte de Lema chinez?...e teorema impartirii cu rest si c.m.m.m.c.
ideea cheie in astfel de probleme e ca diferenta dintre impartitor si rest este constanta in toate cazurile.

Edit:Cred ca am citit intr-adevar o problema in care diferenta nu era constanta si care se rezolva cu Lema chineza.

Da...

Cred ca raspuns corect: 263, adica [3,8,11]-1, pentru a obtine rest maxim la cele trei impartiri.

Multumesc.

[Citat] Fie a un numar natural mai mic decat 300. Stiind ca impartit la 3 da restul 2, la 8 da restul 7 si la 11 da restul 10, sa se afle numarul. M-ar interesa o rezolvare de clasa a VI-a, dar si o alternativa mai sofisticata, daca exista. Eu n-am in minte altceva decat lema chineza a resturilor. Multumesc.

[Citat]

Da, corect, asa am gandit si eu dupa prima indicatie.

Multumesc.

Bun, sa rezolvam atunci o problema asemanatoare, unde nu avem coincidente care sa-i invete pe copii cu norocul si expedierea imediata, ci unde avem coincidente care sa-i deprinda cu munca...

(Nu stiu daca problema de mai sus face mai mult bine decat rau pentru un elev standard de a VI-a, in orice caz daca e prima de acest fel, trebuie sa o vada imediat si pe a doua, unde nu mai merge aceeasi afacere...)

Sa se gaseasca cel mai mic numar natural, care
- la impartirea cu rest la 10 da restul 3,
- la impartirea cu rest la 13 da (tot) restul 3,
- la impartirea cu rest la 12 da restul 11,
- la impartirea cu rest la 14 da (tot) restul 11.

In zilele noastre, trebuie sa-i invatam pe copii si cu computerul, asa ca solutia (cea mai simpla), ar fi de forma:
SAGE


O abordare normala ar fi cea prin care folosim coincidentele si cautam un numar care este de ambele forme:

M(130) + 3 si
M(84) + 11

deci (echivalent deoarece nu dam de probleme modulo cmmdc(130,84) = 2)

M(65) + 3 si
M(84) + 11

si de aici ar mai fi putin de lucru, asta doar ca sa-i invete ceva pe copii. (La scoala noi mai faceam asa ceva prin incercari! Si intotdeauna aveam repede success, deoarece intotdeauna solutiile erau usoare si "mic". Excelenta pregatire pentru formarea optimismului.)

Avem deci de rezolvat in ZZ (x,y intregi...)

si solutia algoritmica foloseste cel mai bine fractii continue, dar motivul pentru acest lucru se intelege cu de la sine putere daca scriem succesiv:

Putem acum alege "la intamplare" o solutie
y''=-3 si x''=1
deci y' = y''+3x'' = -3+3= 0
deci x' = x''+2y' = 1+0 = 1
deci y = y'+3x' = 0+3 = 3
deci x = x'+y = 1+3 = 4 .

Intr-adevar,
65 * 4 + 3 = 263 = 84 * 3 + 11 ...

Exemplul de mai sus arata cum se construieste "cu mana" inversa aplicatiei bijective (izomorfism de grupuri)

care trimite o clasa modulo MN in cele doua clase naturale modulo M, respectiv N. (De exemplu ZZ modul 14 se duce in ZZ modulo 7 trimitand pe 1 in 2, 2 in 2, ... 6 in 6, 7 in 0, 8 in 1, ...) Lema chineza a resturilor ne spune ca aplicatia de mai sus este un morfism injectiv de grupuri de acelasi ordin, deci si bijectiv. Pentru inversa nu avem insa din lema o "descriere algoritmica", ci doar una existentiala. (A se compara cu afirmatia "In Bucuresti exista un magazin unde au bagat papuci de dama rosii, ultimul ragnet, piele pe fata si inauntru, marimea 37, tocul solid, inalt de 5 cm..." Care este prima intrebare natruala, ca sa clarificam si noi ierarhia intereselor...)

[Citat] Care este prima intrebare natruala, ca sa clarificam si noi ierarhia intereselor...)

Va plac papucii rosii?
(Nu de alta,dar si in "Bocancii bunicului" aparea o pereche...)

In alta ordine de idei,multumesc pentru exemplu n-am avut timp nici sa caut nici sa fabric unul,dar nevoie aveam.