1
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – André Nicolas
    Commented May 24, 2013 at 13:34
  • 1
    $\begingroup$ for part (b) After 14, show that all numbers > 14 can be written as a number between 10-14 + 5. $\endgroup$
    – Foo Barrigno
    Commented May 24, 2013 at 13:54

3 Answers 3

Reset to default
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @@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. $\endgroup$
    – H.E
    Commented May 24, 2013 at 14:44
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ @@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 $\endgroup$
    – H.E
    Commented May 24, 2013 at 17:50
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Brian M. Scott
    Commented May 24, 2013 at 17:53
1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ @@Vadim: how can you construct 7 , as a linear combination of 5 and 3 and the two other natural numbers??? $\endgroup$
    – H.E
    Commented May 24, 2013 at 13:36
  • 2
    $\begingroup$ @HeidiE, challenging me to do something is not an adequate proof that it cannot be done. $\endgroup$
    – vadim123
    Commented May 24, 2013 at 13:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .