|
|
 |
Условие
На доске написано несколько чисел. Разрешается стереть любые два числа $a$ и $b$, а затем вместо одного из них написать число $\frac{a+b}{4}$. Какое наименьшее число может остаться на доске после 2018 таких операций, если изначально на ней написано 2019 единиц?Решение
Первое решение.
Пусть $m_n$ — наименьшее число, которое можно получить из $n$ единиц после $n-1$ операций. Заметим, что $$m_n = \min\limits_{\substack{p+q=n,\\p,q \in \mathbb N}}\frac{m_p+m_q}{4}$$ при всех $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$.
