Coin problem with $6$ and $10$

Question

I am doing a coin problem where:

In a city where you only have denominations in $6$ and $10$. What is the largest value that this city cannot pay?

In another problem that my teacher showed me, where instead the numbers were $5$ and $9$, we had: $(5*9)-9-5 = 31$, which is the answer.

Using that same logic, i would get $44$ but the problem is that: $4*6+2*10 = 44$, that does not make sense!

Any advice or ideas would be great.

Answer 1

The formula you quote assumes the coins have no common factor, because otherwise you cannot make any value not divisible by that common factor. The corresponding thing when they do have a common factor is to consider units of that factor. So your coins are $3$ and $5$ (units of $2$). The largest even number you cannot make is $(3×5-3-5)×2=14$. Then as you can make $16=10+6$, $18=3×6$, $20=2×10$ you can add $6$'s as required to make any even number.

Answer 2

This is the well-known Chicken McNuggets Theorem to give it its pop-culture name, also more formally known as the Frobenius problem as Ross wrote.

See the related Schur's Theorem which applies when the set of numbers is relatively prime.

In your case the confusion is due to the following: The general formula for the case of two integers: ab - a - b = (a-1)(b-1) -1 only holds when {a,b} are coprime. But {6,10} are not coprime. So I don't know if a general result applies in the case.

(I've never seen the actual formula itself given a name, btw. Just the theorem about how to find the maximum value which cannot be formed.)

Answer 3

As has been noted, since $(6,10)=2$ any amount of money used must be even. Assuming that, what is the largest even amount that cannot be paid?

Let's divide everything by $2$ so that we consider double coins of $3$ and $5$ value.

Theorem 1 below shows that if $(a,b)=1$ and $c\ge(a-1)(b-1)$, then $ax+by=c$ has a solution where $x,y\ge0$.

Since $(3-1)(5-1)=8$, any amount of $8$ or greater double coins can be paid. Thus, any even amount greater than or equal to $16$ can be paid.

Since $3\not\mid7$ and $5\not\mid7$ and $7\lt3\cdot5$, Theorem 2 says that only one of $7$ or $8$ can have a non-negative solution. Since $8$ has a non-negative solution, $7$ can't. Therefore, the largest even amount that can't be paid is $\mathbf{14}$.

---

Theorem 1: Suppose $(a,b)=1$ and $c\ge(a-1)(b-1)$. Then $ax+by=c$ has a non-negative solution, that is, one in which both $x$ and $y$ are non-negative integers.

Proof: Since $(a,b)=1$, we have some $(u,v)$ so that $au+bv=1$. The set of all solutions to $ax+by=c$ is $$ \{(cu+bk,cv-ak):k\in\mathbb{Z}\}\tag{1} $$ Thus, we have a non-negative solution $(x,y)$ precisely when there is an integer $k$ so that $$ k\ge-cu/b\tag{2} $$ (so that $cu+bk\ge0$) and $$ k\le cv/a\tag{3} $$ (so that $cv-ak\ge0$). Thus, $ax+by=c$ has a non-negative solution iff $$ [-cu/b,cv/a]\cap\mathbb{Z}\ne\{\}\tag{4} $$ Suppose there is no integer in this interval. This means there must be a $j\in\mathbb{Z}$ so that $$ [-cu/b,cv/a]\subset(j,j+1)\tag{5} $$ Since $cu$ and $cv$ are integers, we must have $$ -cu/b-j >= 1/b\tag{6} $$ and $$ j+1-cv/a >= 1/a\tag{7} $$ Adding $(6)$ and $(7)$ and multiplying by $ab$ gives $$ ab-cau-cbv\ge a+b\tag{8} $$ Since $au+bv=1$, $(8)$ becomes $$ c\le ab-a-b\tag{9} $$ Therefore, if $c\ge ab-a-b+1=(a-1)(b-1)$, then there is a non-negative solution $(x,y)$ to $ax+by=c$.

QED

---

Theorem 2: Suppose $(a,b)=1$, $0\lt c\lt ab$, and neither $a\mid c$ nor $b\mid c$. Then one and only one of $$ ax+by=c\tag{10} $$ and $$ ax+by=ab-c\tag{11} $$ has a non-negative solution.

Proof: Note that since neither $a\mid c$ nor $b\mid c$, neither $x$ nor $y$ can be $0$ in any solution. Therefore, any non-negative solution must be a positive solution, that is, one in which both $x$ and $y$ are positive integers.

Suppose both $as+bt=c$ and $au+bv=ab-c$ are positive solutions. Add them together to get $$ a(s+u)+b(t+v)=ab\tag{12} $$ Since $(a,b)=1$, $(12)$ says that $b\mid s+u$ and $a\mid t+v$. Since $s$, $t$, $u$, and $v$ are positive integers, we must have that $s+u\ge b$ and $t+v\ge a$. However, then $a(s+u)+b(t+v)\ge2ab$, which contradicts $(12)$.

Therefore, we have shown that at most one of $(10)$ and $(11)$ can have a non-negative solution.

Suppose $(10)$ does not have a non-negative solution. Since $(a,b)=1$, we have some $(u,v)$ so that $au+bv=1$. The set of all solutions to $ax+by=c$ is then $\{(cu+bk,cv-ak):k\in\mathbb{Z}\}$. Therefore, we can find an $(s,t)$ so that $as+bt=c$ and $0\le s\lt b$.

Since $bt=c-as$, we have that $-ab\lt bt\lt ab$. Since $(10)$ does not have a non-negative solution, we must have $-ab\lt bt\lt 0$. Thus, we have the non-negative solution $a(b-s)+b(-t)=ab-c$.

Therefore, we have shown that at least one of $(10)$ and $(11)$ must have a non-negative solution.

QED