# Frobenius coin problem

Suppose that you only have coins worth, say 3 and 5 euros. According to Sylvester result we can find the Frobenius nr $g(3,5)=15-3-5=7$ so 7 is the largest integer that cannot be written as $a_{1}k_{1}+a_{2}k_{2}$ for $k_{1},k_{2}\in\mathbb{N}$ and $a_{1},a_{2}$ are the values of these coins.

a) how do you pay 8€,9€ and 10€ with these coins?

b)use a) to show that it is possible to pay all amounts that are greater than 10€ with the coins 3€ and 5€.

c) show that it is impossible to pay the amount of 7€ with these coins.

I am afraid I do not understand 100% the whole idea behind the Frobenius numbers.

a) can we just take 3€+5€=8€ and 3€+3€+3€=9€ and 5€+5€=10€ this seems suspicious of how easy it is....

b)do I have to use both coins? or just 3€ or 5€? 11€=3€+5€+3€

12€=3€+3€+3€+3€

13€=3€+5€+5€

14€=5€+3€+3€+3€

.

.

c) if we could pay 7€ with these coins we could have written

$7€=k_{1}5€+k_{2}3€$ but this is impossible as $k_{1},k_{2}\in\mathbb{N}$

can someone please explain to me what should be done in this exercise and how?

• In the standard problem, yes, you are allowed to have $0$ coins of one of the kinds. One can modify that condition to insist on at least one of each. The answer changes, but not much. Commented May 24, 2013 at 13:34
• for part (b) After 14, show that all numbers > 14 can be written as a number between 10-14 + 5. Commented May 24, 2013 at 13:54

For part c, consider the three cases:

1. No €5 coin is used
2. Exactly one €5 coin is used
3. At least two €5 coins are used

In each case, you can easily show that the total can't be €7.

• @@Tony: Thanks, I will think about it. I have just had an idea to maybe show it by creating a Diophantine equation of the form $5x+3y=7$ and then show that the general solution will contain 1 negative and 1 positive number, which is not allowed in our linear construction.
– H.E
Commented May 24, 2013 at 14:44

Your approach to (c) can be made to work. You have the Diophantine equation $3x+5y=7$. One solution is $x=-1,y=2$, so the general solution is

\left\{\begin{align*} x&=-1+5k\\ y&=2-3k\;. \end{align*}\right.

Since we require that $x\ge 0$, we must have $k\ge 1$, but then $y\le-1<0$, so there is no solution in non-negative integers.

However, the numbers are so small that it’s easier to examine cases, unless you’re very comfortable with solving linear Diophantine equations. Since $3+5>7$, you clearly cannot use both denominations to make $7$. But $7$ is not a multiple of $3$, so you can’t make it using only $3$’s, and it’s not a multiple of $5$, so you can’t make it using only $5$’s. Thus, you can’t make it at all.

For (b) you really do need a proof by induction. For your induction step try to prove that if you can make $n,n+1$, and $n+2$, then you can make $n+1,n+2$, and $n+3$; do you see why that would give you the desired result once you know how to make $8,9$, and $10$?

• @@Brian: I got slightly different solution to the same equation...: my particular solution is $\begin{cases}x_{0}=14\\y_{0}=-7\end{cases}$ and the general solution is $\begin{cases}x=5k+14\\y=-3k-7\end{cases}$ I would really appreciate if you could help me to work out the induction problem to part b. I can prove ''standard'' induction problems but I don't see how I can do this one
– H.E
Commented May 24, 2013 at 17:50
• @Heidi: With your general solution the argument is that $k\le-3$ is needed to make $y\ge 0$, but then $x\le-1<0$; it works just as well. Here’s a further hint for the induction: if you can make a total of $n$, how can you use that to make a total of $n+3$? If you can do that, being able to make $n,n+1$, and $n+2$ automatically makes you able to make $n+1,n+2$, and $n+3$, since you already know how to make $n+1$ and $n+2$. Commented May 24, 2013 at 17:53