Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Stamps come in values of units and units. Prove that every amount above units can be made with these stamps, and that itself cannot. Show it by giving five amounts in a row that can be made, then adding -unit stamps. Then list every amount that cannot be made, and count them. Give the largest amount that cannot be made and the number of such amounts.
has integer solutions exactly when . From one solution , all are
For coprime the largest that is not with is .
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Given. Amounts with .
Step 1. Five in a row. , , , , .
Step 2. Every larger amount. Any is one of plus some -unit stamps. So every amount from on can be made.
Step 3. cannot. With eights the rest is , and none is a multiple of . Four eights is , too much.
Step 4. The full list. Testing each amount from to in the same way leaves : fourteen amounts.
Check. The formulas agree: and .
Answer: the largest amount that cannot be made is , and amounts cannot be made. Proof complete.
What if? There is a neat symmetry: for , exactly one of and can be made. That is why exactly half of the numbers fail.
Log in to join the discussion.
Loading…