CombinatoricsDifficulty 7.2National olympiad, round 2Prove itSouth Korea
Let n(≥2) be a positive integer. Alice distributes 2n candies into 4n boxes B1,B2,…,B4n. After checking the number of candies Alice puts in each box, Bob chooses 2n boxes Bk1,Bk2,…,Bk2n out of the 4n 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) Alice gets all candies in the 2n 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 n. If Alice puts one candy in each of boxes B1,B2,…,B4n−1, then Bob can choose at most n out of the 2n boxes, so Alice can get exactly n candies.
Now we prove that Bob can take at least n candies. Let bi be the number of candies Alice puts in Bi for i=1,2,…,4n.
Suppose there exists m=1,2,…,n such that b4m−2<2. We consider the following two sequences pi=⎩⎨⎧11331i=1i=2,4,…,2m−2i=3,5,…,2m−1i=2m,2m+2,…,2ni=2m+1,2m+3,…,2n−1,qi=⎩⎨⎧31311i=1,3,…,2m−1i=2,4,…,2m−2i=2m,2m+2,…,2n−2i=2m+1,2m+3,…,2n−1i=2n and let Pi=p1+p2+⋯+pi and Qi=q1+q2+⋯+qi for i=1,2,…,2n. Then, {Pi}i=1,2,…,2n and {Qi}i=1,2,…,2n satisfy the condition in the problem, and furthermore {P1,P2,…,P2n}∪{Q1,Q2,…,Q2n}={1,2,…,4n}−{4m−2}. So, i=1∑2n(bPi+bQi)≥2n−b4m−2≥2n−1 which implies that either ∑i=12nbPi or ∑i=12nbQi is at least n, so Bob can take at least n.
Now we assume that b4m−2=2 for every m=1,2,…,n. Then, Bob chooses B4k−3,B4k−2 for k=1,2,…,n−1 and B4n−3,B4n where Bob takes 2n−2(≥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.