Maths Olympiad Prep

Library / /3 of 3

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Hong Kong

There are 2n2n cards labelled 1,2,,2n1, 2, \ldots, 2n respectively, where nn is a positive integer. Two players AA and BB take turns choosing a card which has not been chosen by anyone, with AA going first, until all cards are chosen. Let a1,a2,,ana_1, a_2, \ldots, a_n be the labels of the cards chosen by AA in this order, and let b1,b2,,bnb_1, b_2, \ldots, b_n be the labels of the cards chosen by BB in this order. The score of AA is equal to
(a1+a2++an)2+(b1+b2++bn)2(a1b1+a2b2++anbn). (a_1 + a_2 + \dots + a_n)^2 + (b_1 + b_2 + \dots + b_n)^2 - (a_1b_1 + a_2b_2 + \dots + a_nb_n).
What is the maximum score (in terms of nn) that AA can guarantee to obtain regardless of how BB plays?

Solution

The answer is
N:=(k=1n2k)2+(k=1n(2k1))2k=1n(2k1)(2k)=n2(n+1)2+n4(2n(n+1)(2n+1)3n(n+1))=n(6n3+2n2+1)3 \begin{aligned} N &:= \left( \sum_{k=1}^{n} 2k \right)^2 + \left( \sum_{k=1}^{n} (2k-1) \right)^2 - \sum_{k=1}^{n} (2k-1)(2k) \\ &= n^2(n+1)^2 + n^4 - \left( \frac{2n(n+1)(2n+1)}{3} - n(n+1) \right) \\ &= \frac{n(6n^3 + 2n^2 + 1)}{3} \end{aligned}

Denote
X=a1+a2++an,X = a_1 + a_2 + \cdots + a_n,
Y=b1+b2++bn,Y = b_1 + b_2 + \cdots + b_n,
S=X2+Y2,S = X^2 + Y^2,
T=a1b1+a2b2++anbn.T = a_1 b_1 + a_2 b_2 + \cdots + a_n b_n.

Claim. T12+34++(2n1)(2n)T \le 1 \cdot 2 + 3 \cdot 4 + \cdots + (2n-1)(2n)

Proof. Since there are finitely many possible ways to assign the values, TT must attain a maximum value. For this maximal case, we may assume ai<bia_i < b_i for each ii. Note that we may assume {ai}\{a_i\} and {bi}\{b_i\} are increasing by the rearrangement inequality.

Under these assumptions, we must have a1=1a_1 = 1. We are going to show that ai=2i1a_i = 2i - 1 and bi=2ib_i = 2i for all ii. Suppose on the contrary that this does not hold. Then there is a smallest index kk such that bk2kb_k \neq 2k. Note that we must have ai=2i1a_i = 2i - 1 for i=1,2,,ki = 1, 2, \dots, k and ak+1=2ka_{k+1} = 2k (clearly knk \neq n). This implies ak<ak+1<bk<bk+1a_k < a_{k+1} < b_k < b_{k+1}. By the rearrangement inequality, we have
akbk+bk+1ak+1<akak+1+bk+1bk. a_k b_k + b_{k+1} a_{k+1} < a_k a_{k+1} + b_{k+1} b_k.
This means we can swap bkb_k and ak+1a_{k+1} to increase the value of TT, contradiction.

Therefore, TT is maximized when ai=2i1a_i = 2i - 1 and bi=2ib_i = 2i for all ii. This proves the claim. \square

Now, we show that AA can guarantee to obtain score NN. A strategy is to choose the card with the largest label in each round. Note that ai2(n+1i)a_i \ge 2(n+1-i) for each ii since at least one of the cards 2(n+1i),2(n+1i)+1,,2n2(n+1-i), 2(n+1-i)+1, \dots, 2n is not chosen in the iith round. As X+Y=1+2++2nX+Y = 1+2+\dots+2n is fixed and X>YX > Y (because of this strategy), SS is smaller when XX is smaller. Thus,
S(2+4++2n)2+(1+3++(2n1))2. S \ge (2+4+\dots+2n)^2 + (1+3+\dots+(2n-1))^2.
Together with the claim, we deduce
ST(k=1n2k)2+(k=1n(2k1))2k=1n(2k1)(2k)=N S - T \ge \left( \sum_{k=1}^{n} 2k \right)^2 + \left( \sum_{k=1}^{n} (2k-1) \right)^2 - \sum_{k=1}^{n} (2k-1)(2k) = N
as desired.

Next, we show that BB can guarantee that the score of AA is at most NN. A strategy is to pair up the cards with labels 2m12m-1 and 2m2m for each m=1,2,,nm = 1, 2, \dots, n, and choose a card in the same pair as the card just chosen by AA in each round. It is easy to see that
T=12+34++(2n1)(2n). T = 1 \cdot 2 + 3 \cdot 4 + \dots + (2n-1)(2n).
Also, as aibi=1|a_i - b_i| = 1 for each ii, we have
S=X2+Y2=(X+Y)2+(XY)22=12[(1+2++2n)2+(i=1n(aibi))2](1+2++2n)2+n22 \begin{aligned} S &= X^2 + Y^2 = \frac{(X+Y)^2 + (X-Y)^2}{2} \\ &= \frac{1}{2} \left[ (1+2+\dots+2n)^2 + \left( \sum_{i=1}^{n} (a_i - b_i) \right)^2 \right] \\ &\le \frac{(1+2+\dots+2n)^2 + n^2}{2} \end{aligned}

Equality holds when aibi=1a_i - b_i = 1 for all ii or aibi=1a_i - b_i = -1 for all ii. This is exactly the case when
ST=(k=1n2k)2+(k=1n(2k1))2k=1n(2k1)(2k)=N. S-T = \left(\sum_{k=1}^{n} 2k\right)^2 + \left(\sum_{k=1}^{n} (2k-1)\right)^2 - \sum_{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.