Eötvös 1929/1 solution

33rd Eötvös 1929

Problem 1

Coins denomination 1, 2, 10, 20 and 50 are available. How many ways are there of paying 100?

Solution

For 2n there are n+1 ways using just the 1 and 2 coins (0, 1, 2, ... or n 2s). Similarly, there are m+1 ways of paying 20m or 20m+10 with just the 10 and 20 coins. Hence using just the 10, 20, 50 coins we get (for example there are 4 ways of paying 70 without using a 50 and 2 ways with, total 6):

0  10  20  30  40  50  60  70  80  90  100
0   1   2   2   3   4   5   6   7   8   10

Hence there are 1·51 + 1·46 + 2·41 + 2·36 + 3·31 + 4·26 + 5·21 + 6·16 + 7·11 + 8·6 + 10·1 = 784 ways in total.

33rd Eötvös 1929