Kobar and Borah are playing on a whiteboard with the following rules: They start with two distinct positive integers on the board. On each step, beginning with Kobar, each player takes turns changing the numbers on the board, either from P and Q to 2P−Q and 2Q−P, or from P and Q to 5P−4Q and 5Q−4P. The game ends if a player writes an integer that is not positive. That player is declared to lose, and the opponent is declared the winner. At the beginning of the game, the two numbers on the board are 2024 and A. If it is known that Kobar does not lose on his first move, determine the largest possible value of A so that Borah can win this game.
Problem
Source: Indonesian National Mathematical Olympiad 2024, Problem 4 (Day 1)
Tags: Game Theory, Integers, combinatorics, number theory, Inamo
28.08.2024 10:55
28.08.2024 12:05
Basically similar as above, but more convoluted, due to considering ratio instead of difference lol. Write αi as the ratio of the largest to the smallest among P and Q. Let's just assume P>Q. So, αi+1 is either (2αi−1)/(αi−2) or (5αi−4)/(5−4αi). The winner is the one who is forced to make the value of α greater than 2. Let's write f(x)=(2x−1)/(2−x) and g(x)=(5x−4)/(5−4x). It's easy to see that f and g are increasing functions in the interval (1,+∞). And also, we have the following claim: Claim. f(f(x))=g(x) Proof. Expand. Now, we create a directed graph of real numbers, each edge connecting x↦f(x). Consider the following chain: …41/40↦14/13↦5/4↦2/1.This chain tells us the following: if f(r)≥αi>r>1 for some r in the chain, then in one operation we can either move to the next node or to the node after that (we can make either αi+1∈(f(r),f(f(r))] by applying the first operation, or (f(f(r)),f(f(f(r)))] by applying the second). The winner is the one who moves to the node 2/1. If in the first place α>14/13, Kobar can do the second operation (hence moving twice), making α becomes greater than 2, so he wins. Therefore, we need to have α≤14/13⟹A≤⌊2024∗14/13⌋=2179. To prove 2179 works, note that 14/13≥2179/2024>41/40. So, the game starts from node 41/40. The node 2/1 is three moves away, so Borah can just do the distinct operation done by Kobar in the first step, making the total step equals 3. He wins.
28.08.2024 12:33
Did this by bashing:
29.08.2024 02:34
Can someone verify if this generalization is true? Let L be the smallest positive integer such that |2024−A|3L≥2024+AWe claim that Borah wins if and only if L\equiv 1\pmod{3}. From here we can generate all A such that Borah wins
29.08.2024 03:14
A few observations: 1. You can verify that the second move is basically doing the first move twice. Therefore the game can be viewed as only doing the first move, but players have a choice of doing "two moves at once" 2. The sum of the numbers on the board never changes 3. The difference of the numbers on the board grows 3x after the first move, and 9x after the second move. therefore if the two numbers are too unequal, the first move will guarantee a zero or negative number, let alone the second move. Otherwise, the move (first or second) will make them a little bit more unequal. So given an initial condition, we can calculate how many moves are left before the numbers are too unequal. This is a finite positive numbers (except if A=2024 of course). More specifically, If there is one move left in the game, the next person loses. So 1 is a losing position. If there are 2 moves left in the game, the next person wins (he can take option 1). So 2 is a winning position If there are 3 moves left in the game, the next person wins (he can take option 2). So 3 is a winning position If there are 4 moves left in the game, the next person loses because it can only lead to 2 or 3, both are winning positions. So 4 is a losing position. Generalization, if the number of moves left in the game is 1 \mod 3 then the next person loses. If it's 0,2 \mod 3 then the next person wins. Prove by induction. The fact that Kobar does not lose on his first game puts the upper limit on A. That is A < 4048. The next losing position is 4 moves left, and the final position (right before Kobar's move) is 1 move left, which means the difference is 27 times the original difference. If the final numbers (right before Kobar's move) are x and (A+2024)-x then: 27(A - 2024) = (A+2024-x) - x which means x = 14 \times 2024 -13A and the condition that this is a losing position means that the numbers (x, A+2024-x) has a ratio \geq 2. \frac{A+2024-x}{x} \geq 2A \leq 14/13 \times 2024
29.08.2024 03:38
GreenTea2593 wrote: Can someone verify if this generalization is true? Let L be the smallest positive integer such that |2024-A| 3^L \ge 2024+AWe claim that Borah wins if and only if L\equiv 1\pmod{3}. From here we can generate all A such that Borah wins This almost looks right. Basically L represents the number of moves left, and I think you mean if and only if Kobar wins.
01.09.2024 04:51
This year's cutoff prediction, anyone?
01.09.2024 05:28
somebodyyouusedtoknow wrote: Kobar and Borah are playing on a whiteboard with the following rules: They start with two distinct positive integers on the board. On each step, beginning with Kobar, each player takes turns changing the numbers on the board, either from P and Q to 2P-Q and 2Q-P, or from P and Q to 5P-4Q and 5Q-4P. The game ends if a player writes an integer that is not positive. That player is declared to lose, and the opponent is declared the winner. At the beginning of the game, the two numbers on the board are 2024 and A. If it is known that Kobar does not lose on his first move, determine the largest possible value of A so that Borah can win this game. I will omit, the details so the solution is shortened Claim: We can make the game invariant by the first 2 moves. Proof: Just do exhaustion on where: 1. Kobar do 1st type of move then Us (Borah) do 2nd type of move 2. Kobar do 2nd type of move then Us (Borah) do 1st type of move Simple calculation tells us that both will be resulting 2024 - 13D, where D = A - 2024, assuming A > 2024, since we want to find large A Then, doing simple arithmetic inequality: 2024-13D > 0 \frac{2024}{13}>D 155 \geq D Seeing that 156 \leq D doesn't work is easy by considering case where Kobar do 2nd type of move then case working. Therefore, A \leq 2179