Здравствуйте. Помогите разобраться с тем, как правильно понять следующее доказательство.

Автор модифицирует условие задачи (не делая "наименьшесть" полученного значения более очевидной, насколько я могу судить), после чего заключает, что "теперь все ясно". Хотя происходит только усложнение исходной операции, после которого все вдруг становится "очевидным". Не надо ли это как то обосновать кроме как словами "все ясно"? В чем состоит доказательство? С таким успехом можно было и сразу сказать, что все очевидно и все.

Я, вроде, понимаю это рассуждение, я только не вижу, что оно на самом деле хоть что-то доказывает.

Чего я не понял?

Условие.

В 9 ячейках записаны числа: в первой - единица, в остальных - нули. За одну операцию можно выбрать две ячейки и заменить каждое число в них полусуммой этих чисел. Какое наименьшее число можно получить в первой ячейке?

Решение. Нетрудно получить число $%1/2^8$% , усредняя число в первой ячейке со всеми остальными по очереди. Труднее доказать, что меньше получить нельзя. Изменим условие задачи. Пусть после каждой операции все ненулевые числа становятся равными наименьшему из них. Эта новая операция даёт результат в каждой ячейке не больше, чем исходная операция. Теперь всё ясно: новая операция либо ничего не меняет (если числа равны), либо уничтожает один нуль и уменьшает все числа в два раза. Поскольку новая операция не позволяет получить число меньшее $%1/2^8$%, то исходная операция тем более.

задан 5 Авг '17 23:13

изменен 6 Авг '17 2:20

10|600 символов нужно символов осталось
1

Я при первом чтении вообще не понял рассуждения, но при втором чтении всё стало ясно. Здесь рассматриваются два процесса. В первом из них числа x, y оба заменяются на (x+y)/2. Во втором из них, помимо этого, все ненулевые числа дополнительно заменяются на наименьшее из них. Ясно, что осуществляемая операция монотонна: если какие-то числа уменьшились (не важно, как), то результат не увеличится. Поэтому достаточно проследить, что во втором процессе не получится число, меньшее 1/2^8. Но это действительно очевидно, так как в ходе второго процесса у нас всегда имеется несколько одинаковых положительных чисел a, ... , a и несколько нулей. Если взятие полусуммы происходит над двумя одинаковыми числами, ничего не меняется. Если же мы берём числа a и 0, то получаем a/2 два раза, и при дополнительной операции все a заменяются на a/2. Мы получаем при этом набор из чисел a/2, которых стало на одну штуку больше, а нулей стало на один меньше. Теперь понятно, что делить на 2 можно не больше 8 раз, и ненулевые числа второго процесса всегда не меньше 1/2^8.

ссылка

отвечен 6 Авг '17 10:08

1

Спасибо! У Вас всегда хорошие объяснения

(6 Авг '17 19:40) MathAsk
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×497

задан
5 Авг '17 23:13

показан
272 раза

обновлен
6 Авг '17 19:40

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru