1st ASU 1961 problems Problem 10 A and B play the following game with N counters. A divides the counters into 2 piles, each with at least 2 counters. Then B divides each pile into 2 piles, each with at least one counter. B then takes 2 piles according to a rule which both of them know, and A takes the remaining 2 piles. Both A and B make their choices in order to end up with as many counters as possible. There are 3 possibilities for the rule: R1 B takes the biggest heap (or one of them if there is more than one) and the smallest heap (or one of them if there is more than one). R2 B takes the two middling heaps (the two heaps that A would take under R1 ). R3 B has the choice of taking either the biggest and smallest, or the two middling heaps. For each rule, how many counters will A get if both players play optimally? Solution
s: [N/2], [(N+1)/2], [N/2]. Suppose A leaves piles n, m with n≤m. Under R1 , B can certainly secure m by dividing the larger pile into 1 and m-1. He cannot do better, because if b is the biggest of the 4 piles, then the smallest is at most m-b. Hence A's best strategy is to leave [N/2], [(N+1)/2]. Under R2 , if A leaves a=2, b=N-2, then B cannot do better than [N/2], because if he divides the larger pile into a,b with a≤b, then he takes a+1. A cannot do better, because if he leaves a,b with 3≤a≤b, then B can divide to leave 1, a-1, [b/2], [(b+1)/2]. Now if a-1≥[(b+1)/2], then B takes b≥[(N+1)/2]. If a- 1<[(b+1)/2], then B takes a-1+[b/2]. But a-1≥2 and [b/2]≥[(b+1)/2]-1, so a-1+[b/2]≥1+[(b+1)/2], or B takes at least as many as A, so B takes at least [(N+1)/2]. Under R3 , A's best strategy is to divide into [N/2],[(N+1)/2]. We have already shown that B can secure [(N+1)/2] and no more by following R1 . He cannot do better under R2, for if he divides so that the biggest pile comes from [N/2], then the smallest does too and so he gets [(N+1)/2]. If he divides so that the biggest and smallest piles come from [(N+1)/2], then he gets only [N/2]. But one of these must apply, because if he divided so that the smaller from [N/2] was smaller than the smaller from [(N+1)/2], and the bigger from [N/2] was smaller than the bigger from [(N+1)/2], then [N/2] would be at least 2 less than [(N+1)/2] (which it is not). 1st ASU 1961 © John Scholes jscholes@kalva.demon.co.uk 15 Sep 1998