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

Тақтада екі түрлі бүтін сан $u$ және $v$ жазулы тұр. Біз әр қадамда келесі екі амалдың бірін орындай аламыз:
   (i) Егер $a$ және $b$ — тақтада жазулы екі түрлі сан болса, онда $a+b$ санын жаза аламыз (ол сан жоқ болған жағдайда).
   (ii) Егер $a$, $b$, $c$ — тақтада жазулы үш түрлі сан болса және бүтін $x$ саны $ax^2 + bx + c = 0$ теңдеуінің түбірі болса, әрі $x$ саны тақтада әлі жоқ болса, онда $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$, откуда можно записать все целые числа.