Новый Мир ( № 11 2007)

Поясним сказанное на примерах. Пусть объявленный набор содержит всего только одну пластинкуAиз приведённого выше перечня. Ясно, что решение невозможно, поскольку, сколько раз ни прикладывай пластинкуAсаму к себе, нижняя строка всегда окажется длиннее верхней. По сходной причине решения не существует, если объявленный набор состоит из одной только пластинкиD

, только тут длиннее будет верхняя строка. Желающие могут попытаться доказать, что решения не существует и в том случае, когда объявленный набор состоит из двух пластинок,AиD. А вот если объявить набор из всех наших четырёх пластинокA

,D,CиD

, то решение существует. Действительно, если сложить пластинки в таком порядке:DBCDA, то и верх­няя, и нижняя строка окажутся одинаковы:zzzxxzzzzx.

Итак, набор объявлен. Все хотят получить приз. Но прежде, чем пытаться найти такое расположение пластинок, при котором верхняя и нижняя строки окажутся одинаковыми, желательно узнать, возможно ли такое расположение в принципе. Ведь если оно невозможно, то бесперспективно его искать, это будет пустой потерей времени. Так вот, оказывается, что не существует никакого эффективного способа это узнавать. Не существует (именно не существует, а не просто неизвестен) такого алгоритма, который позволял бы для любого объявленного набора пластинок узнать, имеется ли реше­ние, то есть возможно или невозможно сложить пластинки требуемым образом. Для каждого отдельно взятого набора пластинок задача узнать, к какой из двух категорий этот набор относится — к той, для которой решения имеются, или же к той, для которой решений нет, — она, эта задача, есть сугубо творческая задача, своя для каждого такого набора, а общий метод получения ответа для всех таких задач отсутствует.

 

(Окончание следует.)

Собиратель

Десятников Владимир Александрович — художник, искусствовед. Родился в 1931 году; ветеран Великой Отечественной войны. В 1965 году окончил искусствоведческое отделение исторического факультета МГУ. Заслуженный деятель искусств; автор ряда книг и альбомов, посвященных русскому искусству; вице-президент Международной славянской академии. В “Новом мире” выступил с очерком, посвященным знаменитому архитектору-реставратору П. Д. Барановскому (2006, № 12).