## Task 1 - 160831

Uwe had exactly 41 marks for shopping, all in valid East German coins. Among them, there was no coin with a value less than 1 mark. During his shopping, Uwe had to pay exactly 31 marks. He noticed that he could not pay this amount "exactly," meaning he could not pay without receiving change.

Determine all the possibilities for the quantities of each type of coin (1M, 2M, 5M, 10M, 20M) that Uwe could have had with him!
If such numbers of coins are possible, then:

1) If among the coins Uwe had, there was a 10-mark coin, it would follow the contradiction that the remaining coins would add up to exactly $31 \mathrm{M}$.
2) If there was no 10-mark coin but a 5-mark coin, the remaining 36 M could not be made up solely of 20-mark coins; at least $16 \mathrm{M}$ would have to be in 5-mark, 2-mark, and 1-mark coins.

a) If among these there was another 5-M coin, it would add up to $10 \mathrm{M}$ together with the previously mentioned 5-M coin, leading to a contradiction as in 1).

b) If there were only 2-M and 1-M coins, there would either be at least five 2-M coins, which would again add up to $10 \mathrm{M}$, or there would be at most four 2-M coins, and thus at least eight 1-M coins. From five of these and the 5-M coin, one would again get $10 \mathrm{M}$, leading to a contradiction.

3) If among the coins Uwe had, there was no 10-M and no 5-M coin, but a 2-M coin or two 1-M coins, the remaining 39 M could not be made up solely of 20-M coins; at least $19 \mathrm{M}$ would have to be in 2-M and 1-M coins.

Among these, there would either be at least five 2-M coins or at most four 2-M coins and thus at least eleven 1-M coins, in either case allowing $10 \mathrm{M}$ to be assembled again.

4) Therefore, Uwe had at most one 1-M coin and only 20-M coins otherwise. Under these conditions, $41 \mathrm{M}$ can only be composed in such a way that there is exactly one 1-M coin and exactly two 20-M coins.

This composition satisfies the conditions of the problem, as only the amounts $1 \mathrm{M}, 20 \mathrm{M}, 21 \mathrm{M}, 40 \mathrm{M}$, and $41 \mathrm{M}$ can be assembled from these coins, and thus not $31 \mathrm{M}$.