Bankomat wydający monety.

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
jbeibeadce
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 29 mar 2013, o 13:28
Płeć: Mężczyzna
Lokalizacja: LA
Podziękował: 4 razy

Bankomat wydający monety.

Post autor: jbeibeadce »

W pewnym bankomacie są tylko monety o wartościach a zł i b zł .

1.Udowodnij, że istnieje takie n, że dla dowolnej liczby naturalnej k>n , bankomat będzie w stanie wydać kwotę k zł.
2.Wypisz kolejne kroki algorytmu, którym może się posłużyć bankomat przy realizacji prośby klienta.

a = 7
b= 5

Dacie rade coś zdziałać w tym zadaniu?
Awatar użytkownika
pyzol
Użytkownik
Użytkownik
Posty: 4346
Rejestracja: 26 kwie 2010, o 11:39
Płeć: Mężczyzna
Lokalizacja: Nowa Ruda
Podziękował: 5 razy
Pomógł: 929 razy

Bankomat wydający monety.

Post autor: pyzol »

Za pomocą siódemek możemy utworzyć takie liczby:
\(\displaystyle{ 7,14,21,28,35}\)
Dodając jeszcze \(\displaystyle{ 5}\) otrzymamy liczby:
\(\displaystyle{ 12,19,26,33,40}\)
A więc tak na spokojnie dla \(\displaystyle{ n \ge 40}\) (\(\displaystyle{ n}\) może być mniejsze, ale mamy pokazać, że istnieje), otrzymamy wszystkie możliwe, ponieważ, jak widzisz otrzymaliśmy wszystkie możliwe cyfry jedności. Reszta to tylko dokładanie po \(\displaystyle{ 2\times 5}\).
jbeibeadce
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 29 mar 2013, o 13:28
Płeć: Mężczyzna
Lokalizacja: LA
Podziękował: 4 razy

Bankomat wydający monety.

Post autor: jbeibeadce »

A możesz to jeszcze rozpisać w przypadku
a=9 i b=7 bo nie czaje do końca
Awatar użytkownika
pyzol
Użytkownik
Użytkownik
Posty: 4346
Rejestracja: 26 kwie 2010, o 11:39
Płeć: Mężczyzna
Lokalizacja: Nowa Ruda
Podziękował: 5 razy
Pomógł: 929 razy

Bankomat wydający monety.

Post autor: pyzol »

Ogólnie opiera to się na zasadzie przystawania modulo.
Dowolna liczba naturalna przy dzieleniu przez 7 może dać resztę \(\displaystyle{ 0,1,2,3,4,5,6}\). Bądź też inaczej, każdą liczbę naturalną możemy zapisać jako \(\displaystyle{ 7k+m}\), gdzie \(\displaystyle{ m\in \left\{0,1,2,3,4,5,6 \right\}}\). Teraz weźmy wielokrotności liczby \(\displaystyle{ 9}\).
\(\displaystyle{ 9=7\cdot 1+2\\
18=7\cdot 2+4\\
27=7\cdot 3+6\\
...\\
54=7\cdot 7+5}\)

Widać, że biorąc wielokrotności liczby \(\displaystyle{ 9}\) możemy otrzymać dowolną resztę przy dzieleniu przez \(\displaystyle{ 7}\).
Dowolną liczbę \(\displaystyle{ n>54}\) możemy przedstawić w sposób:
\(\displaystyle{ 9k+7m,k=1,2,3,4,5,6}\)
Liczba \(\displaystyle{ 9k}\) odpowiada za resztę z dzielenia.
NO to tak napisałem, lepiej wytłumaczyć tego nie umiem.
Awatar użytkownika
Ponewor
Moderator
Moderator
Posty: 2218
Rejestracja: 30 sty 2012, o 21:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 70 razy
Pomógł: 297 razy

Bankomat wydający monety.

Post autor: Ponewor »

Rozwiązania pierwszego problemu należy szukać pod hasłem , ew. lub twierdzenie Sylvestera.
Najmniejsze takie \(\displaystyle{ n}\) to \(\displaystyle{ 23}\). Bankomat nie umie wydać jedynie \(\displaystyle{ 12}\) sum.
ODPOWIEDZ