Russian 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=[(b+1)/2], then B takes b>=[(N+1)/2]. If 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). Russian 1-10 (C) John Scholes jscholes@kalva.demon.co.uk 15 Sep 1998