на доске написаны n единиц...

[maxal]

Пусть изначально на доске написаны $n$ единиц. За один ход можно стереть любые два числа $x, y$ и написать вместо них число $\frac{x+y}{4}$.
Через $n-1$ ходов на доске останется одно число.

Три задачи по мере возрастания сложности:
1) Доказать, что оставшееся число не меньше $\frac{1}{n}$ (эта задача была на форуме MathLinks).
2) Пусть $m_n$ - наименьшее число, которое можно получить указанным способом. Доказать, что $m_n=\frac{m_{\lfloor n/2\rfloor}+m_{\lceil n/2\rceil}}{4}$ для $n>1$, а также что $2^n m_n$ - целое число.
3) Определить точное значение $m_n.$

[Юстас]

в пункте 1) достаточно провести индукцию по четным n, рассмотрев 2 случая: все числа равны 1, либо одно число равно $\frac{1}{2}$. Когда количество чисел четное, для получения наименьшего результата первыми $\frac n 2$ шагов нужно брать пары исходных единиц, когда нечетное - первым шагом сводится к четному случаю с $\frac 1 2$.

[Юстас]

удалено автором

[maxal]

Юстас писал(а):

пункт 2: пусть $n=2^{m_0}+\dots +2^{m_k}$. Тогда(при условии, что мы хотим получить наименьшее число) через $m_0+\dots +m_k$ шагов останутся числа $\frac{1}{2^{m_0}}, \dots , \frac{1}{2^{m_k}}$.

Это требует доказательства.
Кроме того, в п. 2 еще нужно доказать рекуррентную формулу для $m_n.$

[Юстас]

Насчет пункта 2 я конечно же не прав, глупость написал. Удаляю.

[worm2]

Заметим, что при $n \ge 2$ выполняется $m_n = \min\limits_{p+q=n;\ p,q \in \mathbb N} \frac{m_p+m_q}{4}$. Это почти очевидно, но всё же докажем. Как бы мы ни получили наименьшее число $m_n$, оно равно $(x+y)/4$, где числа $x$ и $y$ были получены на предыдущем шаге. Пусть $x$ получено из $p$ единиц исходного набора, а $y$ - из оставшихся $n-p=q$ единиц. Если $x > n_p$ или $y > n_q$ (предположим для определённости, что $x > n_p$), то из исходного набора $p$ единиц можно было бы получить меньшее число (не затрагивая второй набор), а значит, на последнем шаге получить число, меньшее $m_n$, что противоречит определению $m_n$.

Используя доказанное соотношение, а также очевидно получаемые равенства $m_1 = 1$, $m_2 = 1/2$, $m_3 = 3/8$, можно получить все $m_n$ (уже не опираясь на определение $m_n$). Докажем, что $m_n = F(n)$, где $F(n) = \frac{3 \cdot 2^k-n}{2^{2k+1}}$, а $k$ определяется из условия $2^k \le n < 2^{k+1}$ (т.е. $k = \lfloor \log_2{n} \rfloor$). Будем доказывать формулу индукцией по $n$. Для $1 \le n \le 3$, что соответствует $k$ = 1, 2, формула проверяется элементарно ($m_n$ выписаны в первом предложении этого абзаца). Пусть формула верна для всех $n < n_0$, где $n_0 \ge 3$. Докажем её для $n = n_0+1$.

Верно следующее рассуждение: $F(n)$ выпукла вниз, поэтому условный минимум $F(p)+F(q)$ при условии $p+q = n$ достигается, если $p = \lfloor n/2 \rfloor$, $q = \lceil n/2 \rceil$. Это рассуждение (включая выпуклость $F(n)$) не совсем очевидно, поэтому докажем его подробно.

Обозначим $D(n) = F(n)-F(n+1)$. Подставляя выражения для $F(\cdot)$, имеем: $D(n) = 2^{-2k-1}$, где $2^k \le n < 2^{k+1}$ (нужно отдельно рассмотреть случаи $n < 2^{k+1}-1$ и $n = 2^{k+1}-1$). Из формулы для $D(n)$ следует, что $D(n) \ge D(n+1)$, откуда: $D(p) \ge D(q)$ при $p \le q$.

Пусть $1 \le p \le 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) \ge D(q-1)$, а значит, $F(p)+F(q) \ge 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}$, т.е. первое утверждение второй задачи, для $n=n_0+1$.

Остаётся только убедиться, что $\frac{F(\lfloor n/2 \rfloor) + F(\lceil n/2 \rceil)}{4}$ = $F(n)$. Пусть $k$ таково, что $2^k \le n < 2^{k+1}$. Тогда $2^{k-1} \le \lfloor n/2 \rfloor < 2^k$, и либо (1) $2^{k-1} \le \lceil n/2 \rceil < 2^k$, либо (2) $n = 2^{k+1}-1$ и $\lceil n/2 \rceil = 2^k$.

В обоих случаях $F(\lfloor n/2 \rfloor)$ = $\frac{3 \cdot 2^{k-1}-\lfloor n/2 \rfloor}{2^{2k-1}}$.

В случае (1) $F(\lceil n/2 \rceil)$ = $\frac{3 \cdot 2^{k-1}-\lceil n/2 \rceil}{2^{2k-1}}$.

В случае (2) $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}}$, т.е. получилась та же самая формула, что и в случае (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)$. Индукционный переход совершён.

Итак, $m_n$ = $\frac{3 \cdot 2^k-n}{2^{2k+1}}$, где $k = \lfloor \log_2{n} \rfloor$.