1.5    Некоторые комбинаторные задачи на плоскости

Задача 1. Показать, что можно так организовать автобусное движение в городе, что

1) каждый автобусный маршрут имел ровно 3 остановки;

2) каждые два маршрута имели единственную общую остановку;

3) с любой из остановок можно проехать на любую другую без пересадки. УКАЗАНИЕ. Рассмотреть граф

 

Задача 2. На плоскости дано п точек, расположенных так, что на ка­ждой прямой, соединяющей любые две из этих точек, лежит по крайней мере еще одна из них. Доказать, что все эти точки лежат на одной прямой.

УКАЗАНИЕ. Допустим противное и выберем среди данных точек такие три точки А, В, С, что расстояние от точки А до прямой ВС яе равно нулю и является наименьшим из всех возможных.

 

Пусть В - третья точка нашего множества, принадлежащая прямой ВС. Ясно, что длины перпендикуляров СЬ,РЬ,АР удовлетворяют неравен­ствам: АР > РЬ\ > СЬ. Противоречие.

Задача 3. На плоскости дано некоторое конечное число попарно пере­секающихся прямых, причем через точку пересечения любых двух прямыхнашего множества проходит некоторая третья прямая из этого же множе­ства. Доказать, что все прямые пересекаются в одной точке.

УКАЗАНИЕ. Допустим противное. Тогда существуют прямые 1\, 12,1з из нашего множества такие, что они не пересекаются в одной точке и рассто­яние от точки А пересечения прямых I] и 12 до 1з является наименьшим из возможных:

Через точку А проходит некоторая прямая Ц из нашего множества, а через точку В = Із П і4 прямая /5, пересекающая її в точке С. Ясно, что расстояние от точки С до /3 меньше расстояния от точки А до /3. Проти­воречие.

Задача 4. Можно ли спланировать автобусную сеть в некотором городе, состоящую из п(п > 3) маршрутов так, чтобы после закрытия любого из этих маршрутов оставалась бы возможность проехать с каждой из имею­щихся остановок на любую другую, используя пересадки, а после закрытия каких угодно двух маршрутов нашлись бы две остановки, с одной из кото­рых уже нельзя проехать на другую?

УКАЗАНИЕ. Такая планировка существует. Действительно, рассмотрим п попарно пересекающихся прямых, никакие три из которых не пересекают­ся в одной точке. Каждую прямую будем считать автобусным маршрутом, а каждую точку пересечения - остановкой. Выбросим некоторую прямую

 

Если наши остановки Л и В] лежат на одной прямой, не совпадающей с I, то доехать можно без пересадки. Если же они принадлежат разным прямым (не совпадающими с I), то доехать можно, сделав пересадку в точке пересечения этих прямых. Если же одна или обе остановки принадлежат вычеркнутому маршруту I, то рассуждение аналогично. В случае удаления 2-х маршрутов, то остановка, расположенная на их пересечении, была бы недосягаемой.

Задача 5. Расположить на плоскости девять прямых и девять точек так, чтобы через каждую точку проходили ровно 3 прямые и на каждой прямой лежали ровно 3 точки.

УКАЗАНИЕ.

Задача 6. На плоскости проведено п прямых линий. Доказать, что области, на которые эти прямые разбивают плоскость, можно закрыть 2 красками так, что никакие две соседние области не будут закрашены одним цветом.

УКАЗАНИЕ. Воспользоваться индукцией по числу п. Еслми п = 1, то ре­шение очевидно. Предположим, что задача имеет решение для п прямых. Рассмотрим разбиение плоскости (п + 1) прямыми її, . . . ,Іп+і- По предпо­ложению индукции существует искомая раскраска областей плоскости, на которые она разбивается прямыми її,..., 1п.

Алгоритм новой раскраски: с одной стороны от 1п+\ раскраска не меня­ется, а с другой - меняется на противоположную.

Задача 7. Доказать, что число точек пересечения диагоналей выпукло­го га-угольника не превосходит С^.

Задача 8. На прямой отмечены га различных точек Л|..... Л „(га > 4). Каждая из этих точек покрашена в один из 4-х цветов, причем все 4 цве­та присутствуют. Доказать, что существует отрезок прямой, содержащий ровно по одной точке двух цветов и по крайней мере по одной точке двух оставшихся цветов.

УКАЗАНИЕ. Можно считать, что наши точки расположены слева направо.

Аг   Л2 Ап

Пусть т = тгп{ц среди точек Л|..... Л/ присутствуют точки всех 4-х цветов }. Тогда цвет Ат отличен от цветов Л1..... Ат-\. Пусть к = тах{]] ] < га—1, среди точек Л;-. Л;-_|...., Ат присутствуют точки всех 4-х цветов }. Тогда цвет Л/, отличается от цветов Л/,_|...., Ат, и отрезок [Л/,.. Аш] является искомым.

Задача 9. В некотором обществе любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Доказать, что в этом обществе все имеют одинаковое число знакомых.

УКАЗАНИЕ. Сначала докажем следующую лемму.

Лемма. Если А и В знакомы, то они имеют одинаковое число знако­мых.

ДОКАЗАТЕЛЬСТВО. Пусть Л1..... Л п — все знакомые А. Будем изобра­жать членов общества точками и соединять любые два ребром, если они знакомы. Тогда среди В. А\..... Л„ нет знакомых и существуют В\,..., Вп такие, что В,ь - общий знакомый А;ь и В :

В

 

А

Таким образом, число знакомых В больше или равно п. Аналогично до­казывается, что число знакомых А не меньше числа знакомых В. Лемма доказана.

Пусть С я В незнакомы. Тогда существует Е такой, что

По лемме число знакомых Е равно числу знакомых С и равно числу знакомых В.

Задача 10. В компании, состоящей из 5 человек, среди любых трех человек найдутся двое, которые знают друг друга, и двое, незнакомых друг с другом. Доказать, что компанию можно рассадить за круглым столом так, чтобы по обе стороны от каждого человека сидели его знакомые.

УКАЗАНИЕ. Докажем, что каждый человек знает ровно двоих. Если А знает трех В, С, В, то среди {В, С, В} нет знакомых. Противоречие.

Если А не знаком с тремя членами компании Б, С, В, то Б, С и В попарно знакомы друг с другом. Итак, каждый член компании знаком ровно с двумя другими. Пусть А знаком, например, с В я С. Тогда Б и С не знакомы между собой. Пусть В - знакомый Б и Е - оставшийся член компании. Тогда Е - знакомый С и В - незнакомый С. Укажем искомую рассадку

Задача 11. В каждой из 3-х студенческих групп учится по п студентов. Любой студент имеет (// + 1) знакомых студентов в двух других группах. Доказать, что в каждой группе можно выбрать по одному студенту так, чтобы все трое выбранных студентов были знакомы друг с другом.

УКАЗАНИЕ. Пусть А такой студент одной из групп, который имеет наи­большее число к знакомых в одной из групп (к < п). Так как (п + 1 — к) > 1, то пусть Б - знакомый А из оставшейся третьей группы. Если Б знаком с кем-либо из знакомых А во второй группе, то задача ре­шена. Иначе, он знаком с не более чем к студентами в первой группе и с не более чем (п — к) студентами во второй группе. Т.е. общее число его знакомых не превосходит п. Противоречие.

Задача 12. Доказать, что если в графе с 2п вершинами никакие три ребра не образуют треугольника, то число ребер не превосходит п2.

УКАЗАНИЕ. Воспользуемся методом математической индукции. Выбе­рем две вершины А я В, соединенные ребром:

А

 

Оставшиеся вершины соединены не более чем п2 ребрами и каждая из них соединена с Л и Б не более чем одним ребром.

Таким образом, общее число ребер не превосходит числа п2 + 2п + 1 = = (п + I)2. Примером графа с 2п вершинами и п2 ребрами является дву­дольный граф: