Вкаждой клетке доски 10 на 10 лежит по 100 сосисок. два кота полосатики и волосатик играют в игру по следующим правилам. за один ход можно выбрать в таблице строку и столбец в каждой клетке которого есть хотя бы одна сосиска и из всех этих клеток съесть по одной сосиске. начинает полосатик, проигрывает не имеющие хода. какой код имеет выигрышную стратегию? с решением. заранее
ответ: При нечетном n выигрывает второй кот, при четном n - первый. В самом деле, пусть n = 2k+1 нечетно. Занумеруем все сосиски подряд числами от 1 до n . Сосиску с номером k+1 будем называть центральной. Второму коту каждым ходом нужно перегрызать перемычку, симметричную той, которую перегрыз на предыдущем ходу первый кот (относительно центральной сосиски). Тогда он съест сосисок не меньше, чем первый, причем первый при такой игре не сможет съесть центральную сосиску (так как ее концы (перемычки) симметричны друг другу относительно этой сосиски). Значит, второй кот съест не менее k+1 сосиски и выиграет. Пусть теперь n = 2k четно. Занумеруем все сосиски подряд числами от 1 до n . В этом случае первый кот должен первым ходом съесть одну из крайних сосисок (скажем, последнюю). Тогда перед вторым котом окажется нечетное число сосисок, и из них он сможет съесть только меньше половины, если первый игрок будет пользоваться стратегией второго для случая нечетного n. (Другими словами, далее первому игроку надо отвечать на ходы второго симметричными (относительно k+1-ой сосиски) ходами.) При такой стратегии первый игрок съест в результате по крайней мере на две сосиски больше, чем второй.