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

[spamsink]

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

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

 0 - 0000
 1 - 0001
 2 - 0011
 3 - 0010
 4 - 0110
 5 - 0111
 6 - 0101
 7 - 0100
 8 - 1100
 9 - 1101
10 - 1111
11 - 1110
12 - 1010
13 - 1011
14 - 1001
15 - 1000

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

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

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