spamsink | Код Беккета, или математика в театре

Жил-был драматург Сэмюэл Беккет. Как-то раз в начале 80-х годов он решил написать пьесу для четырех актеров в 16 сценах так, чтобы спектакль начинался и заканчивался при пустых подмостках, каждая сцена начиналась при разном сочетании актеров, находящихся на подмостках, чтобы при смене сцен входил или уходил ровно один актер...

Здесь программисты и примкнувшие к ним скажут - да это же код Грея! Действительно, создать код, удовлетворяющий этим условиям, несложно. Для четырех элементов, например, он может быть таким:

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

Но Беккету этого было мало! Он поставил дополнительное условие: чтобы уходил со сцены всегда тот из актеров, кто находился на ней дольше остальных. Как нетрудно видеть, приведенный выше код этому условию не удовлетворяет: самая правая единица появляется на 5 и пропадает на 7, в то время как вторая слева единица появляется на 4 и торчит аж до 11 включительно.

Беккету найти желаемую последовательность перемещений актеров не удалось; впоследствии выяснилось, что для трех и четырех элементов ее не существует (а для 5-8 элементов - существуют). Эффективного алгоритма для построения кодов Беккета не придумано до сих пор.