Copied from my post on Codeforces:
In CodeChef’s June Lunchtime contest today, there was a problem called Gold Mining, which I’ll summarise here:
There are a N gold mines, and the i th one has G_i units of gold in it. Chef and Chefu can extract gold from the mines at a constant rate. For the i th mine, Chef can extract P_i units of gold per unit of time, and Chefu can extract Q_i units of gold per unit of time. Note that time is continuous here, not discrete. Chef and Chefu each can extract gold from one mine at a time, and they can instantaneously move from one mine to another at any point in time. Chef always know where Chefu is, and Chefu always know where Chef is. Chef and Chefu are always trying to maximize the total amount of gold they get themselves. The task is to predict the total amount of gold which Chef will mine and the total amount of gold which Chefu will mine if Chef and Chefu act optimally.
The solution in the editorial goes like this:
Let X = \sum_i G_i P_i / (P_i + Q_i) and Y = \sum_i G_i Q_i / (P_i + Q_i). X and Y are the amounts of gold which Chef and Chefu will get if they are always in the same mine. Clearly, the sum of the amount of gold which Chef and Chefu will mine is equal to the total amount of gold in the mines. Assume that Chef and Chefu are in different mines at some point. If Chef will get at least X units of gold continuing in this state, then Chefu will get no more than Y units of gold this way. Therefore, it is always optimal for Chefu to move to the mine which Chef is in so that Chefu gets Y units of gold and Chef gets X units of gold. Similarly, if Chef will get no more than X units of gold continuing in this state, then it will be optimal for Chef to move to the mine which Chefu is in so that Chef gets X units of gold and Chefu gets Y units of gold. Therefore, if both Chef and Chefu act optimally, they will always be in the same mine, and the answers are X and Y.
I believe that this proof is invalid, and I will now attempt to demonstrate why. First of all, I’ll state how I’m interpreting the editorial’s proof a bit more formally:
Assume that at some time t, Chef and Chefu are in different mines. Let X' and Y' be the amount of gold which Chef and Chefu will get respectively if Chef and Chefu do not move into the same mine at time t. If X' \geq X, then Y' \leq Y, therefore it is optimal for Chefu to move into the mine that Chef is in, because Chefu will then be able to get Y gold instead of Y' gold. If X' \leq X, then it is optimal for Chef to move to the mine which Chefu is in so that he can get X gold instead of X' gold. Therefore, the optimal strategy for both Chef and Chefu is to always be in the mine which the other person is in, and they will get X and Y gold.
This proof assumes that if Chef and Chefu move into the same mine at time t, then they will get X and Y units of gold. However, the problem is that Chef and Chefu can still move to a different mine afterwards in the same instant. Let’s say at time t, X' \leq X so Chef moves into the mine which Chefu is in. The proof assumes that this will result in Chef getting X gold and does not rule out the possibility that Chefu can move to a different mine in the same instant. In fact, the claim that it is always optimal for Chefu to not move to another mine immediately after Chef moves is the exact same as the statement that is supposedly proved, because the positions of Chef and Chefu at a given instant doesn’t actually matter. We all know that the proof of the statement can’t contain the assumption that the statement is true.
To think about it another way, the proof in the editorial is claiming that Chef can ensure that he is always in the same mine as Chefu, because he can move into the mine which Chefu is in at any moment. However, using the same logic we can conclude that as long as there are at least two nonempty mines, Chefu can ensure that he is always in a different mine than Chef by moving as soon as Chef moves into his mine. As far as I can tell, if Chef and Chefu are in different mines for any nonzero amount of time, the outcome would change.
So this is why I believe the proof in the editorial for this problem is invalid. I suspect that this problem is actually unsolvable, just like how it makes no sense to try to predict the outcome of a game where one player wants to make a bit 1, the other player wants to make it 0, and both players can instantaneously flip the bit at any moment. I haven’t been able to find a rigorous proof of this though. I’m not sure how to even define “optimal” for this problem. What do you think about this? If anyone has a rigorous proof, please share it.
Update: So if Chef and Chefu have some “reaction time” then it can be proven that the outcome approaches X and Y as the reaction time approaches 0. I don’t think that necessarily indicates that there is a defined outcome when the reaction time is exactly 0 though.