Initially, a pair of numbers $(1,1)$ is written on the board. If for some $x$ and $y$ one of the pairs $(x, y-1)$ and $(x+y, y+1)$ is written on the board, then you can add the other one. Similarly for $(x, xy)$ and $(\frac {1} {x}, y)$. Prove that for each pair that appears on the board, its first number will be positive.
Problem
Source: All-Russian 2022 10.3
Tags: algebra
R8kt
20.04.2022 02:32
Notice that from the pair (a, b) we can move to 3 different pairs: 1.(a+b+1, b+2) 2.(a-b+1, b-2) 3. (1/a, b/a) Define a quantity for each pair f(a, b) = a - b^2/4 Notice that f(a+b+1, b+2) = f(a, b) = f(a-b+1, b-2), and f(1/a, b/a) = 1/a - b^2/(4a^2) = (a - b^2/4)/a^2 = f(a, b)/a^2. So now we see, that all 3 of these pairs have the same “positives” of the assigned quantity (if the quantity was positive, then it will always stay positive). Because at the start we had f(1, 1) = 3/4. For every pair (a, b) that we can reach, we have f(a, b) > 0. This means a-b^2/4 > 0 which implies that a >0.
TheStrayCat
20.04.2022 04:35
A more generic statement that can be easily proved by induction is that for any $a, b \in \mathbb{R}$ the expression $a^2x+aby+b^2$ is strictly positive, where $(x,y)$ is an arbitrary pair that can ever appear on the board. Substituting $a=1$ and $b=0$ gives us the result we need.