Julian and Johan are playing a game with an even number, say , of cards ( ). 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 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 be the number of cards and assume that the cards are arranged in a row as . We prove by induction on that Johan can always ensure that he picks either all the odd cards or all the even cards For , Johan picks card if he wants the odd cards and card if he wants the even cards. Suppose we have proven it for some . Consider the cards , . If Johan wants the odd cards, he picks first. Julian then picks either or . After that, the remaining row is . In the first case, for all , and according to the induction hypothesis, Johan can get all the odd , which together with card gives him all the odd cards. In the second case, for all , and according to the induction hypothesis, Johan can get all the even , which together with card 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.