Палочки

From

Alexey Burdin (2:5012/32.768)

To

Alex Sadovsky

Date

2002-11-11T03:08:05Z

Area

RU.ALGORITHMS

> From: /Unknown/

Как после вчерашнего, Alex ?

 AS> Думаю, всем известна игpа: на столе лежат 20 одинаковых палочек. За
 AS> один ход игpок может взять одну, две или тpи палочки. Пpоигpывает тот,
 AS> кто забиpает последнюю палочку.
    Ну довольно стандартный подход: представить всё это дело как состояния
    (стола с палочками) в граф. ПотОм раскрасить все вершины графа так, что
    + Если состояние стола представлено "белой" вершиной графа, то существует
    ход, приводящий к "белой" вершине при любом ходе соперника. Также "белой"
    вершиной является выигрышная позиция (пустой стол)
    + "Черной" вершиной являются все такие позиции, в которых при любом вашем
    ходе существует ход противника, позволяющий предоставить вам "чёрную"
    позицию. (возможно, также "чёрной" является заведомо проигрышная позиция,
    если таковая имеется)

    Применительно сюда:
    0 палочек ── белая позиция
    1 палочка ── черная позиция
    2 палочки ── белая позиция (взять 1 палочку)
    3 палочки ── белая (вз 2)
    4 б (3)
    5 ч (при ходе 1 ответ 3, 2 ── 2, 3 - 1)
    6 б (1)
    ...
    9 ч (... см. выше)
    ...
    4n+1 - ч, остальные - б.
 AS> Не подскажете ли алгоpитм беспpоигpышной игpы?
    20 палочек ── белая позиция.
    Надо брать палочки так, чтобы их оставалось на столе 4n+1.
    Это алгоритм 1-го игрока. При правильных действиях первого игрока у
    второго шансов на победу нет. (симметричность задачи)
    Этот же алгоритм может быть выигрышным для второго игрока, если на
    каком-то ходе ошибся первый игрок.

                Всего хорошего. Alexey.
... А что подyмал кpолик, никто не yзнал,
--- потомy что кpолик был очень воспитанный.
 * Origin: Megabyte (2:5012/32.768)