The chicken McNugget theorem is an interesting concept which has extremely specific applications. The question type asks you to find the largest number which cannot be formed using two or three denominations. Let’s see how to solve these questions.
The story behind the concept is very interesting. In McDonalds, chicken nuggets used to be available in denominations of 9 and 20. Someone wondered what would be the largest number of nuggets one could not have even if any combination of the two denominations was used. The answer, by hit and trial came out to be 151.
Mathematically, the answer can be found using a simple formula. The only prerequisite? The two numbers should be co-prime to each other. So, for two numbers a and b that are relatively co-prime, the highest number that cannot be formed using the two denominations is given by
You can try another example to understand the same. Postage stamps are available in denominations of Rs. 5 and Rs. 7 only. What is the largest amount of stamps that cannot be made using these two denominations?
Three variables
It becomes extremely tricky and difficult to solve in case of three variables. The original form of the theorem involved 3 denominations of nuggets – 6, 9 and 13. Let’s see how to find the largest number that cannot be formed using these three denominations.
Consider 6a+9b. It can be written as 3(2a+3b). Now, 2a+3b can take all values except 1. So, all numbers in the form of 3k are possible that are greater than 3.
Consider 6a+9b+20. It can be written as 3(2a+3b+6)+2. Again, all the numbers of the form 3k+2 can be formed except when 2a+3b=1 which is not possible. So, all numbers of the form 3k+2 greater than 23 can be formed.
Consider 6a+9b+40. It can be written as 3(2a+3b+13)+1. Again, all the numbers of the form 3k+1 can be formed except when 2a+3b=1 which is not possible. So, all numbers of the form 3k+1 greater than 43 can be formed.
So, the largest number that cannot be formed using denominations 6, 9 and 20 is 43. You can use a similar approach to solve all the questions from this area. While two denominations is fairly common, three denominations is very rare and will be found only in a paper deemed to be one of the toughest.
PS: For the vegetarians, the theorem is also known as the postage stamp theorem or the Frobenius coin problem.
