Комбинаторика на Всесибе: игры, графы, конструктивы
Ошибка.
Попробуйте повторить позже
Дядя Андрей и девочка Маша играют в игру. У них имеются две упаковки сока по 
литра: один грушёвый, другой вишнёвый. Кроме
того, у Андрея есть кружка в 
мл, а у Маши — две кружки по 
мл. Игроки пьют сок по очереди по следующим правилам: они
наполняют все свои кружки до краёв, а затем выпивают налитое до дна. При этом запрещается смешивать два вида сока в одной
ёмкости. Если кто-то не может сделать ход, то ходит его соперник. Игра заканчивается, когда никто не может сделать
ход. Побеждает тот, кто выпил больше сока. Может ли кто-либо обеспечить себе победу, если Андрей выбирает, кто ходит
первым?
Подсказка 1
Какой-то непривычный вопрос в задачке, да? Получается, что помимо победы Андрея или Маши еще могло быть, что никто из них не выиграл? Если так, то и Андрей, и Маша должны налить себе одинаково сока. Хм, емкости Маши меньше Андрея, но Маша может сделать больше ходов (за счет двух кружек). Непонятно, может ли кто-то гарантировать победу, но наверняка и Андрей, и Маша могут выпить примерно половину всего сока. Начнем разбираться с Андреем (его ходы более простые). Сколько литров он точно успеет выпить, пока может ходить? Вдруг он выиграет независимо стратегии?
Подсказка 2
Заметим, что объемы всех емкостей кратны 20 мл. Значит, если в упаковках <500 мл сока, то в них не более 480 мл сока. Тогда Андрей заведомо успеет сделать (48 000 - 960) / 980 = 48 ходов (За 1 ход Маши и 1 ход Андрея они выпивают 980 мл). То есть Андрей явно не проигравший - выпил ровно половину всего сока. Правда, Маша тоже могла выпить 24 литра сока суммарно. Хм, вариант ничьи всё более вероятен? Разбираемся с Машей. Выбор первого игрока за Андреем, поэтому может ли Маша набрать 24 литра сока в обоих случаях (за первого и второго игрока)? Стратегия с использованием симметрии или дополнения хода может помочь одному из игроков (как думаете кому именно?:))
Подсказка 3
Теперь можно уверенно сказать, что Маша тоже может не проиграть. Пусть она всегда пьет тот же сок, что и Андрей. То есть на пару за ход они выпивают 980 мл из одной упаковки. А если Маша ходит первой, то пусть она первым ходом выпьет по 240 мл из каждой упаковки. Сколько в обоих случаях будет сока в упаковках, когда Андрей не сможет ходить? Поймите, почему Маша выпьет 24 л и тоже не проиграет.
Докажем, что Андрей может выпить 
литра сока, как бы ни действовала Маша, и покажем, что Маша может ходить так, что тоже
выпьет 
литра.
Предположим, Андрей выпил менее 
литров, то есть смог сделать не более 
ходов. Тогда Маша сделала не более
ходов. Значит, на данный момент выпито не более 
то есть не выпито хотя бы 
мл
сока.
С другой стороны, так как объёмы всех ёмкостей делятся на 
то и количество оставшегося сока в каждой упаковке делится на 
Если Андрей не может сделать ход, то оно не превосходит 
мл в каждой упаковке, но тогда сока осталось не более 
мл. Значит,
Андрей при любых обстоятельствах сможет сделать 
ходов.
Докажем, что Маша тоже может выпить 
литра сока, как бы ни действовал Андрей. Пусть Маша ходит второй
и наполняет оба стакана тем же соком, что и Андрей в свой ход. Тогда за одну пару ходов они выпивают 
мл из
упаковки, и после 
ходов в этой упаковке останется 
мл сока, которые Андрей выпить не может, а Маша может. За 
хода Маша выпивала на каждом на 
мл меньше, чем Андрей, т.е. в итоге выпила на 
меньше, что компенсирует,
допивая последнее из этой пачки. Таким образом, если она ходит второй, то может выпить по крайней мере половину
всего.
Если она ходит первой, то пусть первым ходом выпивает из каждой пачки по 
мл, а затем повторяет ходы. Аналогичными
рассуждениями, в каждой пачке в конце остаётся 
мл (если в какой-то больше, то Андрей пока ещё ходит туда), что Маша допьёт и
компенсируем разницу в выпитом до нуля.
Значит, никто не может обеспечить себе победу.
Нет, не может.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
