Задача 66617

Темы:    [ Теория алгоритмов (прочее) ] [ Процессы и операции ] [ Полуинварианты ]

Сложность: 6 Классы: 10,11

Условие

Автор: Шейпак И.А.

На доске написано несколько чисел. Разрешается стереть любые два числа $a$ и $b$, а затем вместо одного из них написать число $\frac{a+b}{4}$. Какое наименьшее число может остаться на доске после 2018 таких операций, если изначально на ней написано 2019 единиц?

Решение

Первое решение.

Пусть $m_n$ — наименьшее число, которое можно получить из $n$ единиц после $n-1$ операций. Заметим, что $$m_n=\underset{\begin{array}{c}p+q=n,\\ p,q\in \mathbb{N}\end{array}}{min}\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=\frac{1}{2}=\frac{3\cdot 2-2}{2^3},$$ $$m_3=\frac{3}{8}=\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{array}{rl}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{array}$$ т. е. в обоих случаях имеем $$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}+\dots$$ Получаем следующую систему условий, равносильную исходной задаче: $$\{\begin{array}{rl}& x=\frac{a_0+2a_1+4a_2+\dots }{4^{11}}\to min,\\ & a_0+\frac{a_1}{2}+\frac{a_2}{4}+\dots =2019,\\ & a_0+a_1+a_2+\dots =2048.\end{array}$$

Чтобы сделать число $x$ наименьшим, необходимо обнулить как можно больше чисел $a_k$ c большими коэффициентами (или, что то же самое, с большими номерами $k$). Для 2019 единиц достаточно положить $a_2=a_3=\ldots=0$. Решением системы $$\{\begin{array}{rl}& a_0+\frac{a_1}{2}=2019,\\ & a_0+a_1=2048\end{array}$$ будут числа $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}}$.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Год	2019
Номер	82
класс
	1
Класс	11
задача
Номер	5