Пусть m_n  — наи­мень­шее число, ко­то­рое можно по­лу­чить из n еди­ниц после опе­ра­ций. За­ме­тим, что

при всех Дей­стви­тель­но, как бы мы ни по­лу­чи­ли наи­мень­шее число m_n, оно равно где числа x и y были по­лу­че­ны на преды­ду­щем шаге. Пусть x по­лу­че­но из p еди­ниц ис­ход­но­го на­бо­ра, а y  — из остав­ших­ся еди­ниц. Если или (пред­по­ло­жим для опре­де­лен­но­сти, что то из ис­ход­но­го на­бо­ра p еди­ниц можно было бы по­лу­чить мень­шее число, не за­тра­ги­вая вто­рой набор.

Зна­чит, на по­след­нем шаге можно по­лу­чить число, мень­шее m_n, что про­ти­во­ре­чит опре­де­ле­нию m_n.

До­ка­жем ин­дук­ци­ей по n, что где

a опре­де­ля­ет­ся из усло­вия (то есть При это ра­вен­ство про­ве­ря­ет­ся не­по­сред­ствен­но:

Пред­по­ло­жим, что оно верно для всех где и до­ка­жем его для

Лемма. Наи­мень­шее зна­че­ние вы­ра­же­ния при усло­вии до­сти­га­ет­ся при где обо­зна­че­но [x]  — наи­мень­шее целое число, не мень­шеe x.

До­ка­за­тель­ство. Обо­зна­чим Поль­зу­ясь фор­му­лой для f(n), по­лу­ча­ем где (это про­ве­ря­ет­ся не­по­сред­ствен­но как в слу­чае так и при Из по­лу­чен­ной фор­му­лы для d(n) сле­ду­ет, что по­это­му при

Пусть и Срав­ним зна­че­ния и Их раз­ность равна

Если то а зна­чит,

Итак, если p про­бе­га­ет зна­че­ния от 1 до (то есть не пре­вос­хо­дит q), то сумма не воз­рас­та­ет, а зна­чит, ее наи­мень­шее зна­че­ние до­сти­га­ет­ся при (со­от­вет­ствен­но, Лемма до­ка­за­на.

Из до­ка­зан­ной леммы и пред­по­ло­же­ния ин­дук­ции сле­ду­ет, что

Оста­ет­ся убе­дить­ся, что

Пусть k та­ко­во, что Тогда Если то

Если же то и

то есть в обоих слу­ча­ях имеем

Сле­до­ва­тель­но,

При по­лу­ча­ем и

Ответ:

При­ве­дем дру­гое ре­ше­ние.

Пусть x  — число, по­лу­чив­ше­е­ся после 2018 опе­ра­ций. Про­сле­дим, как было по­лу­че­но это число. Для этого «раз­вер­нем» все опе­ра­ции в об­рат­ном на­прав­ле­нии. При пря­мом при­ме­не­нии опе­ра­ции два числа за­ме­ня­лись одним, по­это­му при об­рат­ном каж­дое число мы будем за­ме­нять на два числа, из ко­то­рых оно было по­лу­че­но (со­хра­няя де­ле­ние на 4):

При этом есть числа, у ко­то­рых нет пред­ше­ствен­ни­ков это еди­ни­цы. Каж­дую еди­ни­цу мы ис­кус­ствен­но пред­ста­вим в виде суммы двух чисел:

(если то с этой еди­ни­цей мы про­де­ла­ем ту же про­це­дуpy). Далее каж­дую сте­пень двой­ки, сто­я­щую в чис­ли­те­ле и по­лу­чен­ную когда-то из еди­ни­цы, мы снова ис­кус­ствен­но пре­вра­ща­ем в сумму двух чисел:

Таким об­ра­зом, при каж­дом таком «раз­во­ра­чи­ва­нии» опе­ра­ции в об­рат­ном на­прав­ле­нии ко­ли­че­ство чисел удва­и­ва­ет­ся. По­это­му в итоге мы по­лу­чим пред­став­ле­ние числа x в виде дроби, в чис­ли­те­ле ко­то­рой стоит сумма 2048 чисел каж­дое из ко­то­рых есть не­ко­то­рая сте­пень двой­ки, а зна­ме­на­тель равен 4¹¹.

Обо­зна­чим через a_k ко­ли­че­ство сла­га­е­мых вида a_k, в чис­ли­те­ле дроби, пред­став­ля­ю­щей число x.

С уче­том ис­кус­ствен­но­го раз­дво­е­ния еди­ниц и чисел, по­лу­ча­ю­щих­ся из них, ис­ход­ное ко­ли­че­ство еди­ниц равно

По­лу­ча­ем сле­ду­ю­щую си­сте­му усло­вий, рав­но­силь­ную ис­ход­ной за­да­че:

Чтобы сде­лать число x наи­мень­шим, не­об­хо­ди­мо об­ну­лить как можно боль­ше чисел a_k с боль­ши­ми ко­эф­фи­ци­ен­та­ми (или, что то же самое, с боль­ши­ми но­ме­ра­ми k). Для 2019 еди­ниц до­ста­точ­но по­ло­жить Ре­ше­ни­ем си­сте­мы

будут числа и Тогда

За­ме­тим, что если из­на­чаль­но на доске было на­пи­са­но ко­ли­че­ство еди­ниц, рав­ное сте­пе­ни двой­ки, то можно по­ло­жить то есть в этом слу­чае можно взять от­лич­ным от нуля толь­ко a₀.