Красочная комбинаторика

18

КРАСОЧНАЯ
КОМБИНАТОРИКА
Б.А. Коргемский

Первые занятия «красочной комбинаторской» памятны каждому из нас: на белой бумаге — «оранжевое небо», «оранжевый верблюд» и «оранжевая мама». Перешагнуть рубеж этой детской «оранжевой» комбинаторной геометрии, математическая фантазия ввела палитру красок в условиях задач, занятных, но при этом и серьезных — задач о комбинациях красок и раскрашивания карт. А в некоторых задачах оказалось возможным иное использование красок: раскрашивание — элемент решения, изоминка, придающая рассуждением изящство и краткость.

Что касается комбинаторной геометрии, то это молодое, развивающееся направление математики. Ее методы и, в частности, раскрашивание в соединении с так называемым «принипом проверки на четность» числа однозвечных частей фигуры могут быть полезными в решения инженерных задач отыскания оптимальных способов подгонки стандартных деталей. Откладывая на будущее более подробный рассказ об этом, рассмотрим «для разминки» несколько занятых комбинаторов «красочных» задач.

Один совет: следуя за текстом статьи, пытайтесь всякий раз переедить автора в решении предлагаемых задач.

Двухцветная комбинаторка

Задача 1. ШестЬ мочек расположены в пространстве mak, что никакие три не лежат на одной пря-mой и никакие четыре не принадлежат одной плоскости. Все точки попарно соединены отрезками: синими или красными — по вашему усмотрению. В получившейся конфигурации, содержащей 15 отрезков ($C_6^2 = 15$), есть и треугольники. Может ли подобрать макое распределенное красок для отрезков, при котором не образовалось бы ни однозоно однозвечного треугольника?

Пробы и попытки приведут Вас к отрицательному ответу. Требуется его обосновать.

Решение. Выберем произвольное одну из данных шести точек и обозначим ее буквой A. Из пятей отрезков, сходящая в A, есть не менее трех одного цвета, так как мы располагаем только двумя красками; отметим три из этих отрезков и будем считать для определенности, что они красные. Расмотрим три отрезка, соединяющие пары других концов отчеченных отрезков. Ни один из рассматриваемых трех отрезков не должен оказаться красным, чтобы не возникок треугольник, все стороны которого одного цвета. Но тогда три последних отрезка — все сине и неизбежно образуют однозвечный треугольник.

Осуществим паркет

Задача 2. На рисунке 1 показано покрытие (napkem) квадрата $8 \times 8$ двадцать одной плоской «минимо» ($3 \times 1$) и одной плоской «мonomino» ($1 \times 1$). Доказать, что указанное положение плоки «мonomino»

21

ферийного кубика. Может ли он пройти через центры всех кубков и закончит путь в центральном кубике, если движется термит только параллельно ребрам куба и каждой кубик проходит один раз?

Опять фальшивая монета

«Опять» — в том смысле, что, веряяно, многим из вас знаком серия задач о выделении фальшивой монеты из данной выборки одинаковых по достоинству и по виду монет при помощи указанного числа взвешивания на чашечных весах без гриб. Автор этих задач неизвестен; в математических журналах их решения и исследования начали появляться с 1945 года.

Напомним, что если нет сведений о фальшивой монете (тяжелее она или легче настояшей), то для выделения ее из 12 данных монет достаточно трех взвешивания, а для выделения из 13 — недостаочно. Но…

Задача 9. Пусть кроме 13 монет, среди комorbых одна фальшивая (неизвестно, более легкая или более мягкая), в нашем распоряжении есть одна макая же монета,

причем насмотная. Раскрасием ее следующа, чтобы описить от остальных, но без оцутимого изменения ее собственного веса. Покажите, что в этом случае можно выделить фальшивую монету из 13 заданных при помощи трех взвешивания на цашечных весах без гриб.

Решен и е. Обозначим: 13 испытемых монет цифрами 1—13, окрашенную настоящую монету — кружком ●, левую и правую чашки весов соответствующего буквами Л и П, равновесие — Л=П; опускается левая чашка весов Л/П, опускается правая чашка весов — Л/П.

Схему возможных событий удобно представить таблицей (внизу).

Matematический «катализатор»
Процесс ускорения химического реакции с помощью вспомогательного вещества — катализатора, не расходующая при реакции, — называется камализом. Покажем на одном примере, как раскрашивание может оказаться своеобразным «катализом» решения задачи.

| Первое взвешивание | Второе взвешивание | Третье взвшивание | Фальшивая монета |
| :— | :— | :— | :— |
| монеты на чашках | монеты на чашках | monеты на чашках | monеты на чашках |
| Л=П | Л(10; 11) П(12; ●) | Л(13); П(●) | {Л/П Л/П Л/П Л/П } | 13; тяж. 13; лег. 12; лег. 10; тяж. 11; тяж. 12; тяж. 11; лег. 10; лег. |
| Л/П | Л(1, 2, 6, 7, 8) П(9, 10, 11, 12, ●) | Л(3); П(4) Л(1); П(2) Л(6); П(7) | {Л=П Л/П Л/П Л/П } | 5; тяж. 3; тяж. 4; тяж. 9; лег. 1; тяж. 2; тяж. 8; лег. 6; лег. 7; лег. |
| Л/П | | | | |

Выяснить самоестоящее

22

Рис. 9.

Задача 10. Определить, какое минимальное число кокосовых орехов можно быть собран пямыю моряками, высадившимся на острове после корабкрушения, если они делили орехи так: первый из них уростил один орехм мартынику и взял себеровно $1/5$ часть оставшихся орехов; мощно mak же один за другой посупили и остальные 4 моряка; после эмодо они в шестой раз уростил мартынику один орехом, а остальные поделили между собой поровну.

В слегка измененной редакции эта задача рассмотрена в статье автора «Этому виду задач более 1600 лет» («Квант» № 4, 1973).

Алгебраические решения приводит к линейному неопределенному уравнению с громоздками коэффициентами, которое, однako, как показано в упомянутой статье, легко решается методом «сравнения по модулю». Но всякий, кто увлечен математикой, наверное, с удовлетворением еще раз вернется к этой задаче и, операция дальнейшее изложение, попытается найти новую модель расужений, привлекая в качестве «катализатора» решения задачи дополнительные орехи, окрашенные в желтый цвет (что бы отличить их от исходных).

М. Гарднер в книге «Математические головоломки и развлечения» («Мир», 1971) заметает, что «Впервые раскрашивание как способ решения задачи было структю еще в 1912 году прсфессором Н. Эннингом. В его задание три человек делили между собой яблоки» (см. стр. 238). Далее М. Гарднер показывает, как можно применить способ Эннинга к решению задачи о кокосовых орехах.

К сожалению, именно в этом месте книги содержатся ошибочные утверждения, возникшие, возможно, возможно, вследствие неточности перевода.

Решение. Задачу было бы гораздо проще решить, если бы не требовалось отдавать орехи мартыше. Отделяя от кучи шесть раз $1/5$ часть орехов, мы оставляли бы в куче $4/5$, $(4/5)^2$, $(4/5)^3$, …, $(4/5)^6$ орехов. Наименьшее число орехов, $(4/5)^6$ от которых — целое число, это $5^6$, потому что оно должно шесть раз содержать многоителем пятерку.

Но нам надо еще отдавать орехи мартыше, поэтому даже исходное число орехов не должно делать на пять. Чтобы оно делилось на пять, добавим в кучу четыре желтых ореха. Посмотрим, что получится.

Итак, в кучу орехов, собранных моряками, добавляем еще четыре желтых ореха. Эту кучу разелим на пять равных кучек, причем желтые орехи распределим по одному в четыре кучи. Четыре моряками заготовлено по кучке с желтым орехом, а одному — кучка, в которой все орехи настоящие. Вытащим из кучек по одному ореху: из четырех — по желтому, а из последней — настоящий. Морякам доставется орехов поровну, и мартыше будет орех, и четыре желтых остались в стороне. Все получилось по условию задачи.

Теперь согласно условиям кучки четырех моряков вместе и добавим оставшиеся без дела четырех ореха. По условию, эта куч