Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A pile of stones sits on a table. A player splits any pile with more than one stone into two smaller piles of sizes and , and scores points. She repeats this until every pile has one stone. The way she splits is up to her.
In (b), the first split produces two piles, and each pile is smaller than .
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). Split into (score ), then each into (score each): total . Or split into (score ), into (score ), into (score ): total . The total is the same.
Step 2. Base case. A pile of stone needs no split. The score is .
Step 3. Hypothesis. Assume every pile of fewer than stones gives the score for its size , whatever the splits.
Step 4. The step. The first split of gives with , and scores . By the hypothesis, the two piles then give and . The total is
Step 5. Conclusion. By strong induction, the total is always .
Step 6. Part (c). points.
Step 7. Part (d). A split into and separates exactly pairs of stones. Every pair is separated once, at some split. So the total is the number of pairs, .
Answer: points.
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.