Доказательство алгоритма является правильным для решения игры

Question

Данный ряд содержит не более 30 камней, которые могут быть черного или белого цвета.В начале игры пропуски не допускаются, но может быть не более 30 камней.Цель состоит в том, чтобы удалить все камни.Только черные камни могут быть удалены, если камень удален, его соседи меняют цвета.Если удаленный камень находился посередине, это создает зазор, который больше не может быть заполнен;соседи этого камня не считаются соседями после удаления камня.

Теперь я создал программу, которая решает эту игру, используя грубую силу.Я пришел к выводу, что игра разрешима только в том случае, если есть черные камни вообще (очевидно) и если количество черных камней нечетное.Кроме того, если количество черных камней нечетное, игру можно решить путем рекурсивного удаления первого черного камня в строке.

Моя проблема в том, что я не могу доказать это условие, что число черных камней должнобыть странным, и что удаление первого камня решит игру.Как я могу правильно доказать этот алгоритм?

Я уже пытался использовать индукцию, но я застрял:

Строка (a, b) = a * черный + b * белый

RemoveFirstBlack (Row (1, b)) = RemoveFirstBlack (черный + b * белый) = 0 (если a = 1 или n = 0, где a = 2n + 1 и n целое число)

Предполагается, что RemoveFirstBlack (Row (k * a, b)) = RemoveFirstBlack (k * a * black + b * white) = 0 с k = 2p + 1 и p целым числом.

RemoveFirstBlack (Row ((k + 1) * a, b)) = RemoveFirstBlack ((k + 1) * a * black + b * white) = RemoveFirstBlack ((2 (p + 1) (2n + 1)) * black + b * white) = RemoveFirstBlack (2 (p + 1) * a * black + b * white) = 0?

Заранее спасибо за любые указатели на всех!

Answer 1

Я предлагаю вам попытаться рассматривать два хода как один.(То есть, 30 камней удаляются за 15 ходов.)

Это позволит вам показать, что свойство наличия нечетного или четного количества черных камней является неизменным на протяжении всей игры.Ниже приведен контрольный эскиз:

Базовые случаи: осталось два камня.Нечетное количество негров.Оба камня могут быть удалены одним двойным ходом:

b w       -> _ b        ->  _ _
w b       -> b _        ->  _ _

Для четырех камней или более перечислите различные возможные префиксы, где O и E обозначает последовательность суффиксов камней с нечетное и четное количество черных соответственно.

Вот два случая, с которых можно начать:

b b w b E  -> _ w b b E  ->  _ w _ w E
b b w w O  -> _ w b w O  ->  _ b _ b O
....

В каждом случае вы отмечаете, чторезультирующая последовательность (например, _ w _ w O) содержит нечетное количество черных.

Поскольку если последовательность состоит из одного камня, а число камней нечетное, то этот единственный камень должен обязательно быть черным, что означаетчто также можно удалить последний камень.

---

Заметил, что вы также хотели показать, что это было невозможно, если было четное количество черных камней.Это так же просто.Базовые случаи (b b и w w) невозможно решить, и так как каждый двойной ход удаляет четное количество черных камней, вам не повезет, если вы начнете с четного числа: -)

Answer 2

Предположим, у нас есть группа камней, которая разрешима без разделения группы (если вы должны разделить группу, то у вас фактически есть две группы, которые не требуют разделения). Последний камень, который нужно удалить из группы, должен быть черным [B]. Единственный способ добраться до [B] - через [WB], другого пути нет. Чтобы добраться до [WB] вам нужно либо [BBB], либо [WWB]. Отсюда возникает закономерность. Единственный способ добраться до [xxW] - через [xxBB], а добраться до [xxB] - через [xxWB]. Во всех этих переходах четность не изменяется, а конечное число черных камней нечетное (один), поэтому четность одной неразделимой группы должна быть нечетной .

Скажем, решение требует разделения группы на две неразделимые подгруппы. Мы уже пришли к выводу, что эти две подгруппы должны иметь странный паритет. Если мы исключим черный камень, который сделает переход в новое состояние, у этих двух групп будет четное число черных. Если мы добавим их и добавим черный камень, который будет выполнять переходы, мы можем заключить, что группа, которая решается разделением ее на две неразделимые группы, также должна иметь нечетное число черных камней .

Используя индукцию по группам с одним расщеплением, мы можем заключить, что любая группа должна иметь нечетное количество черных.

Решение исходной задачи не требует грубой силы. Просто возьмите первый черный камень, который придет.