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?
MIT 6.00 Intro Computer Science (OCW)
Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga.
Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus.
Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
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
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.
Oops. I meant 'let r be the remainder of (k-x) divided by 6, aka (k-x) mod 6.'
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!
Not the answer you are looking for? Search for more explanations.
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.