2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 на доске написаны n единиц...
Сообщение08.09.2006, 04:24 
Модератор
Аватара пользователя


11/01/06
5654
Пусть изначально на доске написаны $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.$

 Профиль  
                  
 
 
Сообщение08.09.2006, 12:46 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение08.09.2006, 15:02 
Заслуженный участник


01/12/05
458
удалено автором

 Профиль  
                  
 
 
Сообщение08.09.2006, 20:29 
Модератор
Аватара пользователя


11/01/06
5654
Юстас писал(а):
пункт 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.$

 Профиль  
                  
 
 
Сообщение09.09.2006, 06:41 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение09.09.2006, 14:31 
Заслуженный участник
Аватара пользователя


01/08/06
3046
Уфа
Заметим, что при $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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group