Азиатско-Тихоокеанская математическая олимпиада, 2020 год

Дано натуральное число $n\geq 3$. Число 1 выписано $n$ раз на доске. Под доской стоят две коробки, изначально они пустые. Ход состоит в следующем: с доски стираются два числа $a$ и $b$, вместо них записываются числа $1$ и $a+b$, в первую коробку добавляют 1 камень, а во вторую коробку добавляют НОД$(a,b)$ камней. После нескольких ходов в первой коробке оказалось $s$ камней, а во второй коробке — $t$ камней. Найдите все возможные значения отношения $\dfrac{t}{s}$.

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

Сначала мы покажем, что отношения $\frac{t}{s}$ можно сделать сколь угодно близкими к $n-1$ , а с помощью некоторых дополнительных шагов мы можем достичь любого рационального числа в $[1,n-1)$

Для $n\ge 2$ назовите $P_n$ процедуру, которая переводит $n$ сегментов из состояния $(1,1,1,...,1)$ в состояние $(1,1,1,..., 1,2^k)$ для некоторого $k$ и, следовательно, добавляет $2^k-1$ к $s$ и добавляет $(n-1)2^k-q_n(k)$ к $t$ для некоторого многочлена $q_n$ степени $n-2$.

Для $n=2$ это очевидный $(1,1)\to (1,2) \to...\to(1,2^k)$ и $q_2=1$ . Строим $P_n$ индуктивно, при наличии $n$ сегментов в начальном состоянии выполните следующие действия: $(1,1,...,1,1)\to (1,1,...1,2)\to (1,1 ,...,2,2)\to (1,1,...,1,4) \to .....\to (1,1,...,1,2^{k-1) })\to$(выполнить процедуру $P_{n-1}$ на первых $n-1$ сегментах)

$\to (1,1,...,2^{k-1},2^{k-1}) \to (1,1,...,1,2^k)$

Легко видеть, что всего мы добавили $2^k-1$ к $s$ и $\sum_{m=0}^{k-1}(n-2)2^{m}-q_{n- 1}(m)+2^m=(n-1)2^k-q_n(k)$ до $t$.

Отношение $\frac{(n-1)2^k-q_n(k)}{2^k-1}$ явно стремится к $n-1$.Теперь мы покажем, что это отношение всегда меньше $n-1$. Обратите внимание, что $(a,b)\le min(a,b)$ . Вместо того, чтобы брать два ведра, складывать камни из одного в другое, а затем добавлять камень на $1$ в первое,

$(1)$ мы перемещаем $1$ камня за раз из ведра с $a$ камнями в ведро с $b$ камнями только если $a\le b$ и можем в любой момент

$(2)$ возьмите камень стоимостью $1$ из бесконечного запаса камней и добавьте его в любое ведро.

Перемещение $(1)$ добавляет $1$ к $t$, тогда как перемещение $(2)$ добавляет $1$ к $s$, что по сути представляет собой общее количество камней минус $n$.

Состояние $m$ ведра $i$ с камнями $a_i$ (а тем более состояние этих камней) — это размер максимальной строго возрастающей последовательности других ведер с $b_1<...<b_m<a_i$, имеющей появился . Вначале все сегменты находятся в основном состоянии $0$ и могут достичь любого состояния $0,1,2,...,n-1$ .

Если игра ведется таким образом, что камни только увеличивают свое состояние за ход, то мы закончили, потому что тогда каждый камень будет двигаться не более $n-1$ раз, что означает, что общее количество ходов меньше $n- 1$, умноженный на общее количество камней. Мы можем обеспечить это, наложив следующее: если ведро $i$ в какой-то момент имеет больше камней, чем другое ведро $j$ (и более высокое состояние), то $B_j$ имеет более высокий приоритет, чем $B_i$, для получения камней (поэтому, если в какое-то время $|B