Выбрана 1 задача 
Убрать все задачи
Двое игроков играют в карточную игру. У них есть колода из n попарно различных карт. Про любые две карты из колоды известно, какая из них бьёт другую (при этом, если A бьёт B, а B бьёт C, то может оказаться, что C бьёт A). Колода распределена между игроками произвольным образом. На каждом ходу игроки открывают по верхней карте из своих колод, и тот, чья карта бьёт карту другого игрока, берёт обе карты и кладёт их в самый низ своей колоды в произвольном порядке по своему усмотрению. Докажите, что при любой исходной раздаче игроки могут, зная расположение карт, договориться и действовать так, чтобы один из игроков остался без карт.
|
|
 |
Условие
Двое игроков играют в карточную игру. У них есть колода из 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 у первого игрока одна карта, то есть она критическая, и в неё входит только одна стрелка. Но в каждую достижимую ситуацию должно входить две стрелки. Противоречие.
