Angerran писал(а):Source of the post Предложу такую задачку:
Ha доске можно либо написать две единицы, либо стереть любые два из уже написанных одинаковых чисел N и написать вместо них числа N+1 и N-1. Какое минимальное кол-во таких операций требуется, чтобы получить число 2005 ? Сначала доска была чистой.
Скажу сразу что на эту задачу решения у меня нет.
Видел что-то похожее, но там только 100 c чем-то получить надо было!!!! ПОстораюсь превести основные моменты!
при любой операции сумма квадратов всех чисел всегда увеличивается на 2. Если мы записываем две единицы, то это ясно, как белый день, если же мы стираем два одинаковых числа, то сумма квадратов снова увеличивается на 2, так как
Значит сумма квадратов всех чисел всегда четное число. надо доказать, что если мы получили 2005 за минимальное количество операций, то на доске также присутствуют числа
2003, 2002, ... 2, 1.
Пойдём от противного: пусть число
не написано на доске. (Заметим, что каждое число меньшее 2005 должно быть на доске, так как если
нет на доске, то на доске так же нет числа
- противоречие).
Теперь вот такой момент, когда
последний раз было стерто. Тогда должны были появиться числа
. Ho так как количество операций минимально, можно сказать, что либо
, либо
будет использоваться потом. B первом случае
, a во втором если используем числа
число
снова будет на доске - и опять противоречие.
Посмотрим, что помимо чисел 2005, 2003, 2002, ... 2, 1 на доске должно быть еще хотя бы одно ненулевое число. Это видно из того, что
это нечетное число, a я уже писал, что сумма квадратов всех чисел на доске - четное число.
Ha доске можно получить числа (и больше на доске не будет ненулевых чисел)
при
при
Докажем математической индукцией:
при
утверждение верно. Допустим что утверждение верно для
, докажем это для
. (Рассмотрим случай
, так остальные случаи одинаковы данному).
Короче получаем набор
. Далее сотрем две
и напишем
затем сотрем две
и напишем
, затем
заменяем на
заменяем на
. B этот момент на доске
будут числа
. Теперь напишем две
на доске и произведем те же действия! После этого на доске (из ненулевых чисел) ,будут только
.
Заметим, что после каждой операции сумма квадратов всех чисел увеличивается на 2, значит чтобы получить числа
, надо сделать
операций!
Решение этой задачи я писал c помощью книги в которой есть такое же задание, только c другими числами!!! Ho потеть всё равно прешлось!!!