Is the problem GOLMINE invalid?

general
,
1

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.

12 Likes
2

What I understand from the problem is if you know the concept of TIME AND WORK (APTITUDE)…you have to just implement that only.

1 Like
3

I did not got at first place that how chefu will regain Y points. Link
Can someone help me with that.

I asked the editorial writer and i don’t think even his response was correct.

Is there anyone who proved his/her solution ?

2 Likes
4

yes I completely agree with you
and morever

we can argue this way for any other arrangement also(like suppose if chef works in x then chefu works in x+1 then also we can argue the sameway as in the editorial to prove thsi is indeed the correct).So i feel this is a mistake

2 Likes
5

The thing is they keep doing this no one would get anything.Which contradicts that they have to maximize the gold.

6

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.

I don’t understand why this invalidates anything. Let’s say Chef is “behind” Chefu’s movements by some tiny amount of time. By “tiny”, we mean “infinitesimal”, that is, Chef actually isn’t behind at all because everything is instantaneous. So even if it’s somehow optimal for Chefu to try to “escape” Chef, Chef can still manipulate his trailing of Chefu so he spends the same amount of time in each mine as Chefu.

4 Likes
7

How do you prove that no one will get anything? And how does that work when the total sum is constant?

1 Like
8

moves are always instantaneous

9

What I mean by that sentence is that if there is some time t_1 and t_2 such that t_1 < t_2, Chef is in mine i and Chefu is in mine j where i \neq j during the entirety of the time interval between t_1 and t_2, then the outcome would be different than X and Y.

10

but that won’t be happening if they are tailing each other.

11

Yes, I kind of agree with you .I think if we can provide an example test case then we can be sure that this is not optimal

12

Agreed !!

13

Let c be the change in the outcome you’re talking about, then \lim\limits_{(t_2 - t_1) \to 0}{c} = 0. So because of continuity, this makes no difference. The "entirety of the time interval between t_1 and t_2" is nothing.

1 Like
14

That seems to make a bit of sense, but it still feels very wrong for me.

15

I don’t really like it either, to be honest. But I believe one could craft a strong (probably calculus-based) proof for how the continuity doesn’t make a difference. I’m just not the right person to do it.

16

So I’m thinking that if Chef and Chefu has some “reaction time” r, then as r tends to 0 the maximum difference between the time Chef spends in a mine and the time Chefu spends in a mine will approach 0. So we know that a limit for the outcome as the reaction time tends to 0 exists. But then that doesn’t seem to necessarily indicate that there is a defined outcome when r = 0.

1 Like
17

But can’t we apply the same limit argument to show that there is a defined outcome? Any advantage Chefu will get by evading Chef will be of the form c \cdot r, where c is some constant based on the input. This is definitely not indeterminate, and thus tends to 0 as r does.

edit: maybe c is more complex than a constant, as the mines deplete. But it should still be just some function of the input that doesn’t depend on r.

Okay, I agree with you that there may not be a defined outcome. To be honest, my intuition with this weird type of continuity isn’t strong enough to tell. But we also shouldn’t immediately conclude that there isn’t one, unless you can prove so or concretely prove its similarity to the bit problem (or something similar). I’m starting to doubt myself like crazy, so it definitely shouldn’t be me.

Can we get @taran_1407, @kingofnumbers, and/or @chemthan (or someone else, too) to resolve this?

2 Likes
18

I used the bit problem just to illustrate that a game where players can make instantaneous moves at any time may not have a defined outcome. I think it may be similar if we define the outcome as the total time that the bit is 1, after the game continues for some fixed amount of time. One player wants to maximize the outcome and the other player wants to minimize it. The outcome would approach half of the total time as the reaction time approaches 0, but I don’t know if it’s correct to say that the outcome is exactly half the total time when the reaction time is exactly 0.

19

An issue with the bit problem is that there are multiple conflicting ways to define it, too. For example, let r instead be the time that a player must spend between their own moves, rather than as a reaction. As r tends to 0, it models the same game, but the limit evaluates to 1 (because the player who starts off with the bit in their favor can always instantly counter their opponent) (1 meaning 100% of total time). And the way you choose to define r leads to the outcome being \frac{1}{2}.

1 Like
20

the solution will still be uncertain for the second interpretation as say r be infinitesimally small dt say what if i other player changes it at T-dt time .(I am not sure tho i am having trouble properly defining this game)