|
|
 |
Условие
На доске написано несколько чисел. Разрешается стереть любые два числа a и b, а затем вместо одного из них написать число a+b4. Какое наименьшее число может остаться на доске после 2018 таких операций, если изначально на ней написано 2019 единиц?
Решение
Первое решение.
Пусть mn — наименьшее число, которое можно получить из n единиц после n−1 операций. Заметим, что mn=min при всех n\geqslant 2. Действительно, как бы мы ни получили наименьшее число m_n, оно равно \frac{x+y}{4}, где числа x и y были получены на предыдущем шаге. Пусть x получено из p единиц исходного набора, а y — из оставшихся n-p=q единиц. Если x > m_p или y > m_q (предположим для определенности, что x > m_p), то из исходного набора p единиц можно было бы получить меньшее число, не затрагивая второй набор. Значит, на последнем шаге можно получить число, меньшее m_n, что противоречит определению m_n.
Докажем индукцией по n, что m_n = f(n), где f(n) = \frac{3 \cdot 2^k-n}{2^{2k+1}}, а k=k(n) определяется из условия 2^k \leqslant n < 2^{k+1} (т. е. k = \lfloor \log_2{n} \rfloor). При n=1,2,3 это равенство проверяется непосредственно: m_1 = 1 = \frac{3\cdot 1-1}{2^{1}}, m_2 = \frac12 =\frac{3\cdot 2-2}{2^3}, m_3 = \frac38 = \frac{3\cdot 2-3}{2^3}.
Предположим, что оно верно для всех n \leqslant n_0, где n_0 \geqslant 3, и докажем его для n = n_0+1.
Лемма. Наименьшее значение выражения f(p)+f(q) при условии p+q = n достигается при p = \lfloor n/2 \rfloor, q = \lceil n/2 \rceil, где обозначено \lfloor x \rfloor=[x], \lceil x \rceil — наименьшее целое число, не меньшее x.
Доказательство. Обозначим d(n) = f(n)-f(n+1). Пользуясь формулой для f(n), получаем d(n) = 2^{-2k-1}, где 2^k \leqslant n < 2^{k+1} (это проверяется непосредственно как в случае n < 2^{k+1}-1, так и при n=2^{k+1}-1). Из полученной формулы для d(n) следует, что d(n) \geqslant d(n+1), поэтому d(p) \geqslant d(q) при p \leqslant q.
Пусть 1 \leqslant p \leqslant q < n и p+q=n. Сравним значения f(p)+f(q)} и f(p+1)+f(q-1). Их разность равна f(p)+f(q)-f(p+1)-f(q-1) = d(p)-d(q-1). Если p < q, то d(p) \geqslant d(q-1), а значит, f(p)+f(q) \geqslant f(p+1)+f(q-1). Итак, если p пробегает значения от 1 до \lfloor n/2 \rfloor (т. е. не превосходит q), то сумма f(p)+f(q) не возрастает, а значит, ее наименьшее значение достигается при p = \lfloor n/2 \rfloor (соответственно, q=\lceil n/2 \rceil). Лемма доказана.
Из доказанной леммы и предположения индукции следует, что m_n = \frac{m_{\lfloor n/2 \rfloor}+m_{\lceil n/2 \rceil}}{4} = \frac{f(\lfloor n/2 \rfloor)+f(\lceil n/2 \rceil)}{4}. Остается убедиться, что \frac{f(\lfloor n/2 \rfloor) + f(\lceil n/2 \rceil)}{4} = f(n). Пусть k таково, что 2^k \leqslant n < 2^{k+1}. Тогда 2^{k-1} \leqslant \lfloor n/2 \rfloor < 2^k. Если n < 2^{k+1}-1, то 2^{k-1} \leqslant \lceil n/2 \rceil < 2^k, и f(\lceil n/2 \rceil)= \frac{3 \cdot 2^{k-1}-\lceil n/2 \rceil}{2^{2k-1}}. Если же n = 2^{k+1}-1, то \lceil n/2 \rceil = 2^k, и \begin{align*} f(\lceil n/2 \rceil) =& \frac{3 \cdot 2^k-2^k}{2^{2k+1}} =\\=& 2^{-k} = \frac{3 \cdot 2^{k-1}-2^k}{2^{2k-1}} = \frac{3 \cdot 2^{k-1}-\lceil n/2 \rceil}{2^{2k-1}}, \end{align*} т. е. в обоих случаях имеем f(\lceil n/2 \rceil) = \frac{3 \cdot 2^{k-1}-\lceil n/2 \rceil}{2^{2k-1}}.
Следовательно, m_n=\frac{f(\lfloor n/2 \rfloor)+f(\lceil n/2 \rceil)}{4}=\frac{3 \cdot 2^k-n}{2^{2k+1}}=f(n).
При n=2019 получаем k=10, m_{2019}=\frac{3072-2019}{2^{21}}=\frac{1053}{2^{21}}.
Второе решение.
Пусть x — число, получившееся после 2018 операций. Проследим, как было получено это число. Для этого «развернем» все операции в обратном направлении. При прямом применении операции два числа заменялись одним, поэтому при обратном каждое число мы будем заменять на два числа, из которых оно было получено (сохраняя деление на 4): \frac{a+b}{4}\to \frac{a}{4}+\frac{b}{4}. При этом есть числа, у которых нет предшественников — это единицы. Каждую единицу мы искусственно представим в виде суммы двух чисел: \frac{a+1}{4}\to\frac{1}{4}+\frac{a}{4}=\frac{2}{4^2}+\frac{2}{4^2}+\frac{a}{4} (если a=1, то с этой единицей мы проделаем ту же процедуру). Далее каждую степень двойки, стоящую в числителе и полученную когда-то из единицы, мы снова искусственно превращаем в сумму двух чисел: \frac{2^l}{4^m}=\frac{4\cdot 2^l}{4^{m+1}}=\frac{2^{l+1}+2^{l+1}}{4^{m+1}}=\frac{2^{l+1}}{4^{m+1}}+\frac{2^{l+1}}{4^{m+1}}. Таким образом, при каждом таком «разворачивании» операции в обратном направлении количество чисел удваивается. Поэтому в итоге мы получим представление числа x в виде дроби, в числителе которой стоит сумма 2048 чисел (2^{10} < 2019 < 2^{11}=2048), каждое из которых есть некоторая степень двойки, а знаменатель равен 4^{11}.
Обозначим через a_k количество слагаемых вида 2^k, k=0, 1, ..., в числителе дроби, представляющей число x. С учетом искусственного раздвоения единиц и чисел, получающихся из них, исходное количество единиц равно a_0+\frac{a_1}{2}+\frac{a_2}{4}+\ldots Получаем следующую систему условий, равносильную исходной задаче: \left\{ \begin{aligned} & x=\frac{a_0+2a_1+4a_2+\ldots}{4^{11}}\to\min,\\ & a_0+\frac{a_1}{2}+\frac{a_2}{4}+\ldots=2019,\\ & a_0+a_1+a_2+\ldots=2048. \end{aligned} \right.
Чтобы сделать число x наименьшим, необходимо обнулить как можно больше чисел a_k c большими коэффициентами (или, что то же самое, с большими номерами k). Для 2019 единиц достаточно положить a_2=a_3=\ldots=0. Решением системы \left\{ \begin{aligned} & a_0+\frac{a_1}{2}=2019,\\ & a_0+a_1=2048 \end{aligned} \right. будут числа a_0=1990, a_1=58. Тогда x=\frac{1990+116}{4^{11}}=\frac{2106}{2^{22}}=\frac{1053}{2^{21}}.
Заметим, что если изначально на доске было написано количество единиц, равное степени двойки, то можно положить a_1=a_2=\ldots=0, т. е. в этом случае можно взять отличным от нуля только a_0.
Ответ
\frac{1053}{2^{21}}.
