65
Комбинаторика — что это такое?
В прошлом году увидела свет новая книга известного ученого и популяризатора науки Н. Я. Виленкина — «Популярная компбинаторика»*).
В 1969 году в Главной редакции физико-mатематических литературы издательства «Наука» была напечатана его книга «Комбинаторика». Она получила всеирное признание и была переведена на многое языки (англійский, немецкий, испанский, польский, венгерский, чешский, эстонский).
Резцензируемая книга очень мало наполнивает свою предшественницу. Из шести глав приписаны занюво, а остальные три — полностью переработанный текст из книги «Комбинаторика».
Начинается «Популярная компбинаторика» главной из истории компбинаторики и ее приложений. Здесь расказано о первых магических квадратах, о фигурых числах, о компбинаторных работах астрологии, занимающих сочетания планет, о том, как схолоста Раймонд Люллей пытается создать машину, дающий различные сочетания понятный, и о компбинаторных задачах, возникших в азартных играх. Автор расссказывает о том, как компбинаторика выделяется в самостоятельную ветвь математики, о работах Паскала, Ферма, Лейбница и Эйлера. Без сомнения, больший интерес вызовут у читателя расссказы о приложениях компбинаторики к разгадке древних письменностей, к изучению генетического кода,
*) Виленкин Н. Я. Популярная компбинаторика. М., «Наука», 1975.
к открытию периодического системы Менделеева. Жаль только, что авторсовсем не оставливается на применениях компбинаторики к технике и на компбинаторке кристаллических решеток.
Вторая глава посвящена классификации компбинаторных задач.
Следуя известной книге Бержа, автор делит компбинаторные проблемы следующим образом:
- Найти конфигурацию элементов, обладающих свойствами.
- Доказать существование (или отсутствие) конфигурации с заданным свойствами.
- Найти общее число конфигураций с заданным свойствами.
- Описать все способы решения данной компбинаторной задачи, дать алгоритм их перечисления.
- Из всех решений данной компбинаторной задачи выбрать оптимальное (по тем или иным параметрам).
На примере магических квадратов и задачи оферзях он показывает, как ищут конфигурации с заданным свойствами, потом расссказывает об общем принципе решения проблем оптимизации: если решение является оптимальным в целом, то оно должно быть оптимальным в любой своей части (этот принцип лежит в основе так называемого диамантического программирования*)). На примере «игры в 15» показывает, как можно доказать невозможность решения некоторых некоторых задач. Рассмотрев известную олимпиадную задачу о научной переписке:
ШестЬ ученых переписываются друг с другом по двум научным темам. Какный переписываемый с каждым по одному теме. Доказите, что найдумся прочее ученых, переписывающих механику по одному теме,
*) «Квант», 1972, № 3, с. 6.
66
автор разбирает потом ее различные обобщения и условия: перепись 17 учены по тем темам, придание различного веса отдельным темам и т. д., подводчитель к формулировке общеей теоремы Рамсея. Следует пожалеть, что объем и характер книги не дали возможности привести в общем виде доказательство этой замечательной теоремы.
Далее разбирается теорема о различных представимелях (или, как ее еще называют, теорема о деревенских свадбах), которая дана с полным доказательством. Эта теорема дает автор повод поговорить о графах и комбинаторных задачах теории графов. Кончается глава более известным материалом теории графов — эйлеровыми маршрутами (обходом графа, при котором они одно ребро не проходится дважды), галмлютоновыми путями (замкнутыми путями, проходящими по одному разу через каждой вершину графа), задачей о четырех красках и т. д. Как и все последующее главы, она содержит много разобразных задач (всего в книге приведено более 400 задач). К сожалению, большимство задач второй главы носит оптимизationalный характер. Они могут создать впечатление, что и задачи последующих главы будут стоять же трудны, хотя это совсем не так — многое задачи третьей, четвертой и пятой глав совсем простые.
В третьей главе изложена «классическая комбинаторка» — размещения, перестановки и сочетания как с повторениями, так и без них. При изложении этих вопросов автор систематически использует язык теории множества и понятие кортежа. Это позволило ему определить основные понятия. Хотя, как и во всей книге, изложение ведется путем разбора более или менее заиматальных задач, на самом деле эта глава представляет собой учебное пособие по комбинаторке, написанное достаточно четко и систематично. Переход на теоретико-можжетвенный язык позволяет сюда разбор формулы включений и исключений (формулы перекрытый), позволяющей найти число элементов в объединении нескольких множества, если известно число элементов в каждой множестве, а также в пересечении любого набора этих множества.
Следующая глава называется «Комбинаторика раскладок и разбиений». Об этих вопросах шла речь в предыдущей книге автора, но теперь изложение стало чече и компактнее. Появился новый материал, например, расссказано о числам Белла, то есть о числе разложить n различных предметов в m неразличных ящиков так, чтобы все ящики были неупустыми.
Была в предыдущей книге и глава «Комбинаторные задачи с ограничениями». Но теперь, вместе разбор отдельных, почти не связанных друг с другом задач, дано изложение общих понятий и формул. В частности, автор дает общую формулу для вычисления так называемых ладейных многоценов. Он восстанавливает исторически справедливость, отмечая, что дадейные числа (число способов поставить на доску данной формы n ладей так, чтобы ни одна пара ладей не могла взять друг друга) были введены и изучены советским математиком С. Е. Аршоном за десять лет до того, как эти числа стали заимататься американские математики Капланский и Риордан. Заканчивается глава задачи о максимом короля Артура и об очереди в кассу.
Последняя, шестая, глава книги расссказывает о комбинаторных задачах, связая запись с теории группы — о комбинаторике орбит. Типичной задачей такого рода является отискание числа способов покрасьть вершины куба в k цветов. Общий способ решения таких задач основан на некоторых понятиях теории группы *). Хотя автору удалось найти более простое изложение этого метода, чем встречалось в большимстве книг по комбинаторке (в популяриной литературе этот метод, наколько нам известно, ни когда не излагался), конец главы не доказано книга.
Таким образом, в целом получилась очень интересная и живо написанная книга по комбинаторке. Однако приходится сокалить, что задачи, приведенные в книге, даны не только без решений, но и без ответов.
Новая книга Н. Я. Вилленкона по комбинаторке будет интересна школьникам старших классов, интересующим математикой, учителям и всем, кому приходится именно с комбинаторными задачами. В 1976 году она удостовена второй премии Всесоюзного конкурса на лучшее произведение научно-популярной литературы.
В настоящее время тираж книги полностью разошлся. Мы надеемся, что издательство «Наука» выпустит второе издание этой полезной книги, расширив ее обем, что дает возможность включить решения приведенных в ней задач и другой материал, а также на основе короля Артура и об очереди в кассу.
*) О группах можно прочитать в «Кванте», 1976, № 10.