ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64784
Темы:    [ Процессы и операции ]
[ Кооперативные алгоритмы ]
[ Доказательство от противного ]
[ Принцип Дирихле (прочее) ]
Сложность: 5-
Классы: 10,11
В корзину
Прислать комментарий

Условие

Двое игроков играют в карточную игру. У них есть колода из n попарно различных карт. Про любые две карты из колоды известно, какая из них бьёт другую (при этом, если A бьёт B, а B бьёт C, то может оказаться, что C бьёт A). Колода распределена между игроками произвольным образом. На каждом ходу игроки открывают по верхней карте из своих колод, и тот, чья карта бьёт карту другого игрока, берёт обе карты и кладёт их в самый низ своей колоды в произвольном порядке по своему усмотрению. Докажите, что при любой исходной раздаче игроки могут, зная расположение карт, договориться и действовать так, чтобы один из игроков остался без карт.


Решение

  Выпишем все возможные ситуации, которые могут встретиться в игре (то есть все возможные пары колод у участников). Назовём ситуацию финальной, если все карты у одного игрока; критической, если у одного из игроков ровно одна карта; и регулярной, если у обоих игроков хотя бы по две карты. Проведём стрелку от каждой ситуации к ситуациям, которые могут из неё получиться после одного хода. Тогда из любой нефинальной ситуации ведут две стрелки, а из любой финальной – ноль. Нам надо доказать, что из каждой нефинальной ситуации по стрелкам можно дойти до финальной.
  Выясним, сколько стрелок ведут в каждую ситуацию. Предположим, что она получилась в результате какого-то хода, в котором карты взял первый игрок. Тогда у него оказалось хотя бы две карты, которые лежат в конце колоды; при этом известно, что одна из них – a – бьёт другую – b. Значит, в этом случае карта a была у первого игрока, а карта b – у второго, то есть предыдущая ситуация восстанавливается однозначно. Итак, если наша ситуация регулярна, то на предыдущем ходе карты мог получить любой из двух игроков, и в каждом из этих случаев предыдущая ситуация восстанавливается однозначно. Значит, в каждую регулярную ситуацию ведут ровно две стрелки. Аналогично в каждую нерегулярную ситуацию ведёт ровно одна стрелка.
  Предположим, что из некоторой ситуации S нельзя попасть в финальную. Назовём ситуацию достижимой, если в неё можно добраться из S. Из каждой достижимой ситуации ведут две стрелки в достижимые. С другой стороны, в каждую достижимую ситуацию ведёт не более двух стрелок из достижимых. Это возможно только в том случае, если в каждую достижимую ситуацию ведёт ровно по две стрелки из достижимых. Из этого, в частности, следует, что все достижимые ситуации регулярны. Более того, поскольку в каждую ситуацию ведёт не более двух стрелок, получаем, что все стрелки, входящие в достижимые ситуации, выходят также из достижимых.
  Пусть в ситуации S у первого игрока  k > 1  карт. Тогда в одной из двух ситуаций, из которых ведут стрелки в S, у первого игрока  k – 1  карта – назовём эту ситуацию S1; по показанному выше, она достижима. Аналогично, если  k – 1 > 1,  то в одной из двух ситуаций, из которых ведут стрелки в S1, у первого игрока  k – 2  карты; назовём её S2 и продолжим рассуждения. В итоге мы получим цепочку из достижимых ситуаций  S1, S2, ..., Sk–1,  причём в Sk–1 у первого игрока одна карта, то есть она критическая, и в неё входит только одна стрелка. Но в каждую достижимую ситуацию должно входить две стрелки. Противоречие.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2013-2014
этап
Вариант 5
класс
Класс 11
задача
Номер 11.8

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .