Making N baht using only 9 baht and 10 baht coins

Question

The Thai government decides to issue coins of 9 baht. Show that, for all sufficiently large numbers N you can make N baht using only 9 baht and 10 baht coins.

This is the coin problem. $71$ is the largest sum you cannot obtain. — Arthur, Oct 23 '13 at 07:50

score 5 · Answer 1 · answered Oct 23 '13 at 07:52

5

First, note that all of the values from 72 to 80 can be expressed with 8 coins.

Use that as a base case, and prove that every higher value can be achieved using induction. (Note that if $n - 9$ is expressible, then $n$ is as well.)

answered Oct 23 '13 at 07:52

Dennis Meng

1,397

Don't you mean n = 9? Or is it n - 9? – mathis...Math Oct 23 '13 at 08:00
I definitely meant $n - 9$. – Dennis Meng Oct 23 '13 at 08:03
The number of elements for which you can not make change is:$\frac{1}{2}(10 - 1)(9 - 1) = 36 $ – Alan Oct 23 '13 at 16:46

Making N baht using only 9 baht and 10 baht coins

1 Answers1

Linked