Many puzzles sometimes give you a glimpse of some amazing brilliance that lies all around us – this was one such puzzle. While many of you gave the correct answer for the number (which is 11), and this included Abhinav Jain, Pratik Poddar, Anisha Goyal and I, no one could solve the generic version – except Arushi Gupta from California, a Grade XI student. Very well done Arushi!

As I dug more into it, there is a popular version of the puzzle known as the McDonald’s Chicken Nuggets puzzle, but I also found out that this is a well researched problems with some great mathematicians having lent their time to it. A largest number which cannot be expressed with the two relative primes is called a Frobenius number. For the interested reader, they should go to https://en.wikipedia.org/wiki/Coin_problem

Back in 1884, James Joseph Sylvester had figured out for any two relative primes a1 and a2, there are exactly (a1-1)*(a2-1)/2 number of integers that cannot be represented x*a1+y*a2.

Only in 1993, Zdzislaw Skupien´ (Krak´ow) gave a proper proof for the 2 integer problem, though it can be generalized to larger number of integers. Here is the proof, though I must confess that it is hard to follow (also apologize that instead of p and q, I have now used A1 and A2 which has made it easier to copy and paste).

The answer is a1*a2-a1-a2, or a different way to write it is (a1-1)*(a2-1)-1

Here is the proof:

Solution to Puzzle #171

Hope you all enjoyed the puzzle.