Maths Olympiad Prep

Library / /2 of 3

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it South Korea

Let n(2)n (\ge 2) be a positive integer. Alice distributes 2n2n candies into 4n4n boxes B1,B2,,B4nB_1, B_2, \dots, B_{4n}. After checking the number of candies Alice puts in each box, Bob chooses 2n2n boxes Bk1,Bk2,,Bk2nB_{k_1}, B_{k_2}, \dots, B_{k_{2n}} out of the 4n4n boxes satisfying the following, and then takes all candies in the chosen boxes.
kiki1{1,3} for each i=1,2,,2n, and k2n=4n. (k0=0) k_i - k_{i-1} \in \{1, 3\} \text{ for each } i = 1, 2, \dots, 2n, \text{ and } k_{2n} = 4n.\ (k_0 = 0)
Alice gets all candies in the 2n2n boxes Bob did not choose. If Alice and Bob use their best strategies to take as many candies as possible, how many candies can Alice take?

Solution

The answer is nn.
If Alice puts one candy in each of boxes B1,B2,,B4n1B_1, B_2, \dots, B_{4n-1}, then Bob can choose at most nn out of the 2n2n boxes, so Alice can get exactly nn candies.

Now we prove that Bob can take at least nn candies. Let bib_i be the number of candies Alice puts in BiB_i for i=1,2,,4ni = 1, 2, \dots, 4n.

Suppose there exists m=1,2,,nm = 1, 2, \dots, n such that b4m2<2b_{4m-2} < 2. We consider the following two sequences
pi={1i=11i=2,4,,2m23i=3,5,,2m13i=2m,2m+2,,2n1i=2m+1,2m+3,,2n1,qi={3i=1,3,,2m11i=2,4,,2m23i=2m,2m+2,,2n21i=2m+1,2m+3,,2n11i=2n p_i = \begin{cases} 1 & i=1 \\ 1 & i=2, 4, \dots, 2m-2 \\ 3 & i=3, 5, \dots, 2m-1 \\ 3 & i=2m, 2m+2, \dots, 2n \\ 1 & i=2m+1, 2m+3, \dots, 2n-1 \end{cases}, \quad q_i = \begin{cases} 3 & i=1, 3, \dots, 2m-1 \\ 1 & i=2, 4, \dots, 2m-2 \\ 3 & i=2m, 2m+2, \dots, 2n-2 \\ 1 & i=2m+1, 2m+3, \dots, 2n-1 \\ 1 & i=2n \end{cases}
and let Pi=p1+p2++piP_i = p_1 + p_2 + \dots + p_i and Qi=q1+q2++qiQ_i = q_1 + q_2 + \dots + q_i for i=1,2,,2ni = 1, 2, \dots, 2n. Then, {Pi}i=1,2,,2n\{P_i\}_{i=1,2,\dots,2n} and {Qi}i=1,2,,2n\{Q_i\}_{i=1,2,\dots,2n} satisfy the condition in the problem, and furthermore {P1,P2,,P2n}{Q1,Q2,,Q2n}={1,2,,4n}{4m2}\{P_1, P_2, \dots, P_{2n}\} \cup \{Q_1, Q_2, \dots, Q_{2n}\} = \{1, 2, \dots, 4n\} - \{4m-2\}. So,
i=12n(bPi+bQi)2nb4m22n1 \sum_{i=1}^{2n} (b_{P_i} + b_{Q_i}) \ge 2n - b_{4m-2} \ge 2n - 1
which implies that either i=12nbPi\sum_{i=1}^{2n} b_{P_i} or i=12nbQi\sum_{i=1}^{2n} b_{Q_i} is at least nn, so Bob can take at least nn.

Now we assume that b4m2=2b_{4m-2} = 2 for every m=1,2,,nm = 1, 2, \dots, n. Then, Bob chooses B4k3,B4k2B_{4k-3}, B_{4k-2} for k=1,2,,n1k = 1, 2, \dots, n-1 and B4n3,B4nB_{4n-3}, B_{4n} where Bob takes 2n2(n)2n - 2 (\ge n).

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 and solution reproduced as published; topic and difficulty added by this site.