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
David-Vieta
24.03.2024 13:56
$n$
distribute candies to $1,3,5,\cdots ,4n-1$
Then for every adjacent candies, Bob can only choose one.
We will prove a stronger conclusion by substituting $2n$ candies With $2t,0\le t\le n$, and Bob can take $t$ candies however Alice‘s strategy is.
We use induction on $n$.
Basis step: $n=1,2$, the precise process is left as an exercise to the reader.
Inductive step: We call a box without candies mine, then Bob’s issue is to escape as many mines as possible, more accurately, at least one in two.
If there are $0,2,4$ mines in $1,2,3,4$, induction will kill this.
If the mine distribution is redundant like $1,2,4$,etc., then Bob can only touch one mine.
So what’s left to us are only the cases of $1,3,4$ and $4$. Now we shift our attention to $12345678$. If the number of mine in $5678$ is odd, then by induction the conclusion follows. Now suppose the number of mine in $5678$ is even. Then there must exist a strategy like $1,2,5,8$ and $3,6,7,8$ for Bob to escape at least half of the mine, by induction the result follows.
sami1618
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
Case 1: $j=2$
Take $C_1=\{B_1,B_4,B_5,B_8\}$ and $C_2=\{B_3,B_6,B_7,B_8\}$.
Case 2: $j=4$
Take $C_1=\{B_1,B_2,B_5,B_8\}$ and $C_2=\{B_3,B_6,B_7,B_8\}$.
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$.