Задать вопрос
27 июля, 22:20

Задание №9. У

Васи есть 100 банковских карточек. Вася знает, что на одной из карточек лежит 1

рубль, на другой - 2 рубля, и так далее, на последней - 100 рублей, но не

знает, на какой из карточек сколько денег. Вася может вставить карточку в банкомат

и запросить некоторую сумму. Банкомат выдает требуемую сумму, если она на

карточке есть, не выдает ничего, если таких денег на карточке нет, а карточку

съедает в любом случае. При этом банкомат не показывает, сколько денег было на

карточке. Какую наибольшую сумму Вася может гарантированно получить?

+3
Ответы (2)
  1. 27 июля, 22:33
    0
    Эту сумму Вася получит, если 100 раз запросит 50 рублей (или 100 раз 51 рубль). Докажем, что Вася не может гарантировать себе большую сумму. Представим себе, что рядом с Васей стоит банкир Коля, который знает номиналы карточек. Вася называет сумму, а Коля выбирает одну из карточек и вставляет ее в банкомат. Достаточно найти стратегию для Коли, при которой Вася не может получить более 2550 рублей. Действительно, пусть имеется такая стратегия. Вернемся в условия исходной задачи, где картами обладает Вася. Как бы Вася ни действовал, обстоятельства могут сложиться так, как будто против него играет Коля ("злая сила"), и тогда Вася получит не более 2550 рублей. Предложим следующую стратегию для Коли. Когда Вася называет сумму, Коля вставляет произвольную карточку с номиналом, меньшим названной суммы, если таковая имеется, и карточку с максимальным номиналом из имеющихся на руках в противном случае. В первом случае карточка после использования называется выкинутой, во втором - реализованной. Ясно, что Вася получает деньги только с реализованных карточек, причем карточки реализуются в порядке убывания номиналов. Пусть наибольший платеж составляет n рублей и этот платеж реализует карточку с номиналом m рублей, m n. Сделаем два наблюдения. Во-первых, к моменту этого платежа карточки с номиналом, меньшим n рублей, уже съедены (иначе Коля вставил бы одну из таковых в банкомат вместо карты c номиналом m рублей). Во-вторых, все эти карточки выкинуты. Действительно, карточка с номиналом kрублей при k
  2. 27 июля, 22:54
    0
    Максимальная, и гарантированная сумма это 1 р ...
Знаете ответ?
Сомневаетесь в ответе?
Найдите правильный ответ на вопрос ✅ «Задание №9. У Васи есть 100 банковских карточек. Вася знает, что на одной из карточек лежит 1 рубль, на другой - 2 рубля, и так далее, на ...» по предмету 📘 Математика, а если вы сомневаетесь в правильности ответов или ответ отсутствует, то попробуйте воспользоваться умным поиском на сайте и найти ответы на похожие вопросы.
Смотреть другие ответы