Maths Olympiad Prep

Library / /4 of 4

Combinatorics Difficulty 9.0 Shortlist Prove it Taiwan

Let n5n \ge 5 be a positive integer. There are nn stars with values 1 to nn, respectively. Anya and Becky play a game. Before the game starts, Anya place the nn stars in a row by whatever order she wishes. Then, starting from Becky, each player takes the left-most or right-most star in the row. After all the stars have been taken, the player with the highest total value of stars wins; if their total values are the same, then the game ends in draw. Find all nn such that Becky has a winning strategy.

Solution

The answer is all nn of the form 4k+24k+2. For convenience of discussion, regard the stars from left to right as occupying position 1 through position nn. We discuss the following cases separately.

1. Even nn:
Note that in the case of even nn, Becky can always choose to take all the stars in odd positions (by first taking the star at position 1, and afterwards always taking from the same side as Anya), or take all the stars in even positions (by first taking the star at position nn, and afterwards always taking from the same side as Anya). Let OO be the sum of the values of the stars in odd positions, and EE be the sum of the values of the stars in even positions, then O+E=n(n+1)/2O+E = n(n+1)/2.

- When n=4k+2n = 4k + 2, n(n1)/2n(n-1)/2 is odd, so Becky only needs to choose whichever of OO and EE has the larger sum and take that one.
- When n=4kn = 4k, note that Becky can never lose (because in the worst case she can obtain the same amount as Anya). And if Anya initially arranges the stars as
1,3,5,,4k1,4k,4k2,,2 1, 3, 5, \dots, 4k-1, 4k, 4k-2, \dots, 2
and always takes from the same side as Becky, then in the first kk rounds Anya can guarantee taking a value 2 more than Becky each time, and in the last kk rounds Anya, in the worst case, takes a value only 2 less than Becky each time, so Anya also can never lose, hence the two players draw.

2. Odd nn:
If n=2k1n = 2k-1, Anya only needs to initially place the stars with values 1 through kk in the odd positions, and place the remaining stars in the even positions, and always take from the same side as Becky, then Anya can guarantee taking all the stars from k+1k+1 through 2k12k-1, whose total value is 3k(k1)/23k(k-1)/2, which is greater than the value k(k+1)/2k(k+1)/2 that Becky obtains, so Anya has a winning strategy.

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 translated into English from zh; metadata (topic, difficulty) added by this project.