Loading [MathJax]/jax/output/SVG/jax.js

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


n3 натурал саны берілген. Тақтаға 1 саны n рет жазылған. Тақтаның астында екі қорап тұр. Бастапқыда олар бос. Жүріс келесі қадамдардан тұрады: тақтадан екі a және b сандары өшіріледі, олардың орнына 1 және a+b сандары жазылады, сосын бірінші қорапқа бір тас, ал екінші қорапқа ЕҮОБ(a,b) тас салынады. Бірнеше жүрістен кейін бірінші қорапта s тас, екіншісінде t тас болған. ts қатынасының барлық мүмкін мәндерін табыңыз.
посмотреть в олимпиаде

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

  0
1 года 5 месяца назад #

Сначала мы покажем, что отношения ts можно сделать сколь угодно близкими к n1 , а с помощью некоторых дополнительных шагов мы можем достичь любого рационального числа в [1,n1)

Для n2 назовите Pn процедуру, которая переводит n сегментов из состояния (1,1,1,...,1) в состояние (1,1,1,...,1,2k) для некоторого k и, следовательно, добавляет 2k1 к s и добавляет (n1)2kqn(k) к t для некоторого многочлена qn степени n2.

Для n=2 это очевидный (1,1)(1,2)...(1,2k) и q2=1 . Строим Pn индуктивно, при наличии n сегментов в начальном состоянии выполните следующие действия: (1,1,...,1,1)(1,1,...1,2)(1,1,...,2,2)(1,1,...,1,4).....(1,1,...,1,2k1))(выполнить процедуру Pn1 на первых n1 сегментах)

(1,1,...,2k1,2k1)(1,1,...,1,2k)

Легко видеть, что всего мы добавили 2k1 к s и k1m=0(n2)2mqn1(m)+2m=(n1)2kqn(k) до t.

Отношение (n1)2kqn(k)2k1 явно стремится к n1.Теперь мы покажем, что это отношение всегда меньше n1. Обратите внимание, что (a,b)min(a,b) . Вместо того, чтобы брать два ведра, складывать камни из одного в другое, а затем добавлять камень на 1 в первое,

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

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

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

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

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