Need help finding maximum unpayable amount between two coins of values 5 and 7, and understanding why.

Question

I am currently taking in introduction course to Discrete mathematics, and came across this problem:

Imagine we have only 5- and 7-coins. One can prove that any large enough integer amount can be paid using only such coins. Yet clearly we cannot pay any of numbers 1, 2, 3, 4, 6, 8, 9 with our coins. What is the maximum amount that cannot be paid?

I am a bit stuck, I was told that the solution was simple enough and didn't require programming ( the course also is a crash course in Python) but I don't see any method that was presented in the lectures for arriving at the answer.

How would I do it, and more importantly what should I take away for future similar problems?

Answer 1

The maximum unpayable amount is 23. That higher numbers are payable comes from the following representations: $$24=5+5+7+7$$ $$25=5+5+5+5+5$$ $$26=7+7+7+5$$ $$27=5+5+5+5+7$$ $$28=7+7+7+7$$ with the rest formed by adding 5s to these. That 23 cannot be formed can be seen by repeatedly subtracting 7 from it – 16, 9, 2, $-5$ – and noting that no nonnegative multiple of 5 appears.

This is sometimes known as Sylvester's coin problem. The largest unpayable amount from coins of value $a$ and $b$, when they are coprime, is $ab-a-b$. The takeaway from this, I think, would be that it is always good to try small examples as part of the problem solving process, so as to get a feel of what the problem's conditions and boundaries are.

Answer 2

This is an instance of the Frobenius coin problem. Given two positive integers $x$, $y$ with ${\rm gcd}(x,y)=1$ the largest amount that cannot be paid with $x$- and $y$-coins is given by $$N=x y-x-y\ .$$ The proof is not too difficult: With $x$-coins alone you can do all sums having remainder $0$ mod $x$. One $y$-coin gives you access to a new remainder mod $x$, two $y$-coins access to a second remainder mod $x$, and so on. It follows that you need $x-1$ of the $y$-coins in order to have access to all remainders mod $x$. These $x-1$ coins make up the amount $N':=(x-1)y$. The last inaccessible amount is then obtained by subtracting $x$ from $N'$, whence we are lead to the $N$ given above.

Answer 3

Parcly Taxel has already given a good answer for your specific question, but, since your title also said "understanding why", let me explain a way to think about this. The following idea works in general to prove Sylvester's $ab-a-b$ result, but I'll describe it in your specific situation.

Think of the positive integers in blocks of 5 consecutive numbers. In the first block $\{1,2,3,4,5\}$, the only payable amount is the last element, 5. As a result, in all subsequent blocks, the last element will be payable, just by using more 5-coins. In the second block, $\{6,7,8,9,10\}$, you get, in addition to the last element 10 that we already know is payable, one more payable element, 7. As a result, in all subsequent blocks, the second element will be payable, just by using more 5-coins. In the third block, $\{11,12,13,14,15\}$, in addition to the second and last elements that we already know are payable, we get one more payable element, 14. So in all later blocks, the second, fourth, and last elements will be payable. The fourth block gets us no new payable elements (because there's no multiple of 7 in that block), but the fifth block gets us the new payable element 21. So in all subsequent blocks, all elements but the third will be payable. In the 6th block, we get the new payable number 28, the third number in that block. So from the sixth block on, everything is payable. The last block with an unpayable element is therefore the fifth block, and its only unpayable element is the third element, 23.

You might check what happens in the analogous calculation with blocks of 7 instead of blocks of 5. You'll find that sometimes a block gets two new payable elements, which didn't happen with blocks of 5, but the process still leads you to the correct answer 23.