8 класс — Страница 2 — Задачи на Графы

Задача 025

01.01.2025 от

2016 мальчиков выбирают девочек. Каждый мальчик выбирает ровно двух девочек: одну блондинку и одну брюнетку. Оказалось, что для любого натурального числа $k, 1 \leq k \leq 80$ , найдется девочка (блондинка или брюнетка), которую выбрали ровно $k$ мальчиков. Докажите, что какие-то два мальчика выбрали одних и тех же девочек.

Подсказка

Зафиксируйте 80 вершин со степенями $1,2, \ldots, 80$ соответственно.

Решение

Рассмотрим двудольный (мульти)граф, где вершины — блондинки и брюнетки, а рёбра — выборы мальчиков. В нем 2016 рёбер. Надо доказать, что есть два ребра с общими концами.

Зафиксируем 80 вершин со степенями $1,2, \ldots, 80$ соответственно; назовём их выбранными. Пусть имеется $k$ рёбер, оба конца которых выбраны; также назовём их выбранными. Тогда рёбер, один конец которых выбран, будет $1+2+\ldots+80-2 k$ . С другой стороны, их не больше, чем 2016- $k$ , откуда $k \geq 1+2+\ldots+80-2016=1224$ .

Рассмотрим выбранные вершины со степенями $1,2, \ldots, 26$ . Из них исходит не более $1+2+\ldots+26=351$ выбранного ребра. Значит, остальные 54 вершины связывают не менее $1224-351=873$ рёбер. С другой стороны, пусть среди этих 54 вершин $x$ блондинок и $54-x$ брюнеток, и между любыми двумя вершинами — не более одного ребра. Тогда всего между этими вершинами не более $x(54-x) \leq(x+54-x)^{2} / 2^{2}=27^{2}=729$ рёбер. Противоречие.

Задача 026

01.01.2025 от

В городе 2015 жителей, которые организовали $n$ клубов. Оказалось, что для каждых двух клубов количество жителей, состоящих хотя бы в одном из них, не больше 2011. Однако для любых трёх клубов хотя бы в одном из них состоит каждый житель города. Найдите наибольшее возможное значение $n$ .

Подсказка

По первому условию для каждых двух клубов $A$ и $B$ найдутся 4 человека, которые в этих клубах не состоят. Но по второму условию эти 4 человека состоят во всех оставшихся клубах.

Решение

Ответ: 32.

Решение: Оценка. По первому условию для каждых двух клубов $A$ и $B$ найдутся 4 человека, которые в этих клубах не состоят. Но по второму условию эти 4 человека состоят во всех оставшихся клубах. Отсюда следует, что четверки, соответствующие разным парам клубов, не пересекаются. Отсюда $4 C_{n}^{2}<2015$ , то есть $n \leq 32$ . Пример. Выделим среди жителей города $C_{32}^{2}=496$ непересекающихся четверок. Каждой из них поставим в соответствие пару клубов, в которых жители, входящие в неё, они не состоят, так, чтобы каждой паре клубов соответствовала какая-то четверка. Остальные (не входящие в четверки) жители состоят во всех клубах.

Задача 027

01.01.2025 от

В кружке занимаются $2 n$ человек. Кружок называется однородным, если у каждого кружковца одно и то же количество друзей в кружке. Докажите, что кружок однороден тогда и только тогда, когда при любом его разбиении на две команды по $n$ учеников количества пар друзей в командах равны.

Подсказка

Разделите вершины на две равные группы $A$ и $B$ .

Решение

Рассмотрим граф знакомств. Разделим вершины на две равные группы $A$ и $B$ . Пусть $S_{A}\left(S_{B}\right)$ — сумма степеней вершин, входящих в $A(B)$ , а $R$ — количество знакомств между учениками из $A$ и $B$ . Тогда количество знакомств $N_{A}$ внутри $A$ равно $\left(S_{A}-R\right) / 2$ . 1) Пусть у всех одинаковое число друзей. Тогда при разбиении на равные группы $A$ и $B, S_{A}=S_{B}$ , следовательно, $N_{A}=N_{B}$ . 2) Пусть не у всех одинаковое число друзей. Составим $A$ из $n$ вершин с наименьшими степенями. Тогда $S_{A}<S_{B}$ , и, следовательно, $N_{A}<N_{B}$ .

Задача 031

01.01.2025 от

В чемпионате по волейболу участвовало $n>2$ команд, каждые две из которых сыграли друг с другом ровно один раз. Оказалось, что для каждых двух команд есть ровно $t$ команд, у которых они обе выиграли. Докажите, что $n=4 t+3$ .

Подсказка

Решение

Возьмем любую команду $A$ . Пусть она выиграла у $k$ команд. Тогда каждая из этих $k$ команд выиграла ровно у $t$ из этих $k$ команд — иначе нарушится условие задачи относительно нее и команды $A$ . Общее число матчей в микротурнире между данными $k$ командами равно $k(k-1) / 2$ с одной стороны и общему числу побед, равному $t k$ — с другой, откуда $k=2 t+1$ . Осталось заметить, что в всем турнире было сыграно $n(n-1) / 2$ матчей и одержано $n(2 t+1)$ побед. Значит, $n(n-1) / 2=n(2 t+1)$ , откуда $n=4 t+3$ .

Задача 032

01.01.2025 от

На недавней математической олимпиаде командам-участницам были предложены девять задач. В итоге получилось, что каждая команда решила ровно три задачи, каждые две команды решили разные наборы задач и для любых трех команд можно найти задачу, которую не решила ни одна из них. Какое наибольшее количество команд могло участвовать в этой олимпиаде?

Подсказка

Назовём две непересекающиеся тройки задач запрещённой парой, если задачи, не входящие ни в одну из этих двух троек, образуют выбранную тройку.

Решение

Ответ: 56.

Решение: Пример на 56 команд получаем, выбрав 8 задач и рассмотрев все 56 составленных из них троек: они удовлетворяют всем условиям задачи. Допустим, мы выбрали больше 56 троек задач. Назовём две непересекающиеся тройки задач запрещённой парой, если задачи, не входящие ни в одну из этих двух троек, образуют выбранную тройку. Понятно, что хотя бы одна из двух троек, образующих запрещённую пару, не должна быть выбранной. Поскольку из шести задач можно выбрать три $C_{6}^{3}=20$ способами, каждая выбранная тройка порождает 10 запрещённых пар, причём, очевидно, разные тройки порождают разные запрещённые пары. При этом для каждой тройки задач существует 20 не пересекающихся с ней, то есть каждая тройка входит не больше, чем в 20 запрещённых пар. Если мы выбрали хотя бы 57 троек, у нас не меньше 570 запрещённых пар, в которые входит не менее $570 / 20>28$ различных троек задач. Но из 9 задач можно образовать лишь $C_{9}^{3}=84$ тройки, поэтому невыбранными останутся максимум 27 троек. Значит, какие-то две выбранные задачи образуют запрещённую тройку. Противоречие.

Задача 033

01.01.2025 от

У мальчика Васи в его классе 8 друзей и 11 подруг. Каждый из его друзей дружит с 10 одноклассницами. Для каждых двух мальчиков любая девочка в классе дружит хотя бы с одним из них. Сколько девочек может быть в этом классе?

Подсказка

Пусть девочек $10+k$ . Тогда каждый из друзей Васи не дружит с $k$ девочками.

Решение

Ответ: 11.

Решение: Понятно, что девочек не меньше 11. Пусть их $10+k$ . Тогда каждый из друзей Васи не дружит с $k$ девочками. Тогда всего этих «недружб» — $8 k$ . Если $k>1$ , то $8 k>10+k$ . Следовательно, в этом случае найдётся девочка, которая не дружит хотя бы с двумя друзьями Васи, что противоречит условию.

Задача 041

01.01.2025 от

На конгресс приехало 100 ученых, каждый из которых сделал доклад. В конце каждый заявил, что ему понравилось ровно 75 докладов, сделанных его коллегами на конгрессе. Докажите, что найдутся трое, каждому из которых понравились доклады двух других.

Подсказка

Рассмотрим ученого А, доклад которого понравился наибольшему количеству его коллег (их, как минимум, 75).

Решение

Будем говорить, что ученые А и В взаимны, если им понравились доклады друг друга. Рассмотрим ученого А, доклад которого понравился наибольшему количеству его коллег (их, как минимум, 75). Рассмотрим всех, кому понравился доклад A , и всех, чьи доклады понравились А. Так как тех и других не менее, чем по 75, а всего ученых, кроме А, ровно 99, то найдется хотя бы 51 человек, взаимный с А. Возьмём группу из ровно 51 такого учёного (назовем её s). Для любого ученого из s найдется как минимум $75-49=26$ ученых из s, доклады которых ему понравились. Рассмотрим в s такого ученого B , доклад которого понравился наибольшему числу его коллег из s. Таких будет не менее 26. Тогда так как B понравились не менее, чем 26 докладов из s , среди учёных из s найдется C , который взаимен с B . Тогда $\mathrm{A}, \mathrm{B}$ и C попарно взаимны, что и требовалось доказать.

Задача 049

01.01.2025 от

В математический кружок пришло заниматься 20 детей. Каждый ребёнок знаком ровно с 14 другими, причём есть 10 человек, любые двое из которых знакомы. Докажите, что этот кружок можно разбить на две группы таким образом, чтобы каждые два ученика, попавших в одну группу, были знакомы между собой.

Подсказка

Зафиксируем десятерых, любые двое из которых знакомы. Назовём их синими, а остальных десятерых — зелёными.

Решение

Пусть каждые двое знакомых совершат рукопожатие. Зафиксируем десятерых, любые двое из которых знакомы. Назовём их синими, а остальных десятерых — зелёными. Каждый из синих знаком с девятью синими и, стало быть, с пятью зелёными. Значит, всего зелёные совершили с синими 50 рукопожатий. Поскольку в сумме у зелёных должно быть $14 \cdot 10=140$ рукопожатий, 90 из них приходятся на рукопожатия зелёных между собой. Так как каждый из зелёных мог пожать руки только 9 зелёным, отсюда следует, что между зелёными были совершены все возможные рукопожатия, то есть каждый из зелёных дружит с каждым, что и завершает доказательство.

Задача 052

01.01.2025 от

Дано натуральное число п. В Ёжгороде имеется центральная площадь и п периферийных площадей, а также п улиц, соединяющих центральную площадь с периферийными. Мэр хочет создать Реестр городских объектов, записав в строчку названия всех улии, и площадей. Регламент требует, чтобы название каждой улицы стояло в Реестре правее названий обеих площадей, которые она соединяет. Сколькими способами мэр может составить Реестр?

Подсказка

Докажите индукцией по n

Решение

Ответ: $2^{n} \cdot(n!)^{2}$ последовательностей. Решение. Докажем это индукцией по $n$ . База $n=1$ очевидна.

Индукционный переход $n \rightarrow(n+1)$ . Последняя запись в реестре города с ( $n+1$ ) улицей — это название некоторой улицы. Уберем эту запись, а периферийную площадь этой улицы, упомянутую в реестре ранее, выделим красным цветом. Красная запись может находиться в любом месте оставшегося реестра. При ее удалении получается реестр города с $n$ улицами. Значит, для составления реестра в городе $\mathrm{c}(n+1)$ улицей можно

— выбрать периферийную площадь, которую мы будем считать красной (это можно сделать $n+1$ способами),

— взять реестр остальной части города с $n$ улицами (по индукционному предположению имеется $2^{n}(n!)^{2}$ вариантов такого реестра),

— в любое место этого реестра вставить запись о красной площади ( $2(n+1)$ вариантов)

— и добавить в конец запись о красной улице.

Задача 055

01.01.2025 от

На каждом ребре полного графа с 2019 вершинами написано число 1,2 или 3 так, что сумма чисел на рёбрах каждого треугольника не меньше 5. Какова наименьшая возможная сумма всех чисел на рёбрах?

Подсказка

Пример. Выберем 1009 рёбер без общих вершин, на них напишем 1, на остальных рёбрах — 2.

Решение

Ответ. 2019.2018-1009 = 4073333.

Решение. Пример. Выберем 1009 рёбер без общих вершин, на них напишем 1, на остальных рёбрах — 2. Сумма написанных чисел будет как раз 2•(2019•2018/2) $1009=4073333$ . Оценка. Назовём вершину плохой, если из неё выходит больше одного ребра, помеченного единицей. Если в графе нет плохих вершин, то всё в порядке: ребер с единицами не больше 1009, и сумма написанных не ребрах чисел не меньше $2 \cdot(2019 \cdot 2018 / 2)-1009$ . Пусть плохая вершина $A$ есть. Возьмём ребро $A B$ , на котором написана единица, и рассмотрим все треугольники вида $A B C$ . Если на одной из сторон $A C$ или $B C$ такого треугольника написана единица, то на другой должна быть тройка. Во всех таких случаях заменим эти единицу и тройку на две двойки. Сумма написанных на ребрах чисел при этом не изменится, сумма чисел на сторонах любого треугольника останется не меньше 5, а число плохих вершин уменьшится. Повторяя описанную процедуру, мы можем уничтожить все плохие вершины, а для графа без плохих вершин всё уже было доказано.