Код Беккета, или математика в театре
May. 11th, 2009 12:02 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkЖил-был драматург Сэмюэл Беккет. Как-то раз в начале 80-х годов он решил написать пьесу для четырех актеров в 16 сценах так, чтобы спектакль начинался и заканчивался при пустых подмостках, каждая сцена начиналась при разном сочетании актеров, находящихся на подмостках, чтобы при смене сцен входил или уходил ровно один актер...
Здесь программисты и примкнувшие к ним скажут - да это же код Грея! Действительно, создать код, удовлетворяющий этим условиям, несложно. Для четырех элементов, например, он может быть таким:
Но Беккету этого было мало! Он поставил дополнительное условие: чтобы уходил со сцены всегда тот из актеров, кто находился на ней дольше остальных. Как нетрудно видеть, приведенный выше код этому условию не удовлетворяет: самая правая единица появляется на 5 и пропадает на 7, в то время как вторая слева единица появляется на 4 и торчит аж до 11 включительно.
Беккету найти желаемую последовательность перемещений актеров не удалось; впоследствии выяснилось, что для трех и четырех элементов ее не существует (а для 5-8 элементов - существуют). Эффективного алгоритма для построения кодов Беккета не придумано до сих пор.
Здесь программисты и примкнувшие к ним скажут - да это же код Грея! Действительно, создать код, удовлетворяющий этим условиям, несложно. Для четырех элементов, например, он может быть таким:
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 элементов - существуют). Эффективного алгоритма для построения кодов Беккета не придумано до сих пор.
