Question

About problemset 2 - I'm not sure how to prove that If it is possible to buy x, x+1,…, x+5 sets of McNuggets, for some x, then it is
possible to buy any number of McNuggets >= x. Is this a gcd problem ?

Answer 1

There are, of course, different ways to solve it, but I thought about the general solution like this:
Let T(x) be a function whose domain are the natural numbers bigger than x+5 and that returns a tuple with the number of packages. So, the general solution for this is that T(x) = T(x - k) + (1,0,0), where k is the size of the smallest package and the first coordinate represents the number of smallest package that are needed.
Think about it this way: what is the solution to x+6? The solution to x plus a package of size 6. To x+7 is the solution of package x+1 plus a package of size 6 etc.
I think it's solvable using induction, really.

Answer 2

I've posted some solutions to ps at pythonforum.org. Have a look any feedback is welcome. In the forum search for mit.

Answer 3

So, it's not a gcd problem - or a lcm problem - mainly because this centers around addition, not multiplication. As far as the proof goes, I don't think the profs were looking for a formal math proof, but if you wanted to do one, do six base cases and then do induction assuming n > these six base cases. The induction step might require six cases as well. A general proof of a claim resembling this principle is harder, especially b/c not all triples of numbers will be able to generate every integer after some point (if all three are even, for example, then you will never find a solution).

Answer 4

It looks like it is a general role that the largest number you cannot buy is determed by the smalest number in the tuple - but hey - I think I better move on to the next problem before ps3 makes my head spin - thanks to all for the feed back