0

I've been trying to solve a problem a user posted that I thought was interesting.

Considered a lucky number, the Thai government decides to issue coins of 9 baht. Show that, forall suciently large numbers N you can make N baht using only 9 baht and 10 baht coins.

However I am unable to prove it even with the help of the answer. I mean how can n-9 be used as an inductive step to prove the problem?

Link: Making N baht using only 9 baht and 10 baht coins

Community
  • 1
jim
  • 1
  • 1
    You are seriously asking, if you can make x bahts with 9-baht and 10-baht coins, how does that help you make x+9 bahts? Hint: what happens if you throw in one more 9-baht coin? – bof Oct 23 '13 at 22:50
  • Speaking as the person who posted the answer, this really should've been a comment somewhere on that question (possibly a comment to my answer), though I recognize that you can't comment just yet. – Dennis Meng Oct 23 '13 at 22:54
  • Sorry @DennisMeng is Arthur's method correct then? Is that what you meant? – jim Oct 23 '13 at 22:57
  • His proof is more direct. What I did with my proof is first point out a string of 9 consecutive numbers that are all achievable, then suggest showing the rest by the induction. The idea was that in the induction step, you could assume by induction hypothesis that $n - 9$ was achievable, then just add another 9-baht coin to get $n$. – Dennis Meng Oct 23 '13 at 22:59
  • Do you think you could write out your version? You don't have to but I'm interested on how this could be proven inductively – jim Oct 23 '13 at 23:02
  • The basic idea is that you assume by induction hypothesis that there's an $n \geq 80$ such that all $k$ between 72 and $n$ (inclusive) can be expressed. Then for the induction step, note that $n - 8$ can be expressed, and thus $n + 1$ can be as well by just adding one more 9-baht coin. – Dennis Meng Oct 23 '13 at 23:14

2 Answers2

1

Let $N > 90$, and write $N = 10a + b$ for integers $a,b$, where $b < 10$. Then $9(10-b) + 10(a+b-9) = N$.

Arthur
  • 5,524
0

You're interested in solving the Coin Problem. The smallest number which cannot be made using coins of value $a_1$ and $a_2$ is $g(a_1,a_2) = a_1a_2 - a_1 - a_2$. This number is called Frobenius number.

So for our case we have: $g(10,9) = 10 \cdot 9 - 9 - 10 = 71$. So for every $N>71$ there is an unique solution.

So you can made 72 using 8 coins of 9 bahts. To make it 73 add one coin of 10 bahts and take out one coin of 9 bahts. Do that until you have 8 coins of 10 bahts and 0 coins of 9 bahts. Then do that again but now you will have to have 9 coins of 10 bahts and -1 coin of 9 bahts. Impossible? But note the follwoing:

$$10(9) + (-1)9 = 81$$ $$9(10-1) = 81$$ $$9(9) + 10(0) = 81$$

The numbers in the brackets are the number of coins of that type.

So following the arrangment we reached the simular position as at the beginning, but we have a coin of 9 bahts more. So we can repeat the cycle and reach 90 and so on. This way of "modified" induction will do the job.

For more general proof let $N = a_1x + a_2y$. Becasue $(a_1,a_2) = 1$ this equation will always have integer solution for $x$ and $y$. Because $N,a_1,a_2 > 0$ we get that at least one of $x$ or $y$ is positive. WLOG let $x>0$. We'll prove that for $N > (a_1-1)(a_2-1)$ there is non-negative solution for $y$.

Let $y = 0,1,2,3,\cdots,a_1-1$, then because $(a_1,a_2) = 1$ for different values for $y$ all integers $n - a_2y$ are mutually distinct modulo $a_1$. This is basic property from modular arithmetics. We know that $N=a_1x + a_2y$. So we have:

$$a_1x = N - a_2y \ge (a_1-1)(a_2-1) - (a_1-1)a_2 = (a_1-1)(a_2-1-a_2) = -a_1+1$$

Divide both side by $a_1$ we get:

$$a_1x \ge 1-a_1$$ $$x \ge \frac 1{a_1} - 1 > -1$$

Because $x$ is an integer we get that $x\ge 0$, i.e $x \in \mathbb{N_0}$

Q.E.D.

Stefan4024
  • 35,843
  • Just a "nit" re. your phrasing of the coins result: the solution when $N>71$ is only unique for a small range, and after that there are multiple solutions. – coffeemath Oct 24 '13 at 02:42
  • For every $N$ just one of the values for $y$. So that means that for one $N$ there will be one $j$ that satisfy the equatio. The congruence relation $N \equiv x \pmod{9}$ will have $9$ different solution for $x$ depending on $N$. And the relation $N - 10y \equiv 0 \pmod{9}$ will also have $9$ solution, because as a I've said $(9,10) = 1$ so the relatins are one-to-one, which means that for fixed $N$ only one of the available values for $y$ will work. – Stefan4024 Oct 24 '13 at 14:39
  • What about this example? $N=950$ is expressible two ways as $1050+950$ and as $1041+960$. What I meant in the comment is only that for some large $N$ there can be more than one solution. For example, as long as the $x,y$ used in $10x+9y=N$ happen to satisfy $x\ge 9$ we can subtract $9$ from $x$ and add 10 to $y$ for another representation. – coffeemath Oct 24 '13 at 22:43
  • And you can easily see $41 \equiv 50 \pmod 9$ and $50 \equiv 60 \pmod {10}$. Maybe I wasn't clear enough there are unique solution regarding modulo ${a_1}$ or modulo ${a_2}$ – Stefan4024 Oct 24 '13 at 22:44
  • OK yes the solutions have a uniqueness form using mods. That restriction seems similar to those which apply if one solves $ax+by=k$ without sign restrictions on $x,y$ – coffeemath Oct 24 '13 at 22:46
  • Yes, my point was to prove that for a fixed $N$ and for given $y$ there will always be a unique positive solution modulo $a_1$. Actually that's the reason why I allow only positive values smaller than $a_1$ fo $y$ in the answer. – Stefan4024 Oct 24 '13 at 22:49