Maths Olympiad Prep

Library / Korean Mathematical Olympiad Final Round /18 of 28

Korean Mathematical Olympiad Final Round

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.
ki−ki−1∈{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,…,B4n−1B_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 b4m−2<2b_{4m-2} < 2. We consider the following two sequences
pi={1i=11i=2,4,…,2m−23i=3,5,…,2m−13i=2m,2m+2,…,2n1i=2m+1,2m+3,…,2n−1,qi={3i=1,3,…,2m−11i=2,4,…,2m−23i=2m,2m+2,…,2n−21i=2m+1,2m+3,…,2n−11i=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}−{4m−2}\{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)≥2n−b4m−2≥2n−1 \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 b4m−2=2b_{4m-2} = 2 for every m=1,2,…,nm = 1, 2, \dots, n. Then, Bob chooses B4k−3,B4k−2B_{4k-3}, B_{4k-2} for k=1,2,…,n−1k = 1, 2, \dots, n-1 and B4n−3,B4nB_{4n-3}, B_{4n} where Bob takes 2n−2(≥n)2n - 2 (\ge n).

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

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