Задание №9. УВаси есть 100 банковских карточек. Вася знает, что на одной из карточек лежит 1рубль, на другой – 2 рубля, и так далее, на последней – 100 рублей, но незнает, на какой из карточек сколько денег. Вася может вставить...

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

Эту сумму Вася получит, если 100 раз запросит 50 рублей (или 100 раз 51 рубль). Докажем, что Вася не может гарантировать себе большую сумму. Представим себе, что рядом с Васей стоит банкир Коля, который знает номиналы карточек. Вася называет сумму, а Коля выбирает одну из карточек и вставляет ее в банкомат. Достаточно найти стратегию для Коли, при которой Вася не может получить более 2550 рублей. Действительно, пусть имеется такая стратегия. Вернемся в условия исходной задачи, где картами обладает Вася. Как бы Вася ни действовал, обстоятельства могут сложиться так, как будто против него играет Коля ("злая сила"), и тогда Вася получит не более 2550 рублей. Предложим следующую стратегию для Коли. Когда Вася называет сумму, Коля вставляет произвольную карточку с номиналом, меньшим названной суммы, если таковая имеется, и карточку с максимальным номиналом из имеющихся на руках в противном случае. В первом случае карточка после использования называется выкинутой, во втором – реализованной. Ясно, что Вася получает деньги только с реализованных карточек, причем карточки реализуются в порядке убывания номиналов. Пусть наибольший платеж составляет n рублей и этот платеж реализует карточку с номиналом m рублей, m n . Сделаем два наблюдения. Во-первых, к моменту этого платежа карточки с номиналом, меньшим n рублей, уже съедены (иначе Коля вставил бы одну из таковых в банкомат вместо карты c номиналом m рублей). Во-вторых, все эти карточки выкинуты. Действительно, карточка с номиналом kрублей при k