Feladat: C.755 Korcsoport: 14-15 Nehézségi fok: átlagos
Megoldó(k):  Csóka Győző 
Füzet: 2005/február, 81 - 82. oldal  PDF file
Témakör(ök): Egészrész, törtrész függvények, C gyakorlat
Hivatkozás(ok):Feladatok: 2004/március: C.755

Hányféleképpen lehet 1000 Ft-ot felváltani kizárólag 1, 2 és 5 Ft-os érmék felhasználásával?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. Számoljuk össze azokat az eseteket, amikor egy- és kétforintosokat használunk a váltáskor, de ötforintost nem.
A csupa egyforintosra történő váltás egy lehetőséget jelent. Ezután váltsunk át két darab egyforintost egy kétforintosra, majd így tovább 4 darabot, 6 darabot stb. Ez összesen az előbbivel együtt [10002]+1=501 lehetőséget ad.
Legyen most ötforintos is a váltópénzek között. Jelölje n az egy- és kétforintos érmék értékeinek összegét és k az ötforintosok számát. Ekkor n=1000-5k, ahol 0k200. Az előbb láttuk, hogy k=0 esetén (vagyis amikor ötforintos nem szerepel) a váltások száma [10002]+1, általában pedig [1000-5k2]+1.
Írjuk fel k összes lehetséges értéke esetén a lehetséges váltások számát:

kn=1000-5ka lehetséges váltások száma:  [1000-5k2]+1   20001  19953  198106  1995498  01000501
Látható, hogy k=200-tól 1-ig, ha a szomszédos tagokat páronként összeadjuk, egy 100 tagú számtani sorozatot kapunk, amelynek első tagja a1=4, differenciája pedig d=10. Ha összeadjuk ezt a 100 tagot és még hozzáadjuk a k0-hoz tartozó értéket, akkor megkapjuk a lehetséges váltások számát:
k=0200([1000-5k2]+1)=S100+501=49901+501=50401,
ennyiféleképpen lehet 1000 Ft-ot egy-, két- és ötforintosokra váltani.