CombinatoricsDifficulty 7.7National Olympiad, round 2Prove itHong Kong
There are 2n cards labelled 1,2,…,2n respectively, where n is a positive integer. Two players A and B take turns choosing a card which has not been chosen by anyone, with A going first, until all cards are chosen. Let a1,a2,…,an be the labels of the cards chosen by A in this order, and let b1,b2,…,bn be the labels of the cards chosen by B in this order. The score of A is equal to (a1+a2+⋯+an)2+(b1+b2+⋯+bn)2−(a1b1+a2b2+⋯+anbn). What is the maximum score (in terms of n) that A can guarantee to obtain regardless of how B plays?
Solution
The answer is N:=(k=1∑n2k)2+(k=1∑n(2k−1))2−k=1∑n(2k−1)(2k)=n2(n+1)2+n4−(32n(n+1)(2n+1)−n(n+1))=3n(6n3+2n2+1)
Proof. Since there are finitely many possible ways to assign the values, T must attain a maximum value. For this maximal case, we may assume ai<bi for each i. Note that we may assume {ai} and {bi} are increasing by the rearrangement inequality.
Under these assumptions, we must have a1=1. We are going to show that ai=2i−1 and bi=2i for all i. Suppose on the contrary that this does not hold. Then there is a smallest index k such that bk=2k. Note that we must have ai=2i−1 for i=1,2,…,k and ak+1=2k (clearly k=n). This implies ak<ak+1<bk<bk+1. By the rearrangement inequality, we have akbk+bk+1ak+1<akak+1+bk+1bk. This means we can swap bk and ak+1 to increase the value of T, contradiction.
Therefore, T is maximized when ai=2i−1 and bi=2i for all i. This proves the claim. □
Now, we show that A can guarantee to obtain score N. A strategy is to choose the card with the largest label in each round. Note that ai≥2(n+1−i) for each i since at least one of the cards 2(n+1−i),2(n+1−i)+1,…,2n is not chosen in the ith round. As X+Y=1+2+⋯+2n is fixed and X>Y (because of this strategy), S is smaller when X is smaller. Thus, S≥(2+4+⋯+2n)2+(1+3+⋯+(2n−1))2. Together with the claim, we deduce S−T≥(k=1∑n2k)2+(k=1∑n(2k−1))2−k=1∑n(2k−1)(2k)=N as desired.
Next, we show that B can guarantee that the score of A is at most N. A strategy is to pair up the cards with labels 2m−1 and 2m for each m=1,2,…,n, and choose a card in the same pair as the card just chosen by A in each round. It is easy to see that T=1⋅2+3⋅4+⋯+(2n−1)(2n). Also, as ∣ai−bi∣=1 for each i, we have S=X2+Y2=2(X+Y)2+(X−Y)2=21(1+2+⋯+2n)2+(i=1∑n(ai−bi))2≤2(1+2+⋯+2n)2+n2
Equality holds when ai−bi=1 for all i or ai−bi=−1 for all i. This is exactly the case when S−T=(k=1∑n2k)2+(k=1∑n(2k−1))2−k=1∑n(2k−1)(2k)=N. The proof is complete.
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 reproduced verbatim; metadata (topic, difficulty) added by this project.