|
|
 |
Условие
У Васи есть 100 банковских карточек. Вася знает, что на
одной из карточек лежит 1 рубль, на другой – 2 рубля, и так
далее, на последней – 100 рублей, но не знает, на какой из
карточек сколько денег. Вася может вставить карточку в банкомат и
запросить некоторую сумму. Банкомат выдает требуемую сумму, если
она на карточке есть, не выдает ничего, если таких денег на
карточке нет, а карточку съедает в любом случае. При этом банкомат
не показывает, сколько денег было на карточке. Какую наибольшую
сумму Вася может гарантированно получить?
Решение
Эту сумму Вася получит, если 100 раз запросит 50 рублей (или 100
раз 51 рубль). Докажем, что Вася не может гарантировать себе
большую сумму.
Представим себе, что рядом с Васей стоит банкир Коля, который
знает номиналы карточек. Вася называет сумму, а Коля выбирает
одну из карточек и вставляет ее в банкомат. Достаточно найти
стратегию для Коли, при которой Вася не может получить более 2550
рублей.
Действительно, пусть имеется такая стратегия. Вернемся в условия
исходной задачи, где картами обладает Вася. Как бы Вася ни
действовал, обстоятельства могут сложиться так, как будто против
него играет Коля ("злая сила"), и тогда Вася получит не более
2550 рублей.
Предложим следующую стратегию для Коли. Когда Вася называет
сумму, Коля вставляет произвольную карточку с номиналом, меньшим
названной суммы, если таковая имеется, и карточку с максимальным
номиналом из имеющихся на руках в противном случае. В первом
случае карточка после использования называется выкинутой, во
втором – реализованной. Ясно, что Вася получает деньги только с
реализованных карточек, причем карточки реализуются в порядке
убывания номиналов.
Пусть наибольший платеж составляет n рублей и этот платеж
реализует карточку с номиналом m рублей, m n . Сделаем два
наблюдения. Во-первых, к моменту этого платежа карточки с
номиналом, меньшим n рублей, уже съедены (иначе Коля вставил бы
одну из таковых в банкомат вместо карты c номиналом m рублей).
Во-вторых, все эти карточки выкинуты. Действительно, карточка с
номиналом k рублей при k<n не могла быть реализована раньше
карточки с номиналом m рублей, поскольку k<m .
Таким образом, общее число реализованных карточек не превосходит
100-n+1 . С каждой реализованной карточки Вася получает не более
n рублей, поэтому общая сумма, полученная Васей, не превосходит
nx (100-n+1) ; максимум достигается при n=50 и n=51 .
Ответ
2550 рублей.
