# 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?

#### Solutions Collecting From Web of "Frobenius coin problem"

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$?

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.