Музей математики под открытым небом «Математический парк» — вписанная в городское пространство коллекция арт-объектов, иллюстрирующих математические факты и понятия. Целью проекта является популяризация математики, пробуждение интереса и мотивации к занятиям этой наукой у детей и взрослых. Математический парк создан в городе Майкопе, в Республике Адыгея на базе Республиканской естественно-математической школы (РЕМШ). На протяжении вот уже 20 лет она готовит лучших школьников из республики Адыгея до уровня призеров и победителей Всероссийской олимпиады по различным предметам. Около 50 выпускников ежегодно поступают в лучшие столичные вузы. Красные дорожки во дворике РЕМШ иллюстрируют знаменитую задачу о Кёнигсбергских мостах, беседка – триангуляцию. Лист Мёбиуса (см. 1-ю страницу обложки), являющийся логотипом РЕМШ, выполнен из доломита. На его односторонней поверхности выгравированы три изображения всемирно известных археологических находок, обнаруженных в курганах Адыгеи: серебряный сосуд ритон, имеющий скульптурное окончание в виде крылатого коня пегаса, золотая бляха-накладка в виде лежащего оленя, нащитная золотая бляха в виде пантеры. Эти находки свидетельствуют о богатей-
шем историко-культурном наследии Адыгеи. Летящий олень, найденный в кургане в городе Майкопе, относится к древнейшей из известных культур, существовавших на территории современной России (конец IV– середина II тысячелетия до н.э.). Эта культура получила название майкопской. Додекаэдр – один из пяти правильных многогранников в трехмерном пространстве.
Идея скульптуры принадлежит Асе Еутых, члену Союза художников России, народному художнику Республики Адыгея, а исполнение – Татьяне Вагановой, дизайнеру, члену Союза художников России. Классическая геометрическая интерпретация теоремы Пифагора, с квадратами, пост-
27
ЗАДАЧНИК
на). Известно, что при выделении любого ребенка оставшихся 99 детей можно разбить на 33 группы по три человека так, чтобы в каждой группе все трое попарно дружили. Найдите наименьшее возможное количество пар дружащих детей.
Ответ: 198. Переведем задачу на язык графов, сопоставляя ребенку вершину, а дружбе – ребро. Тогда нам известно, что в данном графе на 100 вершинах при удалении любой вершины оставшиеся можно разбить на 33 тройки так, что в каждой тройке вершины попарно соединены. Требуется же найти минимальное возможное число ребер в таком графе. Для начала построим пример ровно с 198 ребрами. Разобьем 99 вершин, кроме вершины A, на 33 группы по 3 вершины. Соединим попарно вершины в каждой тройке; наконец, соединим A со всеми другими вершинами. Тогда условия задачи выполнены: при удалении A разбиение на тройки уже приведено, а при удалении любой другой вершины B в этом же разбиении достаточно заменить B на A. При этом в описанном графе всего 33 3 99 198 ребер. Осталось доказать, что это количество – наименьшее. Назовем граф на 3k + 1 вершинах хорошим, если при удалении любой вершины остальные 3k вершин разбиваются на k троек попарно соединенных. Докажем индукцией по k, что в хорошем графе на 3k + 1 вершинах хотя бы 6k ребер; при k = 33 получим требуемую оценку. База при k = 1 несложна: так как при удалении любой вершины три остальные попарно соединены, любые две вершины должны быть соединены, т.е. число ребер равно . Докажем переход индукции. Если из каждой вершины выходит хотя бы по 4 ребра, общее количество ребер не меньше 3 k 1 4 2 2 3 k 1, что даже больше, чем требуемое 6k. В противном случае найдется вершина A, соединенная не более чем с тремя другими. Если удалить любую вершину, кроме A, то A попадет в какуюто тройку, а значит, она соединена хотя бы
«КВАНТА»
с двумя вершинами. Если удалить одну из этих вершин, у A останется не менее двух смежных, т.е. было их не меньше трех. Итак, A соединена ровно с тремя вершинами B, C и D. Тогда при удалении, скажем, B вершины A, C и D образуют тройку, т.е. C и D соединены; аналогично получаем, что B, C и D попарно соединены. Выбросим теперь из нашего графа вершины A, B, C и D, взамен добавив одну вершину X, соединенную со всеми, с кем была соединена хотя бы одна из вершин B, C и D. Заметим, что при этом количество ребер уменьшилось хотя бы на 6 (т.е. на количество ребер между A, B, C и D). Покажем, что полученный новый граф хороший; отсюда будет следовать переход индукции, ибо тогда в новом графе будет не менее 6 k 1 ребер, а значит, в исходном – не менее 6 k 1 6 6 k ребер. Пусть из нового графа удалена некоторая вершина Y z X. Если ее удалить из исходного графа, остальные вершины разобьются на тройки; пусть при этом вершина A окажется, для определенности, в тройке с B и C, а вершина D – в другой тройке. Тогда можно разбить новый граф так же, поместив вершину X в ту тройку, где была вершина D. Наконец, если удалить из нового графа вершину X, можно проделать ту же операцию, считая, что из исходного графа удалена вершина D (тогда A, B и C автоматически окажутся в одной тройке). Таким образом, переход индукции доказан. Отметим, что приведенный в задаче пример – не единственный. Рассуждение из второй части решения по сути показывает, что много различных оптимальных примеров можно построить следующим индуктивным образом. При k = 1 возьмем 4 вершины и соединим все пары ребрами. При переходе от k к k + 1 добавим три вершины B, C, D, соединим их попарно друг с другом, а также соединим их всех с какой-то уже имеющейся вершиной A. В таком примере всегда будет 6k ребер, и он будет удовлетворять условию задачи. С.Берлов, Н.Власова