Problem C. 1050. (November 2010)

C. 1050. Currently there are six different kinds of banknotes in Hungary: 500, 1000, 2000, 5000, 10000 and 20000 forint notes. How many different sums of money can be paid with three notes?

(5 pont)

Deadline expired on December 10, 2010.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Számoljuk össze a kifizethető összegek számát a szerint, hogy hány darab 500-assal fizettünk. Ha pontosan egy vagy mindhárom bankjegy 500Ft-os, akkor az összeg nem osztható 1000-rel, így a többi esetben ilyen összegeket biztosan nem kapunk. Három darab 500-assal 1500Ft-t tudunk kifizetni, és ha a két bankjegy nem 500-as, akkor az összeg biztosan nagyobb. Nézzük, milyen összegeket állíthatunk elő kettő, nem 500-as bankjegy segítségével: \(\displaystyle \binom 52 +5=15\) pár lehetséges, melyek mind különböző összeget adnak.

Ha pontosan két 500-ast használunk, akkor öt különböző összeget tudunk kifizetni az öt különböző harmadik bankjegy választása szerint (2000, 3000, 6000, 11000 és 21000).

Ha a három bankjegy mindegyike legalább 1000Ft-os, akkor \(\displaystyle \binom 53 + 2\cdot \binom 52 + 5 = 35\) összeget tudunk képezni. Ugyanakkor az előző pontban kapott összegek mindegyikéta 2000 kivételével most is megkaptuk. Másrészről ezen esetek mindegyike különböző összeget ad, ha különböző értékű bankjegyeket használunk, ugyanis bármely kettő, háromtagú összeget összehasonlítva - mivel csak öt számból választhattuk a tagokat - legalább egy tag megegyezik. Tehát két összeg pontosan akkor lehetne egyenlő, ha van két-két olyan szám, melyek összege megegyezik. Mivel az 1000, 2000, 5000, 10000, 20000 számokból képezhető kéttagú összegek mind különböznek, ezért ha három tagú összegeket képezünk, azok is mind különbözőek lesznek. Ha egy összegben van két azonos értékű bankjegy is, akkor az nem lehet a kimaradtak összege (kipróbálással v. mert akkor ha \(\displaystyle a+a+b\) az első összeg, akkor \(\displaystyle 2a+b=38000-a-b\), azaz \(\displaystyle a=12+\frac{2(1-b)}{3}\). \(\displaystyle b\) csak 1 v. 10 lehetne, de akkor \(\displaystyle a\) 12, ill. 6, ami nem lehet.) Tehát nézzük azt, amikor \(\displaystyle a+a+b\) alakú összegek egyenlőek, azaz \(\displaystyle 2a+b=2c+c\), ahonnan \(\displaystyle 2(a-c)=d-b\) (\(\displaystyle a-c\ge 1000\)). A lehetséges eseteket végignézve az 1000(2+5+5)=1000(1+1+10), 1000(5+5+20)=1000(10+10+10) és 1000(1+1+20)=1000(2+10+10).

Összesen \(\displaystyle 1+15+5+(35-4-3)={\mathbf 49}\) különböző összeget tudunk kifizetni ötszáz, ezer, kétezer, ötezer, tízezer és húszezer forintos bankjegyekből.

Statistics:

297 students sent a solution.
5 points:	155 students.
4 points:	32 students.
3 points:	28 students.
2 points:	16 students.
1 point:	15 students.
0 point:	42 students.
Unfair, not evaluated:	9 solutionss.

Problems in Mathematics of KöMaL, November 2010