Задание №9. У
10-11 класс
|
Васи есть 100 банковских карточек. Вася знает, что на одной из карточек лежит 1
рубль, на другой – 2 рубля, и так далее, на последней – 100 рублей, но не
знает, на какой из карточек сколько денег. Вася может вставить карточку в банкомат
и запросить некоторую сумму. Банкомат выдает требуемую сумму, если она на
карточке есть, не выдает ничего, если таких денег на карточке нет, а карточку
съедает в любом случае. При этом банкомат не показывает, сколько денег было на
карточке. Какую наибольшую сумму Вася может гарантированно получить?
Максимальная, и гарантированная сумма это 1 р...
Эту сумму Вася получит, если 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 .
Другие вопросы из категории
Читайте также
вот задание Каб 7х7х7 покрашен и затем разрезан на маленькие кубики размером 1х1х1. сколько маленьких кубиков не покрашено ответы (64) (100) (336) (125) какую выдрать ответ
выполнение всей работы потребовалось бы на 7 дней меньше,чем второму.За сколько дней мог выполнить заданий каждый токарь .работая отдельно?
Задание 2.
Даны множества А={5;-8;-1;4} и В={2,-7 }.
Найти прямое произведение А×В и прямое произведение В×А
Задание 3.
На прямом произведении А×В из Задания 2 построить бинарное отношение по признаку: пара (а;b) принадлежит бинарному отношению R, если а≥b.
Задание 4.
Найти предел функции.
Задание 5.
Найти производную и дифференциал функции.
y=ctg 3x
Задание 6.
Исследовать функцию и построить ее график.
y= -
Задание 7.
Найти неопределенный интеграл.
Задание 8.
Вычислить определенный интеграл.
задания относятся к теме производные.
того, что буквы вынимаются в порядке заданного слова.
Слово: Экономика