2023-02-17
Фабрика выпускает двухцветные ткани из пряжи шести различных цветов. В расцветках этих тканей каждый цвет сочетается по крайней мере с тремя другими. Доказать, что можно выбрать ткани трех различных расцветок, в которых будут представлены все шесть цветов.
Решение:
Первое решение. Перенумеруем шесть цветов однозначными числами от 1 до 6, а расцветки тканей условимся обозначать двузначными числами, цифры которых соответствуют номерам цветов пряжи.
Выберем одну из тканей, выпускаемых фабрикой, например ткань расцветки 56. Если фабрика выпускает также ткани расцветок 12 и 34 или 13 и 24, то утверждение задачи уже выполняется (в расцветках трех тканей $56, 12, 34$ или $56, 13, 24$ представлены все шесть цветов). В противном случае фабрика не выпускает ткани одной из расцветок в каждой паре ($12, 34$) и ($13, 24$). Предположим, что фабрика не выпускает ткани расцветок 12 и 13. (Заметим, что любой вариант расцветок тканей мы всегда можем свести к рассматриваемому, выбрав надлежащим образом нумерацию цветов.)
Поскольку в расцветках тканей, выпускаемых фабрикой, каждый цвет сочетается по крайней мере с тремя другими цветами, то для каждого цвета существует не более двух сочетаний с другими
цветами, не представленных в продукции фабрики. Для цвета 1 известны два таких сочетания: 12 и 13. Следовательно, фабрика заведомо выпускает ткань расцветки 14. Предположим, что фабрика не выпускает ткань расцветки 23, ибо в противном случае утверждение задачи выполнялось бы для тканей трех расцветок: $14, 23, 56$.
Но если фабрика не выпускает ткани расцветок 12 и 23, то из доказанного выше следует, что она заведомо выпускает ткань расцветки 25, а поскольку среди выпускаемых тканей не представлены расцветки 13 и 23, то фабрика должна выпускать ткань расцветки 36. Таким образом, утверждение задачи оказывается выполненным и в этом случае, поскольку все шесть цветов встречаются в расцветках 14, 25 и 36.
Задачу можно «перевести» на язык теории графов. Сопоставим каждому цвету вершину графа и соединим ребрами те пары вершин, которые соответствуют расцветкам выпускаемых фабрикой тканей. Полученный граф содержит 6 вершин. Любые 2 вершины соединены не более чем 1 ребром. По условиям задачи из каждой вершины должно выходить по крайней мере 3 ребра, то есть степень каждой вершины больше или равна 3. Утверждение задачи означает, что среди ребер графа можно найти 3 ребра, не имеющих общих концов.
Соединим пунктирной линией вершины, не связанные ребрами. Тогда ход рассуждений, использованный в первом решении, можно наглядно представить в виде графа, изображенного на рис. На нем сплошными линиями показаны лишь те ребра, о которых упоминалось в решении.
В приводимом ниже решении мы также сформулируем задачу на языке теории графов.
Второе решение. Пусть $P_{1}, P_{2}, \cdots , P_{6}$ - вершины графа. Не ограничивая общности, предположим, что граф содержит ребро $P_{1}P_{2}$. Поскольку из вершины $P_{3}$ выходят по крайней мере 3 ребра, то рассмотрим то из них, которое заканчивается не в $P_{1}$ и не в $P_{2}$. Обозначения всегда можно выбрать так, чтобы это ребро заканчивалось в вершине $P_{4}$. Таким образом, рассматриваемый граф содержит ребро $P_{3}P_{4}$. Следовательно, достаточно рассмотреть лишь случай, когда граф не содержит ребра $P_{5}P_{6}$, поскольку если граф содержит ребра $P_{1}P_{2}, P_{3}P_{4}, P_{5}P_{6}$, то утверждение задачи выполнено. (Ход рассуждений второго решения, аналогичный использованному в предыдущем решении, наглядно изображен на рис.)
Поскольку из вершины $P_{5}$ выходят по крайней мере 3 ребра, то среди ребер $P_{1}P_{5}, P_{2}P_{5}, P_{3}P_{5}, P_{4}P_{5}$ не менее трех ребер принадлежат графу и не более одного ребра не принадлежит графу. Следовательно, вершина $P_{5}$ соединена ребрами по крайней мере с одним из концов каждого ребра $P_{1}P_{2}$ и $P_{3}P_{4}$. Не ограничивая общности, можно предположить, что рассматриваемый граф содержит ребра $P_{2}P_{5}$ и $P_{3}P_{5}$.
Аналогичные рассуждения, проведенные для вершины $P_{6}$, показывают, что не более чем одно из ребер $P_{1}P_{6}, P_{2}P_{6}, P_{3}P_{6}, P_{4}P_{6}$ не принадлежит графу. Следовательно, по крайней мере одно из ребер $P_{1}P_{6}, P_{4}P_{6}$ (например, последнее) принадлежит графу. Но тогда утверждение задачи выполнено для ребер $P_{1}P_{2}, P_{3}P_{5}, P_{4}P_{6}$, что и требовалось доказать,
По поводу самой задачи нам хотелось бы сделать сейчас несколько замечаний:
1. Утверждение задачи допускает следующее обобщение (его и все приводимые далее замечания мы формулируем на языке теории графов): если граф содержит по крайней мере 6 вершин и любые две из его вершин соединены не более чем одним ребром, а степень каждой вершины не меньше 3, то из ребер графа можно выбрать три таких, концы которых различны.
Доказательство этого утверждения мы получим, заменив во втором решении предположение о том, что граф не содержит ребро $P_{5}P_{6}$, другим предположением, согласно которому граф не содержит одно из ребер, соединяющих две вершины с индексами $i > 4, j > 4$.
2. Приведенное выше утверждение останется в силе, если вместо чисел 3 и 6 говорить о числах $n$ и $2n$:
если граф содержит по крайней мере $2n$ вершин и любые две из его вершин соединены не более чем одним ребром, а степень каждой вершины не меньше $n$, то из ребер графа можно выбрать $n$ таких, концы которых различны.
Здесь $n$ означает любое натуральное число. Доказывается это утверждение при помощи рассуждений, аналогичных тем, которые были использованы во втором решении.
Будем отбирать одно за другим ребра графа до тех пор, пока не дойдем до ребра, один из концов которого совпадает с концом ранее отобранного ребра. Предположим, что нам удалось отобрать $k$ ребер. Если $k \geq n$, то утверждение доказано. Предположим, что $k < n$ и что после того, как мы отобрали ребра $P_{1}P_{2}, P_{3}P_{4}, \cdots , P_{2k - 1}P_{2k}$, по крайней мере один из концов остальных ребер совпадает с какой-то из точек $P_{1}, P_{2}, \cdots , P_{2k}$. Тогда каждая из вершин $P_{2k + 1}$ и $P_{2k + 2}$ соединена по крайней мере с $n$ вершинами из $P_{1}, P_{2}, \cdots , P_{2k}$ (следовательно, неравенство $2k \geq n$ выполняется во всех случаях) .
Если мы покажем, что среди отобранных ребер имеется такое, у которого один из концов соединен с вершиной $P_{2k + 1}$, а другой - с вершиной $P_{2k + 2}$ (во втором решении таким ребром было $P_{3}P_{4}$), то теорема будет доказана, поскольку, исключив ребро, концы которого соединены с вершинами $P_{2k + 1}$ и $P_{2k + 2}$, из числа отобранных ребер и пополнив их запас двумя новыми ребрами, соединяющими один конец отброшенного ребра с вершиной $P_{2k + 1}$, а другой - с вершиной $P_{2k + 2}$. мы увеличим число отобранных ребер на единицу и можем делать то же самое до тех пор, пока оно не станет равным $n$.
Упомянутое выше утверждение может быть доказано так. Среди вершин $P_{1}, P_{2}, \cdots , P_{2k}$, служащих концами отобранных ребер, отметим те, парные к которым соединены с вершиной $P_{2k + 1}$. Их не меньше п. Следовательно, неотмеченными остались не более $2k - n < n$ концов отобранных ребер. Вершина $P_{2k + 2}$ соединена по крайней мере с $n$ концами отобранных ребер, а значит, по крайней мере с одним отмеченным концом. Итак, среди отобранных ребер имеется такое, что один его конец соединен с вершиной $P_{2k + 1}$ , а другой - с вершиной $P_{2k}$. Существование именно такого ребра и требовалось доказать.
Третье решение. Если среди ребер графа найдется такое, что, исключив его, мы получим новый граф, также удовлетворяющий условиям задачи, то такое ребро можно назвать лишним и стереть. Стерев одно за другим все лишние ребра графа (их конечное число, поскольку граф конечен), мы получим новый граф, в котором после исключения любого ребра степень по крайней мере двух вершин (то есть число выходящих из них ребер) будет меньше 3. Утверждение задачи достаточно доказать для такого графа, поскольку стирание лишних ребер не нарушало условий задачи (степень каждой вершины оставалась больше или равной 3).
Рассмотрим граф, вершины которого совпадают с вершинами исходного графа, а ребра соединяют лишь пары вершин, не связанные в исходном графе (такие графы называются дополнительными). Поскольку из каждой вершины исходного графа выходят не менее 3 ребер, то из каждой вершины дополнительного графа выходят не более 2 ребер. Удаление ребра из исходного нарушило бы это свойство, поскольку степень по крайней мере двух вершин стала бы меньше 3. Поэтому присоединение ребра к дополнительному графу также лишает его названного выше свойства.
Выясним, каким должен быть граф для того, чтобы его можно было считать дополнительным по отношению к исходному графу.
Две вершины, степень которых меньше 2, могут принадлежать дополнительному графу лишь в том случае, если они связаны ребром, поскольку в противном случае от присоединения к графу ребра, идущего от одной из этих вершин к другой, степень ни одной из вершин графа не стала бы больше 2. Отсюда следует, что допустимы лишь такие разновидности графов, у которых: 1) все вершины имеют степень 2; 2) степень лишь одной вершины меньше 2, а степень всех остальных равна 2; 3) две вершины степени 1 соединены между собой ребром, а степень всех остальных вершин равна 2. Действительно, если бы граф содержал 3 вершины, степень которых меньше 2, то они были бы попарно связаны ребрами и, следовательно, из каждой из них выходило бы по 2 ребра, что невозможно, поскольку по предположению их степень меньше 2.
Поскольку у каждого ребра имеется 2 конца (каждое ребро соединяет две вершины графа), то при любом числе ребер число соединенных ими вершин графа четно. Это означает, что сумма степеней всех вершин графа всегда четна. Отсюда следует, что если граф содержит лишь одну вершину, степень которой меньше 2, то из нее не выходит ни одного ребра (степень такой изолированной вершины равна 0). Тем самым мы доказали еще одно важное свойство графа, дополнительного к исходному: если ребро такого графа выходит из вершины степени 2, то вершина на другом конце ребра также имеет степень 2.
Таким образом, относительно вершин степени 2 можно утверждать, что соединяющие их ребра образуют цикл, «многоугольник», поскольку, выйдя из одной вершины степени 2, мы попадем в другую, из нее - в третью и так далее до тех пор, пока не возвратимся в исходную вершину. Как было показано выше, граф, дополнительный к исходному, может содержать 6, 5 или 4 вершины степени 2. Если число вершин степени 2 равно 6, то соединяющие их ребра образуют либо шестиугольник, либо два треугольника. Если число вершин степени 2 равно 5 или 4, то соединяющие их ребра образуют пятиугольник или четырехугольник. Таким образом, число сторон у всех многоугольников не меньше 3.
Итак, мы установили, что существуют следующие разновидности графов, дополнительных к исходному (рис.): а - шестиугольник; б - два треугольника, не имеющие общих вершин; в - граф, состоящий из пятиугольника и одной отдельной вершины; г - граф, состоящий из четырехугольника и двух вершин, соединенных ребром.
Все четыре графа нетрудно дополнить тремя ребрами так, чтобы эти ребра попарно соединяли все 6 вершин и не имели общих концов. (На рис. изображены два графа, каждый из которых соответствует любому из четырех графов, представленных на рис.) Это означает, что среди тканей, выпускаемых фабрикой, всегда можно выбрать ткани трех различных расцветок, изготовленные из пряжи всех 6 цветов.