There are $100$ piles of $400$ stones each. At every move, Pete chooses two piles, removes one stone from each of them, and is awarded the number of points, equal to the non- negative difference between the numbers of stones in two new piles. Pete has to remove all stones. What is the greatest total score Pete can get, if his initial score is $0$? (Maxim Didin)
Problem
Source: Tournament of Towns, Junior A-Level , Spring 2019 p7
Tags: game, combinatorics, game strategy
gravel
10.09.2022 14:06
The answer is 98*200*200
For each pile label the stone at the bottom 1, the second from the bottom 2, ... until the top stone which is labeled 400. Each time Peter makes a move he earns |x-y| where x and y are the labels of the stones on top of the two piles he has chosen.
Peter's total score is equal to the sum of all larger labels in each of his pairings minus the sum of all smaller labels. As Peter adds one label to each group with each move they end equal in size. This establishes the upper bound of 100*(201+202+...400) - 100*(1+2+...200) = 100*200*200, because the best he can do is to have all of the larger than median labels in the big group and all of the smaller than median labels in the small group.
This upper bound is not achievable though. To see why, we argue that we can keep a consistent ordering of the piles and the larger than median labels in the smallest pile must be in the small group while the smaller than median labels of the largest pile must be in the large group.
To see how to keep the labeling, label the piles arbitrarily to begin with. Then if Peter would ever make a move such that piles i,j where i>j would have numbers of stones s_i < s_j then before the move s_i = s_j and Peter must have chosen only pile i in that move. We can pretend that Peter instead selected pile j and the resulting multi-set of pile sizes is the same as it would be with Peter's initial choice of pile i. In this way we can change some of Peter's pile selections but preserve the score of his strategy and the relative ordering of pile sizes.
As pile 1 is always smaller than the other pile when it is played and pile 100 is always greater we see that the best we can do is 99*(201+...+400)+(1+2+...200) - (99*(1+2+...+200) + 201+202+...400) = 98*(201+202+...400) - 98*(1+2+...200) = 98*200*200.
To show that this is achievable, Peter may choose piles 1 and 2 200 times consecutively to begin then he may choose a pile with 200 and a pile with 400 and play the larger pile and the smaller pile 200 times consecutively until he ends up with 2 piles of size 200 and then play those two piles 200 times consecutively. He will choose 98 pairs of piles of size 200/400 earning 200*200 points from each such pair and 0 points from piles 1,2 and 99,100. He thus earns 98*200*200 points establishing the optimality of that bound.