Ответ к задаче #14

Сначала непосредственно задача:
Четыре пивные кружки расставлены по краям квадратного стола, некоторые вверх ногами. По столу ползает робот исполняющий три команды (a) «перевернуть угловую кружку» (b) «перевернуть две диагональных кружки» (c) «перевернуть две соседние кружки». Однако после каждой команды непредсказуемо в каком углу, на какой диагонали или стороне стола кружки приглянутся роботу больше. Придумайте серию команд понуждающую робота привести кружки хотя бы к единообразию.

Источник Benjamin Rossman.

Задача вышла довольно интересной, вчера убил часа 3 на нахождение решения.
Сперва такой факт: любую, как угодно длинную комбинацию из команд 'a', 'b', 'c' можно заменить всего одной командой 'a', 'b' или 'c'. Необходимо понять, что у нас есть всего 4 возможных комбинации (и не важно как именно расположены кружки относительно стола):

• Все кружки в одинаковом положении
• Ровно одна кружка отличается положением от остальных
• Ровно две кружки с одинаковым положением, которые стоят по диагонали
• Ровно две кружки с одинаковым положением, которые стоят рядом

Предположим, мы уже нашли комбинацию команд S, длиной N (N>1). Возьмем первые две команды, выйдет всего 9 вариантов: 'aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc'.

• 'aa' - команда 'a' меняет состояние угловой кружки на противоположное, так что при повторном использовании команды 'a' состояние может остаться таким же (если робот выберет ту же кружку, что и сначала); могут изменить свое состояние две диагональные кружки (то есть, можно заменить 'aa' на 'b'); могут изменить свое состояние две соседние кружки (что фактически означает применение команды 'c'). Выходит, 'aa' всегда дает один из 3 исходов: 'b', 'c', либо 0 (ноль), если состояние системы не изменилось. 'aa' -> 0, 'b', 'c'.
• 'ab' - сначала меняется одна угловая кружка (не важно какая, ведь робот действует рандомно), потом возможны 2 варианта: робот выберет ту же диагональ, на которой стоит измененная кружка, тогда состояние первой кружки изменится на изначальное, а состояние второй кружки изменится на противоположное (поскольку 2 остальных кружки мы не трогали, 'ab' фактически изменяет состояние всего одной кружки, то есть 'ab' дает такой же результат что и команда 'a'); робот выберет диагональ с нетронутыми кружками, тогда после выполнения 'ab' свое состояние изменят 3 кружки, что фактически равняется тому, что изменила свое состояние одна нетронутая кружка (а это так же применение команды 'a'). 'ab' -> 'a'. Аналогично поступим и с остальными двойными командами, для краткости приведу только результаты рассуждения.
• 'ac' -> 'a'
• 'ba' -> 'a'
• 'bb' -> 0 (состояние прежнее)
• 'bc' -> 'c'
• 'ca' -> 'a'
• 'cb' -> 'c'
• 'cc' -> 'b'

Выходит, сколько команд не имела бы последовательность, можно брать по две команды в её начале, и превращать их в одну (или в случае с 'bb', вообще убирать). Можно сказать, что это частный случай метода индукции. В итоге, если и есть последовательность, которая всегда приводит к правильному решению, то её всегда можно свести к одной команде: 'a', 'b' или 'c'.

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

Ответ: для общего случая невозможно найти такую комбинацию.