Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 guys.

Thanks

share|improve this question
    
Because {6,10} are not coprime. So the McNuggets/Frobenius formula ab - a - b doesn't hold. See my answer. –  smci Mar 28 at 16:25

4 Answers 4

up vote 27 down vote accepted

The answer is infinity. How would you find a combination of coins to get to an odd number?

share|improve this answer
9  
I think technically the answer is that there is no answer (ie no largest value). Giving you an infinite amount of 10s would give you infinity so you should likely avoid answers like that (and indeed any answer that pretends that infinity is an answer). –  Chris Mar 28 at 12:19
2  
Of course techincally an answer that says there is no answer either is no answer or it is wrong (or both).;-) –  Marc van Leeuwen Mar 28 at 12:57
7  
Or $∞-1$ if infinity is even ;) –  Briguy37 Mar 28 at 15:10
    
@MarcvanLeeuwen: Perhaps I should have said the correct response is that there is no valid answer. –  Chris Mar 28 at 16:43
1  
Should it read "How would you find a combination of even coins to get to an odd number?" –  Brad Mar 28 at 21:07

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.

share|improve this answer
    
Does the quoted formula have name? A link or reference would be appreciated. –  bduran Mar 28 at 14:18
3  
The general problem is the Frobenius coin problem I don't know of a name for the formula –  Ross Millikan Mar 28 at 14:54

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 given a name, btw. Just the theorem about how to find the maximum value which cannot be formed.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.