
Can you solve this McNuggets Puzzle Computer Programming Puzzle
video description
Date: 2023-11-15
Related videos
Comments and reviews: 15
chaman, charlie
I used a combined approach of your mathematical and algorithmic while solving and ended up with right answer 43. Felit my approach was more rigorous
Same logic to find 5 consecutive numbers ie if N number of nuggets can be formed by combination of the three,
i. e N = 6(x) + 9(y) + 20(z)
then N+1 to N+5 should be formed too by other combinations
(the trick is to see how the numbers 1 to 5 can be formed in combinations of multiples of 6, 9 and 20
Eg. 1 = 30 - 9 - 20, 2 = 20 - 18,
It is easy to see that with atleast 1 box of 6, 2 boxes of 9 and one box of 20, all these combinations can be generated with only additions and not subtraction terms.
Hence minimum needed is 6 + 9 + 9 + 20 = 44
reply
I used a combined approach of your mathematical and algorithmic while solving and ended up with right answer 43. Felit my approach was more rigorous
Same logic to find 5 consecutive numbers ie if N number of nuggets can be formed by combination of the three,
i. e N = 6(x) + 9(y) + 20(z)
then N+1 to N+5 should be formed too by other combinations
(the trick is to see how the numbers 1 to 5 can be formed in combinations of multiples of 6, 9 and 20
Eg. 1 = 30 - 9 - 20, 2 = 20 - 18,
It is easy to see that with atleast 1 box of 6, 2 boxes of 9 and one box of 20, all these combinations can be generated with only additions and not subtraction terms.
Hence minimum needed is 6 + 9 + 9 + 20 = 44
reply
yuri
Boxes with values of 9, 12 and 25:
Every multiple of 3 greater than or equal to 18 can be created either as a multiple of 9, or as 1x12 + multiple of 9, or as 2x12 + multiple of 9.
Every n = 1 mod 3 greater than or equal to 43 can be created as 1x25 + -multiple of 3 greater than or equal to 18-
Every n = 2 mod 3 greater than or equal to 68 can be created as 2x25 + -multiple of 3 greater than or equal to 18-
==> every number greater than or equal to 68 can be created.
What about numbers less than 68?
67 = 1x25 + 2x12 + 2x9
66 = 1x12 + 6x9 = 4x12 + 2x9
65 = 2x25 + 15, which cannot be created.
Conclusion: Highest non-McNugget number is 65.
reply
Boxes with values of 9, 12 and 25:
Every multiple of 3 greater than or equal to 18 can be created either as a multiple of 9, or as 1x12 + multiple of 9, or as 2x12 + multiple of 9.
Every n = 1 mod 3 greater than or equal to 43 can be created as 1x25 + -multiple of 3 greater than or equal to 18-
Every n = 2 mod 3 greater than or equal to 68 can be created as 2x25 + -multiple of 3 greater than or equal to 18-
==> every number greater than or equal to 68 can be created.
What about numbers less than 68?
67 = 1x25 + 2x12 + 2x9
66 = 1x12 + 6x9 = 4x12 + 2x9
65 = 2x25 + 15, which cannot be created.
Conclusion: Highest non-McNugget number is 65.
reply
Philip
You can solve using algebra 6x+9y+20z=total nuggets simplifies to 3(2x+3y)+20z where x, y, z integer inc 0, so total is always a multiple of 3 plus multiple of 20 but 2x+3y cannot equal 1 when x and y integers inc 0 so total not achieveable is 20u+3 where u integer inc 0, u cannot be 3 or more in this not achieveable formulae, otherwise 20u+3 is 3(20+1) which is same as first formula with z =0, x=0, y=7, u cannot also be 4 or greater as this becomes 20+3(20+1) which is also orginal formula with z=1, x=0, y=7 same for any other value u greater than 4 so u max is 2 which means max unachieveable is 2x20+3 = 43
reply
You can solve using algebra 6x+9y+20z=total nuggets simplifies to 3(2x+3y)+20z where x, y, z integer inc 0, so total is always a multiple of 3 plus multiple of 20 but 2x+3y cannot equal 1 when x and y integers inc 0 so total not achieveable is 20u+3 where u integer inc 0, u cannot be 3 or more in this not achieveable formulae, otherwise 20u+3 is 3(20+1) which is same as first formula with z =0, x=0, y=7, u cannot also be 4 or greater as this becomes 20+3(20+1) which is also orginal formula with z=1, x=0, y=7 same for any other value u greater than 4 so u max is 2 which means max unachieveable is 2x20+3 = 43
reply
Ralph
Very clever. Both approaches have their own unique merit: you can solve a subset of this type of problem very quickly with number theoretical approaches. If time and space complexity is not of issue, an algorithmic approach is simple and effective.
I think there's something pretty about the fact that you cycle through mod 3 using the boxes of 20 to create this kind of perfectly closed -loop- that you can use to identify the largest -unsolvable- number of nuggets. Way more satisfying than my -check a bunch of numbers- algorithm that just -works-.
Very nice, many thanks for these beautiful puzzles!
reply
Very clever. Both approaches have their own unique merit: you can solve a subset of this type of problem very quickly with number theoretical approaches. If time and space complexity is not of issue, an algorithmic approach is simple and effective.
I think there's something pretty about the fact that you cycle through mod 3 using the boxes of 20 to create this kind of perfectly closed -loop- that you can use to identify the largest -unsolvable- number of nuggets. Way more satisfying than my -check a bunch of numbers- algorithm that just -works-.
Very nice, many thanks for these beautiful puzzles!
reply
Adam
Here's an implementation of the algorithm in python using dynamic programming.
I believe it runs in O(n)-O(k, where n is the size of the smallest box and k is the number of different box sizes you can order.
def isPossible(n): -
global biggest-
global boxes-
global possible-
if len(possible)>n: -
return possible[n]-
for b in boxes: -
if b
reply
Here's an implementation of the algorithm in python using dynamic programming.
I believe it runs in O(n)-O(k, where n is the size of the smallest box and k is the number of different box sizes you can order.
def isPossible(n): -
global biggest-
global boxes-
global possible-
if len(possible)>n: -
return possible[n]-
for b in boxes: -
if b
reply
P.
Thank you for the amazing amazing interactive puzzle Ammar! Watching your videos helps me greatly to exercise my mind before a new semester: D
I'm happy to have found the answer with the tools you introduced me to: (=65) using only a pencil, paper, and the algorithm. Thanks again!
reply
Thank you for the amazing amazing interactive puzzle Ammar! Watching your videos helps me greatly to exercise my mind before a new semester: D
I'm happy to have found the answer with the tools you introduced me to: (=65) using only a pencil, paper, and the algorithm. Thanks again!
reply
Dhiraj
Given value of
N and K (N>=2, K>=1)
From Range K, N + K -1
How many number you can't aachive?
Ex.
N = 3, K = 3
Range ( 3, 5 )
So by combination of 3, 4, 5
You cant aachive 1 and 2 so ans is
2 ( total no. Cant aachive )
reply
Given value of
N and K (N>=2, K>=1)
From Range K, N + K -1
How many number you can't aachive?
Ex.
N = 3, K = 3
Range ( 3, 5 )
So by combination of 3, 4, 5
You cant aachive 1 and 2 so ans is
2 ( total no. Cant aachive )
reply
Rupin
This is actually the Frobenius number, which mathematically is the largest number for which the Frobenius equation has no solution. This equation was first developed by Sylvester in 1884. So it is a very old problem.
reply
This is actually the Frobenius number, which mathematically is the largest number for which the Frobenius equation has no solution. This equation was first developed by Sylvester in 1884. So it is a very old problem.
reply
Paulo
I can buy -43- nuggets! At noon, I buy 6 nuggets. Later, I return to the grocery and order 49 nuggets, which I partially pay with the 6 nuggets I bought earlier. Technically, I bought -43 nuggets! -
reply
I can buy -43- nuggets! At noon, I buy 6 nuggets. Later, I return to the grocery and order 49 nuggets, which I partially pay with the 6 nuggets I bought earlier. Technically, I bought -43 nuggets! -
reply
LOGITRIKK
#include
#include
using namespace std;
int main)
-
int n=3, sum=100, i, j, temp, a[]=-9, 12, 25-;
int dp[sum+1];
dp[0]=0;
for(i=1; i
reply
#include
#include
using namespace std;
int main)
-
int n=3, sum=100, i, j, temp, a[]=-9, 12, 25-;
int dp[sum+1];
dp[0]=0;
for(i=1; i
reply
Minh
Well, similar to the original problems, from 9's and 12's we can make every multiple of 3 that are greater than 15, but not 15. So the answer is 25x2+15 = 65
reply
Well, similar to the original problems, from 9's and 12's we can make every multiple of 3 that are greater than 15, but not 15. So the answer is 25x2+15 = 65
reply
Abhimanyu
65, though it took a long time to reach this by making all the combinations.
What's the shorter or optimised method of applying the algorithm?
reply
65, though it took a long time to reach this by making all the combinations.
What's the shorter or optimised method of applying the algorithm?
reply
Ryarios
Define -impossible-. There are lots of large numbers that can-t be bought if nothing more than the fact that there isn-t enough money or chicken.
reply
Define -impossible-. There are lots of large numbers that can-t be bought if nothing more than the fact that there isn-t enough money or chicken.
reply
Archana
This is something related to frobenius number. If you are interested in maths then you can check out Vsauce2 video, 'Frobenius'
reply
This is something related to frobenius number. If you are interested in maths then you can check out Vsauce2 video, 'Frobenius'
reply
Michael
The highest number of nuggets that cannot be bought is one more than the restaurant has in its freezer
reply
The highest number of nuggets that cannot be bought is one more than the restaurant has in its freezer
reply
Add a review, comment
Other channel videos















