Задание №9. УВаси есть 100 банковских карточек. Вася знает, что на одной из карточек лежит 1рубль, на другой – 2 рубля, и так далее, на последней – 100 рублей, но незнает, на какой из карточек сколько денег. Вася может вставить карточку в банкомати запросить некоторую сумму. Банкомат выдает требуемую сумму, если она накарточке есть, не выдает ничего, если таких денег на карточке нет, а карточкусъедает в любом случае. При этом банкомат не показывает, сколько денег было накарточке. Какую наибольшую сумму Вася может гарантированно получить?. Created by zharikovaiulii. matematika-ru

Максимальная, и гарантированная сумма это 1 р...

Задание №9. УВаси есть 100 банковских карточек. Вася знает, что на одной из карт...

yliaks Эту сумму Вася получит, если 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 .

1 votes Thanks 3

zharikovaiulii Ты уверен(а)?

yliaks Да!

yliaks Это сумма 2550, не более.

zharikovaiulii а ты где нашел(а)?

Answers & Comments

рекомендуемые вопросы

Helpful Links

Helpful Social