Question

Can anyone please explain me the solution to this problem?
Show that it is possible to buy exactly 50, 51, 52, 53, 54, and 55 McNuggets, by finding solutions to the Diophantine equation. You can solve this in your head, using paper and pencil, or writing a program. However you chose to solve this problem, list the combinations of 6, 9 and 20 packs of McNuggets you need to buy in order to get each of the exact amounts.
Given that it is possible to buy sets of 50, 51, 52, 53, 54 or 55 McNuggets by combinations of 6, 9 and 20 packs, show that it is possible to buy 56, 57,…, 65 McNuggets.

Answer 1

it is from problem set 2 of 6.00 Introduction to Computer Science and Programming (Fall 2008)

Answer 2

i would write a program that increments the smallest pack of McNuggets until it either hits the target number or goes over. if it goes over i would then reset my count, add 1 of the next size up packet of nuggets, and then repeat the first step. i dont know what the diophantine equation is but thats how i would approach this problem

Answer 3

This is the solution:

50 = 20+9+9+6+6: 1 twenty-piece, 2 nine-piece, 2 six-piece
51 = 9+9+9+9+9+6: 5 nine-piece, 1 six-piece
52 = 20+20+6+6: 2 twenty-piece, 2 six-piece
53 = 20+9+9+9+6: 1 twenty-piece, 3 nine-piece, 1 six-piece
54 = 9+9+9+9+9+9+9: 6 nine-piece
55 = 20+20+9+6: 2 twenty-piece, 1 nine-piece, 1 six-piece

That's how you make combinations for 50 through 55. To make any combination higher than that, subtract 6 (the smallest number of McNuggets you can get in an order) until you get some number between 50 and 55. Then add the appropriate number of 6-piece orders.

For example: What combination of orders will yield 77 McNugets?

Start subtracting sets of 6:
77 - 6 = 71 (1 set)
71 - 6 = 65 (2 sets)
65-6 = 59 (3 sets)
59 - 6 = 53 (4 sets)

53 is listed above as 1 twenty-piece, 3 nine-piece, and 1 six piece. So if we add 4 more 6 piece orders to that, we will get 77 McNuggets.

We can do this for any number greater than 55.

Answer 4

thanks got it :)

Answer 5

Here's how I did it. However, I don't quit understand what the theorem means to say...if anyone has an idea, is more then welcomed to tell it :D thanks!

Answer 6

Hi For8aby- I described how the theorem works in a previous post to this thread. Did you see that?

Answer 7

I figured it out :) Thank you anyways