Solution to Puzzle #171: Buying Dimsums

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

Solution to Puzzle #171

Hope you all enjoyed the puzzle.

 

This entry was posted in Solution and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s