Maths Olympiad Prep

Library / /188 of 196

Combinatorics Difficulty 6.8 National Olympiad Prove it Soviet Union

Problem:
A and BB play the following game with NN counters. AA divides the counters into 22 piles, each with at least 22 counters. Then BB divides each pile into 22 piles, each with at least one counter. BB then takes 22 piles according to a rule which both of them know, and AA takes the remaining 22 piles. Both AA and BB make their choices in order to end up with as many counters as possible. There are 33 possibilities for the rule:

R1R1 BB 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).

R2R2 BB takes the two middling heaps (the two heaps that AA would take under R1R1).

R3R3 BB has the choice of taking either the biggest and smallest, or the two middling heaps. For each rule, how many counters will AA get if both players play optimally?

Solution

Solution:
Answers: [N/2][N/2], [(N+1)/2][(N+1)/2], [N/2][N/2].

Suppose AA leaves piles nn, mm with nmn \leq m.

Under R1R1, BB can certainly secure mm by dividing the larger pile into 11 and m1m-1. He cannot do better, because if bb is the biggest of the 44 piles, then the smallest is at most mbm-b. Hence AA's best strategy is to leave [N/2][N/2], [(N+1)/2][(N+1)/2].

Under R2R2, if AA leaves a=2a=2, b=N2b=N-2, then BB cannot do better than [N/2][N/2], because if he divides the larger pile into aa, bb with aba \leq b, then he takes a+1a+1. AA cannot do better, because if he leaves aa, bb with 3ab3 \leq a \leq b, then BB can divide to leave 11, a1a-1, [b/2][b/2], [(b+1)/2][(b+1)/2]. Now if a1[(b+1)/2]a-1 \geq [(b+1)/2], then BB takes b[(N+1)/2]b \geq [(N+1)/2]. If a1<[(b+1)/2]a-1 < [(b+1)/2], then BB takes a1+[b/2]a-1 + [b/2]. But a12a-1 \geq 2 and [b/2][(b+1)/2]1[b/2] \geq [(b+1)/2] - 1, so a1+[b/2]1+[(b+1)/2]a-1 + [b/2] \geq 1 + [(b+1)/2], or BB takes at least as many as AA, so BB takes at least [(N+1)/2][(N+1)/2].

Under R3R3, AA's best strategy is to divide into [N/2][N/2], [(N+1)/2][(N+1)/2]. We have already shown that BB can secure [(N+1)/2][(N+1)/2] and no more by following R1R1. He cannot do better under R2R2, for if he divides so that the biggest pile comes from [N/2][N/2], then the smallest does too and so he gets [(N+1)/2][(N+1)/2]. If he divides so that the biggest and smallest piles come from [(N+1)/2][(N+1)/2], then he gets only [N/2][N/2]. But one of these must apply, because if he divided so that the smaller from [N/2][N/2] was smaller than the smaller from [(N+1)/2][(N+1)/2], and the bigger from [N/2][N/2] was smaller than the bigger from [(N+1)/2][(N+1)/2], then [N/2][N/2] would be at least 22 less than [(N+1)/2][(N+1)/2] (which it is not).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.