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.

Your answer to (a) is correct. Your answer to (b) needs to have induction, three dots is insufficient. Your answer to (c) needs to go into a lot of detail about the word “impossible”; why is this so?