For a positive integer $n(\geq 2)$, there are $2n$ candies. Alice distributes $2n$ candies into $4n$ boxes $B_1, B_2, \dots, B_{4n}.$ Bob checks the number of candies that Alice puts in each box. After this, Bob chooses exactly $2n$ boxes $B_{k_1}, B_{k_2}, \dots, B_{k_{2n}}$ out of $4n$ boxes that satisfy the following condition, and takes all the candies. (Condition) $k_i - k_{i - 1}$ is either $1$ or $3$ for each $i = 1, 2, \dots, 2n$, and $k_{2n} = 4n$. ($k_0 = 0$) Alice takes all the candies in the $2n$ boxes that Bob did not choose. If Alice and Bob both use their best strategy to take as many candies as possible, how many candies can Alice take?
Problem
Source: FKMO 2024 P2
Tags: combinatorics
24.03.2024 13:56
20.06.2024 00:47
Answer: n Alice's Strategy: Alice can place candies in all boxes with odd indices. Notice that $k_{i}$ and $k_{i+1}$ can not both be odd so Bob can acquire at most $n$ candies. Bob's Strategy: One of the boxes, say $B_j$, out of $B_2,B_4,\dots, B_{4n-2}$ must contain no candies. If each of these boxes did contain a candy then Alice has a strategy to acquire $n$ of them. We make the following claim which is sufficient. Claim: There exists two choices $C_1$ and $C_2$ such that $B_1,B_2,\dots, B_{4n-1}/B_j$ are each chosen in one of them
Now assume we are moving from $n\mapsto n+1$. Assume $C_1$ chooses $B_{4n-1}$, then simply consider $C_1\cup \{B_{4n+2},B_{4n+3},B_{4n+4}\}/\{B_{4n-1}\}\mapsto C_1$ and $C_2 \cup \{B_{4n+1},B_{4n}\}\mapsto C_2$.