Задачка про машину и круговой маршрут
Из этого поста avva (первая по счёту), если не ошибаюсь, тесно связана с леммой о циклах (the cycle lemma) Дворецкого и Моцкина (её саму с применениями можно найти, например, в статье Дершовича и Закса). Если расстояния между станциями, расположенными по кругу - числа рациональные, это фактически частный случай. С иррациональными можно и напрямую доказать. Мой научрук относительно недавно другой частный случай этой леммы использовал в одной из своих статей.
Стратегия Элис для задачки про монеты (второй по счёту) такова. Пронумеруем монетки от единицы до пятидесяти по их местоположению в ряду. Нужно определить, какая из сумм больше: чётных монеток или нечётных. Без ограничения общности, можно предположить, что нечётных, тогда Элис должна в любой свой ход выбирать нечётную по номеру монету. Поскольку вначале с краёв ряда видна одна нечётная (первая) и одна чётная (пятидесятая) по порядку монетки, она сможет это осуществить в свой первый ход. Бобу тогда останется выбирать одну из чётных по номеру монеток, и к следующему ходу Элис инварианта повторится: ей предстоит выбор между одной чётной и одной нечётной монетой (и выбирать ей, конечно, нужно всегда нечётную). В конечном итоге, Боб насобирает все чётные, а Элис все нечётные, за счёт чего она и выиграет.
Стратегия Элис для задачки про монеты (второй по счёту) такова. Пронумеруем монетки от единицы до пятидесяти по их местоположению в ряду. Нужно определить, какая из сумм больше: чётных монеток или нечётных. Без ограничения общности, можно предположить, что нечётных, тогда Элис должна в любой свой ход выбирать нечётную по номеру монету. Поскольку вначале с краёв ряда видна одна нечётная (первая) и одна чётная (пятидесятая) по порядку монетки, она сможет это осуществить в свой первый ход. Бобу тогда останется выбирать одну из чётных по номеру монеток, и к следующему ходу Элис инварианта повторится: ей предстоит выбор между одной чётной и одной нечётной монетой (и выбирать ей, конечно, нужно всегда нечётную). В конечном итоге, Боб насобирает все чётные, а Элис все нечётные, за счёт чего она и выиграет.