Сосисочная стратегия

Имеется цепочка сосисок длины n. Два кота по очереди перегрызают по одной перемычке между сосисками и съедают образовавшиеся одиночные сосиски. Выигрывает тот, кто съест большее число сосисок. Какой должны быть выигрышная стратегия?

Ответ: При нечетном n выигрывает второй кот, при четном n - первый. 

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

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

Ваша оценка: Нет Средняя: 2.9 (36 оценки)


Комментарии

По очереди каждый кот перекусывает по одной перемычке между сосисками и съедает появляющиеся ПРИ ЭТОМ одиночные сосиски.

Берешь сосиски и съедаешь сам.. в итоге сам в выйгрыше

Блин,ниче не поняла

При чем здесь перемычки? это специально чтобы запутать? если за один ход один кот съедает одну сосиску то при нечетном n первый кот съедает на одну сосиску больше так как ему достается центральная, а при четном количестве они съедают поровну, можно рассмотреть на примере минимальных чисел 1 и 2. Так что либо я чего-то не понял, либо ответ ужасно сложный и неверный.

Извините, не посмотрел комментарий, теперь все ясно, но в задаче должно быть сказано что n>1 так как в противном случая коты подерутся :) но так и не смогут съесть сосиску, потому что нет перемычки )))

очень простая стратегия если четное n то первым надо начинать а если нечет то вторым ...)

посмотрел ответ - отстой задача замудрили че то даже я не понял о чем речь. и по прежнему считаю что на такой вопрос правильный ответ тот что я написал

Вот в

Кто быстрее ест, тот и выиграет