Анализ с конца
Ошибка.
Попробуйте повторить позже
Паша и Игорь подбрасывают монетку. Если выпадает орёл, выигрывает Паша, если решка — Игорь. В первый раз проигравший заплатил победителю 1 рубль, во второй — 2 рубля, потом — 4, и так далее (каждый раз проигравший платит в 2 раза больше, чем на прошлом шаге). В начале игры у Паши была однозначная сумма денег, а у Игоря — четырёхзначная, а в конце у Игоря стала двузначная, а у Паши — трёхзначная. Какое минимальное количество игр мог выиграть Паша? Игроки не могут уходить в минус.
Источники:
Подсказка 1
Вот с чего можно начать: поймите, что Паша не мог проиграть последнюю игру) А после посмотрите на серии, где он проигрывает, а после одну выигрывает. Что можно с этом случае сказать?
Подсказка 2
Если нумеровать игры с нуля, то выигрыш или проигрыш составляет 2 в степени номер игры. Если Паша проиграл игры с k-ой по (m-1)-ую, а m-ую выиграл, то его выигрыш составил как раз 2^k! Можно ли теперь связать общий выигрыш Паши и то, как развивались события игр?
Подсказка 3
По двоичному представлению числа выигрыша Паши как раз можно теперь понять какие игры он выиграл) Осталось лишь разобраться с тем, каким вообще мог быть выигрыш, и минимизировать кол-во побед.
Подсказка 4
Например, если у Паши сначала было однозначное число, а потом трехзначное, то выигрыш Паши не больше 999. С другой стороны, если у Игоря было четырехзначное, а после двузначное, то выигрыш Паши 901)
Будем нумеровать игры с нуля. Тогда в игре с номером 
победитель получает 
денег.
Обозначим через 
сумму денег, на которую Паша стал богаче (а Игорь - беднее) по результатам всех игр.
Заметим, что последнюю игру Паша выиграл (иначе за неё он потерял бы больше денег, чем приобрел на всех предыдущих этапах).
Значит, последовательность игр можно разбить на серии, в каждой из которых Паша выиграл последнюю игру и проиграл все остальные в
серии (возможно, никакие). Если серия началась с игры номер 
и окончилась игрой номер 
то Паша выиграл за эту
серию
Если 
то сразу же получаем серию из одного выигрыша такой же суммы 
Итак, двоичное представление числа 
однозначно описывает набор выигранных Пашей игр (за исключением номера последней игры):
слагаемое 
(для 
означает, что очередная серия началась с игры номер 
а предыдущая серия оканчивается победой на игре с
номером 
По условию, 
Но все числа от 901 до 998 содержат в двоичном представлении 
поэтому Паша выиграл 
и 
игры. При этом есть и последняя игра под номером 9, которую Паша тоже должен был выиграть (как мы отметили в начале
решения). В итоге Паша выиграл хотя бы 4 игры.
Кроме этого, за первые 6 игр Паша должен был выиграть хотя бы 3 раза:
- 1.
-
из первых четырёх игр выиграна хотя бы одна, так как
- 2.
-
из двух следующих также выиграна хотя бы одна, так как
- 3.
-
если из первых четырёх выиграна только одна, то после них сумма не более
пятая и шестая обязательно должны быть
выиграны.
Таким образом, суммарно Паша выиграл не менее 
игр.
Пример для 
игр: изначально у Паши было 
рублей, у Игоря – 
рублей, всего сыграно 10 игр. Тогда
Значит, Паша выигрывал в играх с номерам 
а Игорь – в играх 
В конце у Паши окажется 
рубля, а у Игоря –
рублей.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
