1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This is the coin problem. $71$ is the largest sum you cannot obtain. $\endgroup$ – Arthur Oct 23 '13 at 7:50
5
$\begingroup$

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.)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.