Кто зажжёт последний фонарь?

Xenia1996 · Сообщение **Xenia1996** » 14 июн 2011, 08:53

На улице Ксюшекатерининской расположены $$n>1$$

фонарей.
Изначально ни один из них не горит.
Фонарщицы Ксюша и Катенька по очереди зажигают их.
Первым ходом Ксюша зажигает любое число фонарей от 1 до $$ n-1 $$

(порядок не играет роли).
Затем каждая из фонарщиц при своей очереди хода имеет право зажечь не больше фонарей, чем зажгла предыдущим ходом её соперница (но, разумеется, больше нуля).
Выигрывает тот, кто зажжёт последний фонарь.
При каких $$ n $$

выигрывает Ксюша, при каких - Катенька и как нужно играть, чтобы выиграть?

СергейП

Xenia1996 писал(а):Source of the post При каких выигрывает Ксюша, при каких - Катенька и как нужно играть, чтобы выиграть?

Катенька выигрывает только при $$ n=2^k $$

, в остальных случаях выигрывает Ксюша

Xenia1996 · Сообщение **Xenia1996** » 14 июн 2011, 09:36

СергейП писал(а):Source of the post
Xenia1996 писал(а):Source of the post При каких выигрывает Ксюша, при каких - Катенька и как нужно играть, чтобы выиграть?
Катенька выигрывает только при , в остальных случаях выигрывает Ксюша

Верно.
А как играть нужно?

СергейП

Xenia1996 писал(а):Source of the post А как играть нужно?

Да из решения все понятно, Ксюша зажигает столько фонарей, чтобы Катеньке осталось ближайшая степень двойки
Ну и при нечетном кол-ве есть и более простая стратегия - 1 фонарь.

Xenia1996 · Сообщение **Xenia1996** » 14 июн 2011, 09:53

СергейП писал(а):Source of the post
Xenia1996 писал(а):Source of the post А как играть нужно?
Да из решения все понятно, Ксюша зажигает столько фонарей, чтобы Катеньке осталось ближайшая степень двойки
Ну и при нечетном кол-ве есть и более простая стратегия - 1 фонарь.

Да и при чётном - тоже.
Например, при $$n=14$$

имеем нечётное число двоек (7). Ксюша зажигает два фонаря. Если Катенька будет продолжать зажигать по 2, она проиграет, так как двоек всего 7. Если Катенька зажжёт один, она тем более проиграет, так как после этого останется нечётное число фонарей.

Это я о том, что при нечётном (> 1) числе фонарей (а также их двоек, четвёрок, восьмёрок, ... $$2^m$$

-ок) выигрывает всегда Ксюша. А единственный случай, при котором нельзя образовать нечётное (большее 1) число $$2^m$$

-ок - это

.

СергейП

Xenia1996 писал(а):Source of the post
СергейП писал(а):Source of the post
Xenia1996 писал(а):Source of the post А как играть нужно?
Да из решения все понятно, Ксюша зажигает столько фонарей, чтобы Катеньке осталось ближайшая степень двойки
Ну и при нечетном кол-ве есть и более простая стратегия - 1 фонарь.
Да и при чётном - тоже.
Например, при имеем нечётное число двоек (7). Ксюша зажигает два фонаря. Если Катенька будет продолжать зажигать по 2, она проиграет, так как двоек всего 7. Если Катенька зажжёт один, она тем более проиграет, так как после этого останется нечётное число фонарей.

Это я о том, что при нечётном (> 1) числе фонарей (а также их двоек, четвёрок, восьмёрок, ... -ок) выигрывает всегда Ксюша. А единственный случай, при котором нельзя образовать нечётное (большее 1) число -ок - это .

Зачем кота за хвост тянуть?
Проще Ксюше сразу зажечь 6 фонарей и получить проигранную для начинающего игру ситуацию $$2^3$$

Xenia1996 · Сообщение **Xenia1996** » 14 июн 2011, 10:12

СергейП писал(а):Source of the post
Зачем кота за хвост тянуть?
Проще Ксюше сразу зажечь 6 фонарей и получить проигранную для начинающего игру ситуацию

Согласна.
Но я об этом не подумала.

BSK · Сообщение **BSK** » 14 июн 2011, 10:32

Xenia1996 писал(а):Source of the post
СергейП писал(а):Source of the post
Зачем кота за хвост тянуть?
Проще Ксюше сразу зажечь 6 фонарей и получить проигранную для начинающего игру ситуацию

Согласна.

Не согласен. Вообще говоря, без хвоста не обойтись, так как не всегда можно оставить $$2^k$$

фонарей из-за разрешения гасить не более штук, чем на предыдущем ходе.

Xenia1996 · Сообщение **Xenia1996** » 14 июн 2011, 10:50

BSK писал(а):Source of the post
Xenia1996 писал(а):Source of the post
СергейП писал(а):Source of the post
Зачем кота за хвост тянуть?
Проще Ксюше сразу зажечь 6 фонарей и получить проигранную для начинающего игру ситуацию

Согласна.
Не согласен. Вообще говоря, без хвоста не обойтись, так как не всегда можно оставить фонарей из-за разрешения гасить не более штук, чем на предыдущем ходе.

Речь о первом ходе шла. А там любое число можно взять.

СергейП

BSK писал(а):Source of the post
Xenia1996 писал(а):Source of the post
СергейП писал(а):Source of the post Зачем кота за хвост тянуть?
Проще Ксюше сразу зажечь 6 фонарей и получить проигранную для начинающего игру ситуацию
Согласна.
Не согласен. Вообще говоря, без хвоста не обойтись, так как не всегда можно оставить фонарей из-за разрешения гасить не более штук, чем на предыдущем ходе.

Доказательство не полное, сначала надо доказать, что $\displaystyle n=2^k$ проиграно для начинающего, это несколько нудно, но несложно.
А если есть более сильное ограничение на ход, чем n-1, то тем более проиграно.

yourdomain.com