Европейская математическая олимпиада среди девочек (EGMO). 2024 год. Грузия

На доске записаны два различных целых числа $u$ и $v$. Мы выполняем последовательность шагов. На каждом шаге мы выполняем одну из следующих двух операций:
   (i) Если $a$, $b$ — это два различных числа, записанных на доске, то мы можем написать на доске число $a+b$, если этого числа еще нет на доске.
   (ii) Если $a$, $b$, $c$ — это три попарно различных числа, записанных на доске, и если целое число $x$ удовлетворяет условию $ax^2 + bx + c = 0$, то можно написать на доске число $x$, если этого числа еще нет на доске.
   Определите все пары начальных чисел $(u, v)$, с помощью которых любое целое число в конце концов может быть записано на доске после конечной последовательности шагов.

Комментарий/решение

Answer: Все пары $(u,v)$ , где $u,v \ne 0$ , $ \{u,v\} \ne \{1,-1\} $ и хотя бы одно из чисел $u,v >0$

Если $u = 0$ то с помощью операций $(i)$ можем записать только $0+v = v$ что уже есть на доске а операцию $(ii)$ использовать не можем так как у нас максимум $2$ различных числа

Если $ \{u,v\} = \{1,-1\} $ то с помощью операций $(i)$ можем записать только $1-1= 0$ потом с помощью операций $(i)$ мы ничего нового не сможем написать, а используя операция $(ii)$ мы сможем записать только числа $1,-1,0$ Но при $ \{u,v\} = \{n,-n\} ($ $n \ne 1$) записав число $n-n= 0$ и взяв $(a,b,c) = (0,n,-n)$ можем записать число $1$

Если оба $u,v<0$ то с помощью операций $(i)$ мы не можем записать положительное число, допустим что используя операцию $(ii)$ можем получить положительное число $n$ тогда $an^2 + bn + c = 0 $ но $an^2,bn,c < 0$ Противоречие.

Claim 1: Если на доске написано число $1$ и любое другое натуральное число ($ \ne 0$), то мы можем в конце концов записать любое целое число.

Док-во: Пусть на доске есть число $1$ и $n$ , $n \in \mathbb{N}$ ,тогда очевидно мы можем записать числа $n+1,n+2,n+3,.....$ то есть все натуральные числа $ \geq n+1$ , тогда возьмем числа $(a,b,c) = (1,2(n+1),(n+1)^2)$ очевидно что они не равны и не меньше чем $n$, тогда можем записать число $\dfrac{-2(n+1) \pm \sqrt{4(n+1)^2-4(n+1)^2}}{2} = -(n+1)$ и просто прибавляя 1 получим числа $-(n+1) , -n ,........-1,0$ Далее прибавляя $-1$ к $-(n+1)$ получим все отрицательные целые числа.

Claim 2: Если записаны числа $u,v$ то мы можем записать числа $-u , -v.$

Док-во: Мы можем записать числа вида $xu + yv$, где $x,y \in \mathbb{N}$ и пусть $u>0$ тогда возьмем

$(a,b,c) = (u+v,4u(u+v),4u^2(u+v))$ очевидно они не не равны, запишем число $\dfrac{-4u(u+v) \pm \sqrt{16u^2(u+v)^2-16u^2(u+v)^2}}{2(u+v)} = -2u$, и запишем $ -2u +u=-u$, аналогично можем записать и $-v$

Conclusion: По Теорему Безу $\exists m,n \in \mathbb{Z}$ такие что $mu + nv = gcd(u,v)$, тогда аналогично продолжая получим что в конце концов по Алгоритму Эвклида можно записать число $1$, откуда можно записать все целые числа.