Цитата
egor писал:
Подозреваю, что если отменить возможность пропуска хода, то можно будет выигрышную стратегию нолика переделать в беспроигрышную стратегию крестика.
Роман писал:
Нельзя. Если существует выигрышная для кого то, то она проигрышная для другого, ежели, конечно, обходится игрой с нулевой суммой.
Полученное противоречие и будет доказывать, что выигрышной стратегии для нолика не существует.
Попробую вспомнить идею правильного рассуждения. Рассматриваем игру "5 в ряд" (крестики-нолики на большой конечной доске). Ходы пропускать нельзя.
Позицией называем расположение крестиков и ноликов. Всевозможные позиции образуют конечный граф, естественно разбитый на этажи (по числу сделанных ходов). Двигаясь от верхних этажей к нижним, можно определить выигрышность каждой позиции. Значит, либо у нолика есть выигрышная стратегия, либо у крестика есть беспроигрышная.
1. Докажем, что у крестика есть беспроигрышная стратегия. Рассуждая от противного, предположим, что у нолика есть выигрышная стратегия A. (*) Без ущерба для общности можем и будем считать, что стратегия A учитывает только текущую позицию, а не последовательность ходов (историю).
2. Используя предполагаемую выигрышную стратегию A, построим для крестика выигрышную стратегию B (и тогда получим желанное противоречие). Сначала крестик ходит в верхнюю левую клетку, помечая для себя этот ход как "лишний". Далее перед каждым своим ходом крестик на отдельном листочке строит из текущей позиции "комплементарную" позицию: убирает лишний ход, меняет крестики на нолики, а нолики на крестики. Затем крестик смотрит, куда в этой комплементарной позиции предписывает походить стратегия A. Если эта клетка свободна, то крестик туда и ходит, если же она занята из-за лишнего хода, то крестик ходит в самую верхнюю-левую из пустых клеток и считает лишним уже этот последний ход.
3. Каждая позиция, в которую можем попасть при такой стратегии, не менее выгодна для крестика, чем соответствующая комплементарная позиция выгодна для нолика. Поэтому построенная стратегия B выигрышна для крестика. Получили, что и у нолика, и у крестика есть выигрышные стратегии. Противоречие. Значит, предположение (*) неверно, для нолика нет выигрышной стратегии. Следовательно, существует беспроигрышная стратегия для крестика.
