Очередь

Штирлиц и Мюллер играют в игру, стреляя по очереди. В очереди 999 человек, и каждым своим ходом Штирлиц или Мюллер убивают одного из них. Если у человека в очереди не осталось соседей, он в ужасе убегает. Проигрывает тот, кто не может сделать очередной ход. Кто выиграет при правильной игре обоих участников?

Решение
Выиграет тот, кто стреляет первым, т.е. Штирлиц. Первым выстрелом ему нужно убить стоящего посередине, а после этого симметрично повторять ходы Мюллера.

Для общего случая, когда число человек в очереди равно N, сформулировать оптимальную стратегию одного из игроков довольно сложно. Перебор на компьютере показывает, что первый игрок выигрывает почти всегда. Второй игрок выигрывает, например, в случае N = 4, 12, 20, 30, 46, 72...