Maths Olympiad Prep

Library / /387 of 520

Combinatorics Difficulty 6.9 National olympiad Prove it

Julian and Johan are playing a game with an even number, say 2n2 n, of cards ( nZ>0n \in \mathbb{Z}_{>0} ). On each card, there is a positive integer. The cards are shuffled and laid out in a row on the table with the numbers visible. A player whose turn it is may take either the leftmost card or the rightmost card. The players take turns alternately.
Johan starts, so Julian picks the last card. Johan's score is the sum of the numbers on the nn cards he has picked, and the same goes for Julian. Prove that Johan can always achieve a score that is at least as high as Julian's.

Solution

Let 2n2 n be the number of cards and assume that the cards are arranged in a row as a1,a2,,a2na_{1}, a_{2}, \ldots, a_{2 n}. We prove by induction on nn that Johan can always ensure that he picks either all the odd cards a1,a3,a5,a_{1}, a_{3}, a_{5}, \ldots or all the even cards a2,a4,a6,a_{2}, a_{4}, a_{6}, \ldots For n=1n=1, Johan picks card a1a_{1} if he wants the odd cards and card a2a_{2} if he wants the even cards. Suppose we have proven it for some nn. Consider the cards a1a_{1}, a2,,a2n+2a_{2}, \ldots, a_{2 n+2}. If Johan wants the odd cards, he picks a1a_{1} first. Julian then picks either a2a_{2} or a2n+2a_{2 n+2}. After that, the remaining row is b1,b2,,b2nb_{1}, b_{2}, \ldots, b_{2 n}. In the first case, bi=ai+2b_{i}=a_{i+2} for all ii, and according to the induction hypothesis, Johan can get all the odd bib_{i}, which together with card a1a_{1} gives him all the odd cards. In the second case, bi=ai+1b_{i}=a_{i+1} for all ii, and according to the induction hypothesis, Johan can get all the even bib_{i}, which together with card a1a_{1} gives him all the odd cards. Therefore, Johan can ensure that he gets all the odd cards. Similarly, he can also ensure that he gets all the even cards. This completes the induction. Johan can now ensure that he scores at least as many points as Julian in the following way: if the sum of the numbers on the odd cards is at least as large as the sum of the numbers on the even cards, he chooses all the odd cards. Otherwise, he chooses all the even cards.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.