Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A games arcade sells tokens worth points and points. A prize can be bought only with an exact total.
Write each base case as a sum of tokens.
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.
Step 1. Part (a). The totals that can be made up to are . The ones that cannot are . The largest is .
Step 2. Base cases. The step goes back places, so we need four in a row: , , , .
Step 3. The step. Let and assume every total from to can be made. Then can be made. Add one token of points.
Step 4. Conclusion. By strong induction, every total of or more can be made.
Step 5. Part (c). The totals that cannot be made are the nine listed in Step 1.
Step 6. Part (d). , as found. The count also matches .
Answer: the largest total that cannot be made is points, and totals cannot be made.
Log in to join the discussion.
Loading…
Strong induction: assume and prove . A step that goes back places needs base cases. Well-ordering: every non-empty set of positive integers has a least element.