The problem I'll describe below looks very difficult to me when trying to approach it with common mathematical processes (I'm not very skilled), but I've noted a good relation with physics which allows a good, though only partial, way for a solution. Here's the text:
Two points, P and Q, lie on a positive real plane and their coordinates are Px, Py, Qx and Qy, respectively. Let's define a "step" as it follows:
- The coordinate of P which is greater becomes itself minus the other (for istance if Px > Py then Px becomes Px - Py)
- The other coordinate doubles itself (in the previous case, Py becomes 2*Py)
- The coordinate of Q which is associated with the same axis as the one which was less among the P coordinates becomes (Qx + Qy) / 2 (If Py < Px then Qy changes)
A game consists of a series of steps which ends when Qx = Qy. The problem asks to find this value at the end of the game.
I've written a small python script to better understand the problem and try some initial coordinates:
import random
import time
while True:
result = []
Px, Py = random.choice(range(1, 1001)), random.choice(range(1, 1001))
Qx, Qy = random.choice(range(1, 1001)), random.choice(range(1, 1001))
result.append([Px, Py, Qx, Qy])
while Qx != Qy:
if Px > Py:
Px -= Py
Py += Py
Qy = (Qx+Qy)/2
else:
Py -= Px
Px += Px
Qx = (Qx+Qy)/2
result.append([Px, Py, Qx, Qy])
print(result)
time.sleep(5)
this script prints out a result every 5 seconds (just to avoid a too rapid output outcoming). What I fear is that, for some initial values of the coordinates, the game should go straight forever with the loop in an infinite amount of steps, but the program doesn't because it approximates a certain amount of digits, making a game finish though it shouldn't. However, I know that the final value of Qx (and Qy) is correct because it's possible to find that with a "closed formula" as shown below:
Here is where the physics comes in: we could see Px and Py as two masses of two objects (made of the same material) and Qx and Qy as their respective temperatures. With this interpretation, we could see each step as a transmission of mass between the objects: the coolest one "receives" an amount of mass equal to its own (in fact, the hottest loses it) and comes in contact with it, changing the temperature of the new mass (two times its initial mass) which becomes the arithmetic mean of the starting two.
As the game proceeds, it doesn't matter if the total number of steps is finite or not. We know that the final value of Qx will correspond with the final temperature obtained by mixing the totality of the masses in a whole object, and this is a very known model. The solution is simply:
(Px*Qx + Py*Qy) / (Px + Py)
or, in other words, the weighted mean of the two masses (where weights are temperatures). But it still remains the doubt if it's possible that some games doesn't end at all. What could you suggest me to do?
EDIT 1
In the comments it came out from CyclotomicField that if Px and Py happen to be equal, the game has no apparent continuation. Assuming that the rules remain the same as one of the cases above, we find ourselves in a symmetrical circumstance which actually forces the game to continue indefinitely. The question now is, are there any non-trivial cases of never-ending games?
EDIT 2
I must be a bit misguided not to have noted earlier that the same reason for which a game couldn't finish in the "edge case" described in the previous edit holds for every possible game: since two values cannot become equal when making one of them the arithmetic mean between the two, and given that Qx and Qy are independent from the position of P, unless they start equal they cannot be.
Now I've also grasped in a better way how to think more "mathematically" at this problem. There are two values, once a step one of them becomes their mean, sometimes the first, sometimes the second. It just remains to understand the pattern they follow in order to accomplish that.