НУЖНА ЗАДАЧИ С ГРАФАМИ. 1. В трехмерном пространстве 9 точек размещены так, что никакие три не лежат на одной прямой, никакие четыре в одной плоскости. Каждая точка соединена отрезками прямых в точности с четырьмя другими. Докажите, что всегда найдется хотя бы один треугольник с вершинами в точках, расположенных в 3-х разных плоскостях.

2. В городе 5 жителей. Любые двое из них либо дружат, либо враждуют, причем, среди любых троих жителей дружат либо все трое, либо только двое. Докажите, что если не все жители этого города – друзья, то найдется горожанин, у которого врагов больше, чем друзей.

1. Для решения этой задачи на графах, мы можем представить каждую точку как вершину графа, а каждый отрезок между двумя точками как ребро графа. Таким образом, у нас получится граф с 9 вершинами и ровно 36 ребрами.

Мы знаем, что каждая точка соединена с ровно четырьмя другими точками. То есть, каждая вершина имеет ровно четыре ребра, выходящих из нее.

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

Возьмем любую вершину графа. У нее есть ровно 4 смежных вершины. Предположим, что эти 4 вершины все лежат в одной плоскости. Тогда, если мы возьмем еще одну вершину из графа, она должна быть соединена с этой плоскостью ребром. Но у нас есть всего 4 ребра, выходящих из нее, и они уже соединены с другими вершинами в плоскости. Таким образом, мы не можем добавить новую вершину в эту плоскость, что противоречит нашему предположению. Это значит, что хотя бы одна из вершин изначально выбранной плоскости должна лежать в другой плоскости.

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

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

2. Чтобы решить эту задачу на графах, мы можем представить каждого жителя города как вершину графа, а дружеские отношения или враждебность между жителями как ребра графа.

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

Предположим обратное - что нет горожанина, у которого врагов больше, чем друзей. То есть, у каждого жителя количество друзей не меньше, чем количество врагов.

Возьмем любого жителя и обозначим его как вершину A. У вершины A будет не меньше столько же друзей, сколько и врагов.

Теперь, мы выбираем одного из друзей вершины A и обозначаем его как вершину B. У вершины B также будет не меньше столько же друзей, сколько и врагов.

Далее, мы выбираем одного из друзей вершины B, который не является дружеским с вершиной A, и обозначаем его как вершину C. У вершины C также будет не меньше столько же друзей, сколько и врагов.

Теперь у нас есть три вершины - A, B и C. Согласно условию задачи, среди трех вершин должен быть треугольник дружеских отношений или треугольник враждебности.

- Если среди A, B и C есть треугольник дружеских отношений, то у вершины C должно быть не меньше столько же друзей, сколько и врагов, противоречащее нашему изначальному предположению.

- Если среди A, B и C есть треугольник враждебности, то у вершины A должно быть не меньше столько же друзей, сколько и врагов, противоречащее нашему изначальному предположению.

И, следовательно, наше исходное предположение было неверным. То есть, если не все жители города - друзья, то найдется горожанин, у которого врагов больше, чем друзей.