Question

Question P2 Theorem:
Not sure how to prove the theorem that if x,...x+5 sets are possible, then given 6,9,20 packs it is possible to buy any number >=x?

Answer 1

Suppose that you find a way to get x, x+1, ..., x+5, but there is some number larger number, call it k, that you can't get. Now, let r be the remainder of k divided by 6, aka k mod 6, and notice:

(k - x) = n * 6 + r

or equivalently

x + r + n*6 = k

but r is the remainder when dividing by 6, so r must be 0, 1, 2, 3, 4, or 5.

Thus you can take the way you already found to get (x + r), and toss in n additional sixes, and you're done.

Answer 2

Oops. I meant 'let r be the remainder of (k-x) divided by 6, aka (k-x) mod 6.'

Answer 3

So we got six b/c it is the smallest of the pack sizes? If we were to generalize, you could change 6 to a variable which represents the smallest of the pack sizes? So if Mcdonalds changed McNugget sizes to an 8 pack, 9 pack, 20 pack, would the equation change to (k-x) = n*8 +r. meaning that R can only be from 0 to 7, so now we have to have x,...x+6 in order to ensure that every integer above it can be solved? Maybe i'm not 100% understanding, but how would the generalized formula look so we can any value of pack sizes, and still find the maximum unsolvable number? Thanks!

Answer 4

You got it! if you have several different pack sizes and the smallest is S then any set of S continuous sizes implies that all larger sizes can be found.

So in general you want to find solutions for x, x+1, x+2, ..., x+S where S is the smallest of the pack sizes, and you're guaranteed to be able to find solutions to all larger pack sizes.

Of course, you're not guaranteed to be able to find S contiguous solutions. For example, if all of your pack sizes are even, you won't be able to get any odd numbers.

Answer 5

Love it, thanks for the help.