Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела игры
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#96247

Имеется 5  кучек по 2018  камней в каждой. Двое по очереди убирают по одному камню из какой-нибудь кучки до тех пор, пока в кучках есть камни. Первый выигрывает, если в какой то момент времени найдется четыре кучки с разным количеством камней. Иначе выигрывает второй. Кто из игроков может победить, как бы ни играл соперник?

Источники: Лига открытий - 2018

Показать ответ и решение

Пусть первый берет из первой кучки, пока там не останется 2018− 1000  камней. Упорядочим по возрастанию остальные кучки, и забудем про вторую кучку. Будем брать из третьей кучки, пока не возьмем оттуда (возможно вместе со вторым игроком) еще 250  камней. Упорядочим две оставшиеся кучки. Покажем, что первый или уже выиграл, или выиграет своим следующим ходом.

После того, как игроки взяли 1000  камней из первой кучки и упорядочили, разность между первой и третьей стала не менее 500,  после чего из этих кучек второй может взять не более 250  камней. Аналогично, после того как игроки взяли 250  камней из третьей кучки и упорядочили, разница между третьей и пятой стала хотя бы 125.  Тогда в первой, третьей и пятой кучках разница в количестве камней больше 120.  И следующим ходом первый (при необходимости) берет камень из второй кучки и выигрывает.

Ответ:

Первый игрок

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!