Monede de 3 şi 5 lei

Question

O problemă veche pe care o citez aproximativ " deţinînd numai monede de 3 şi 5 lei se poate plăti exact orice sumă întreagă mai mare decît 7" ? Dacă răspunsul este afirmativ, cum demonstraţi?

Prima jumătate a întrebării este cea de mai sus. A doua parte: se poate descoperi matematic o pereche de numere întregi (k, p) astfel încît orice număr natural n>7 să fie descris de n= 3k+5p ? Dacă există k şi partenerul p, aceste numere sînt unice?

Answer 1

Voi începe cu punctul 2 care conține punctul 1 ca un caz particular.

Cerința problemei este de a arăta că pentru orice număr n>7 există o pereche (k, p) întregi  care să satisfacă ecuația n=3k+5p. Voi nota Modulo x cu modx.

Din punct de vedere al divizibilității lui n cu 3 avem următoarele situații:

 

1. n=0 mod3 => 0+5p=0 mod3 => p de forma p=3m, m natural, sau

p=.....-12, -9, -6, -3, 0, 3, 6, 9, 12,.....

 

2. n=1 mod3 => 3k+5p=1 mod3 => 3k+5p-1=0 mod3 => 0+ 5p-1=0 mod3 =>

=> p=.... -10, -7, -4, -1, 2, 5, 8, 11,.......

 

3. n=2 mod3 => 3k+5p=2 mod3 =>0+ 5p-2=0 mod3 =>

=> p=....-11, -8, -5, -2, 1, 4, 7, 10,...... .

 

În oricare din aceste situații ne-am afla, pentru orice n dat putem alege un p dintr-unul din șirurile obținute, după care se determină simplu valoarea lui k. 

De exemplu, pentru n=1175 ne aflăm în cazul 3. Alegem p=10. 

Din 1175=3k+5*10 rezultă k=375, adică 1175=3*375+5*10

Dacă alegem p=19, din 1175=3k+5*19 rezultă k=360, adică 1175=3*360+5*19.

De aici se vede și că soluțiile nu sunt unice. Mai mult, având libertatea de a-l alege pe p dintr-un șir infinit de numere întregi, rezultă că există un număr infinit de soluții de tip (k, p) k și p întregi, care satisfac n=3k+5p pentru orice n, nu neapărat cu condiția n>7.

Pentru că problema cere perechile k și p întregi, voi lua un alt n arbitrar, n=2431, pentru alt exemplu.

Observăm că ne aflăm în cazul 2. Alegem p=-10, din 2431=3k+5*(-10) rezultă k=827, adică 2431=3*827-5*10. Este evident că și pentru această valoare a lui n există un număr infinit de perechi (k, p) întregi  care satisfac relația. 

Partea întâi a problemei este un caz particular pentru k și p naturale.

Comments

Felicitări şi daţi-mi voie să vă prezint şi ce-am gîndit eu cînd am inventat partea a 2-a  remarcînd că această problemă se poate generaliza într-un fel.

Pornind de la n=2*(k+2p) +(k+p), aproape fulgerător rezultă ca o primă soluţie;

n=par  => (k,p) = (-n/2, n/2)

n=impar => (k,p)= ((5-n)/2, (n-3)/2)

Pentru a arăta că pereche (k,p) nu este unică pornesc de la presupunerea că există (k1,p1), deci 3k+5p=3k1+5p1 => (k-k1) / (p1-p) = 5/3. Se remarcă că se poate scrie k1=k-5t şi p=p+3t, t număr întreg. Deci se demonstrează existenţa unei infinităţi de soluţii de forma :

n=par  => (k,p) = (-n/2 -5t, n/2+3t)

n=impar => (k,p)= ((5-n)/2  - 5t, (n-3)/2+3t), t orice număr întreg.

Probabil eram cu mintea la numărat monede (dolari) de am spus n>7. n poate fi orice număr întreg.

 

 

 

---

Da, e o analiză bună a situațiilor posibile în numere întregi. O exprimare condensată a  soluției generalizate este (k, p)=( (n-5p)/3, p ) unde, în funcție de n mod3, p este ales din unul din șirurile infinite pe care le-am obținut mai sus.

---

Diferenţa în abordarea problemei, dar esenţială, constă în faptul că avînd un număr n după formula mea perechea (k,p) se poate calcula numai în funcţie de n, deci nu trebuie un p ales. Rezultă un fel de simplitate şi uşurinţă. Cu prietenie....

 

---

Din punct de vedere al simplității abordările mi se par comparabile. Dumneavoastră îl calculați pe p iar eu îl aleg.

Pentru mine e mai simplu să aleg la întâmplare decăt să calculez.

Pe k îl calculăm amîndoi,

Dar puteți simplifica și mai mult formulele finale la care ați ajuns. Dacă tot sunt valabile pentru orice t întreg, faceți t=0.

Cu aceeași prietenie...

---

Intrînd pe acest site şi remarcînd că nu se încumetă nimeni să dea un răspuns la nişte întrebări puse de un user (hopa, tot eu le-am pus, ori sînt prea grele, ori prea uşoare sau neinteresante, habar nu am) şi dorind să fac mişcare apăsînd nişte taste pot să mă leg de t şi să vă spun că în comentariul meu, t nici nu exista la început, apoi l-am înfiinţat doar pentru a arăta existenţa infinităţii. Remarc că aveţi o pasiune pentru modulo.  

 

Answer 2

Daca gasim un procedeu care merge pentru orice numar inseamna ca am demonstrat ca se poate, nu?

Fie un numar oarecare N. Il impartim la 5 (cu rest) si obtinem sa zicem k' si restul r.

r poate fi 0,1,2,3,4

1. Daca r=0, atunci N=5*k' (deci k=k', p=0)

2. Daca r=1, atunci imprumutam un 5 ca sa obtinem 6 (care e 2*3) si facem k=k'-1 si p=2

3. Daca r=2, atunci imprumutam doi de 5, ca sa facem 12 (care 4*3) si deci k=k'-2, p=4

4. r=3, atunci k=k' si p=1

5. Daca r=4, imprumutam un 5 pentru a obtine 9 (3*3) si deci k=k'-1 si p=3

Astea sant toate cazurile.

Exemplu: N=47

N/5= 9 rest 2. Deci e cazul 3 (k=9-2=7; p=4)

47=7*5+4*3

 

Numerele k si q nu sant unice in general. Putem inlocui de exemplu 3 monezi de 5 lei cu 5 monezi de 3 lei. Doar in cazul numerelor destul de mici pentru a avea k<3 descompunerile pot fi unice.

Comments

Ideea e corectă dar ați inversat k și p din enunț la toate cele 5 cazuri analizate. De exemplu, în cazul N=47 (în enunț este n), pentru k=7 și p=4, adică valorile pe care le-ați găsit,  înlocuind în n=3k+5p ar rezulta că 47=41 (!).

E doar o greseală de notație dar crează dificultăți celor care vă citesc răspunsul. 

---

Asa e, ai dreptate. Am incurcat notatiile.