Есть три страны, в каждой по 17 городов. Города связаны дорогой в том и только в том случае, когда они находятся в разных странах. Почтальон Андрей хочет проехать по нескольким дорогам на велосипеде (каждая следующая дорога выходит из того города, в который пришла предыдущая), так, чтобы ни на одной дороге не побывать дважды. Какое максимальное число дорог он может посетить?
Назовём для удобства кота, ходящего первым, Барсиком, а ходящего вторым - Мурзиком.
Стратегия для Барсика:
Пусть первым своим ходом Барсик берёт две соседние сосиски. Теперь он расставляет оставшиеся тарелки в ряд и ищет из них тарелку, лежащую ровно посередине ряда (назовём эту тарелку средней).
Если Мурзик своим ходом не взял сосиску со средней тарелки, отразим осевой симметрией, ход Мурзика относительно средней тарелки (прямая перпендикулярна ряду тарелок и проходит через среднюю тарелку). Если в конце осталась сосиска только на средней тарелке, значит, сейчас ход Мурзика, но Барсик взял на две сосиски больше (за первый свой ход - две сосиски, из ряда - столько же, сколько и Мурзик), следовательно, Мурзик проигрывает, если не берёт сосиску со средней тарелки, пока она не осталась последней.
Пусть Мурзик всё-таки взял сосиску со средней тарелки, после чего игра не закончилась. Рассмотрим два случая:
1) Мурзик взял две сосиски. Тогда Барсик, пользуясь осевой симметрией, пытается съесть две сосиски, но съедает одну, после чего продолжает отражать все ходы Мурзика. В итоге Барсик съел на одну сосиску больше Мурзика.
2) Мурзик съел только среднюю сосиску. Отражением тарелки назовём тарелку, в которую данная тарелка переходит при осевой симметрии относительно средней тарелки. Тогда Барсик ест самую левую сосиску и продолжает отражать ходы Мурзика. Заметим, что у самой правой сосиски теперь нет отражения. Пусть Мурзик съел самую правую сосиску. Возможны два варианта:
2.1) Мурзик съел две сосиски. Тогда Барсик съедает одну, после чего у всех сосисок будут отражения и Барсик в итоге победит.
2.2) Мурзик съел только самую правую сосиску. Тогда Барсик ест самую левую из оставшихся сосисок. Теперь опять у одной сосиски нет отражения. Количество сосисок уменьшилось, потому процесс не может продолжаться бесконечно, из чего в какой-то момент либо Мурзик возьмёт две сосиски, одна из которых без отражения, либо возьмёт последнюю сосиску, после чего Барсик всё равно победит.
ответ: Победит первый кот.