В ряд стоят $%600$% мешков с яблоками: в первом одно яблоко, во втором $%-$% два, в третьем $%-$% три и так далее, в последнем мешке $%600$% яблок. Время от времени приходит Вася и съедает одно и то же число яблок из нескольких мешков (в каждом мешке яблок должно быть не меньше числа, которое выбрал Вася). За какое наименьшее число визитов Вася съест все яблоки?

задан 24 Дек '16 18:09

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

Такое ощущение, что задача на эту тему когда-то была. Но ссылку я не нашёл, и решения тоже не помню. Будем поэтому делать всё как бы заново.

В процессе у нас могут возникать мешки с одинаковым числом яблок. Легко обосновать, что такие повторы не влияют на количество визитов -- ни в ту, ни в другую сторону. Тогда можно предложить такой способ: съедаем по 300 яблок из последних 300 мешков, и получаем числа от 1 до 300. Повторы сразу мысленно устраняем. Далее тот же приём приводит к числам до 150, затем до 75 -- с уменьшением вдвое. Здесь мы можем съесть по одному яблоку из всех мешков с нечётным количеством, и это даст числа 2, 2, 4, 4, ... , 74, 74. Устраняем повторы и делим числа на 2. Это даёт переход к числам от 1 до 37. Затем тем же путём получаем 18 вместо 37, потом 9, 4, 2, 1. Итого этот способ потребует 10 визитов. В общем случае, если дано $%n$% мешков, этот способ даёт $%k+1$% визит при условии $%2^k\le n < 2^{k+1}$%.

Осталось доказать оптимальность. Докажем, что если у нас присутствуют как минимум $%2^k$% различных значений (идущих подряд или не подряд), то визитов потребуется как минимум $%k+1$%. При $%k=0$% это очевидно. Пусть $%k > 0$%. Мы съедаем яблоки из какого-то числа мешков. Если при этом в стороне остаётся не менее половины, то есть $%2^{k-1}$%, то количество яблок в них не меняется. Тогда по предположению индукции нам будет нужно совершить не менее $%k$% дальнейших шагов, что даёт не менее $%k+1$% шага в целом. Если же мы оставляем меньшее количество, то берём как минимум $%2^{k-1}+1$% мешок. Количество яблок при этом уменьшается на одну и ту же величину, и максимум одно значение может исчезнуть. При этом как минимум $%2^{k-1}$% различных значений остаётся, и снова работает индукция.

ссылка

отвечен 24 Дек '16 21:30

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×27

задан
24 Дек '16 18:09

показан
621 раз

обновлен
24 Дек '16 21:30

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

по почте:

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

по RSS:

Ответы

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

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