Средняя сложность — Задачи на Графы

Задача 005

01.01.2025 от

В школе организовали $n(n>1)$ кружков. Оказалось, что для любых двух школьников есть кружок, в который ходит ровно один из них, а для любых трёх школьников есть либо кружок, в который ходят все трое, либо кружок, в который не ходит ни один из них. Какое наибольшее количество учеников может быть в этой школе?

Подсказка

Сопоставьте каждому ученику число в двоичной записи.

Решение

Ответ: $2^{n-1}$ .

Решение: Пронумеруем кружки и сопоставим каждому ученику $n$ -значное двоичное число, где в $k$ ом разряде стоит 0 , если ученик не ходит в этот кружок, и 1 , если ходит. Так как для любых двух школьников есть кружок, в который ходит ровно один из них, у разных школьников будут разные коды. Далее, разобьём коды на пары, где коды в каждой из пар не совпадают ни в одном разряде. Так как по условию у любых трёх сопоставленных школьникам кодов должен быть разряд, в котором все три совпадают, из каждой такой пары может быть использовано не больше одного кода. Поэтому школьников не больше, чем половина числа $n$ значных двоичных кодов, то есть не больше $2^{n-1}$ . Пример на $2^{n-1}$ : использованы в точности все коды, начинающиеся с 1 .

Задача 008

01.01.2025 от

В чемпионате по футболу участвовало 72 команды. Каждые две команды встречались не более одного раза. Оказалось, что любые 48 команд провели между собой не менее 24 игр. Какое наименьшее количество игр могло состояться в этом чемпионате?

Подсказка

Рассмотрите вершину наибольшей степени. Удалите её из графа. Что можно сделать дальше?

Решение

Ответ: 72.

Решение: Обозначим команды точками, а матчи — соединяющими точки отрезками. Возьмем точку, из которой выходит больше всего отрезков, присвоим ей номер 1 и сотрем все исходящие из нее отрезки. После этого рассмотрим точку, из которой выходит больше всего оставшихся отрезков, присвоим ей номер 2, сотрем все исходящие из нее отрезки и т.д. Если из каждой из первых 24 точек перед стиранием выходило не меньше, чем по 2 отрезка, то всего отрезков не менее $2 \times 24+24=72$ , поскольку команды с номерами от 25 до 72 сыграли между собой не менее 24 матчей. Если же из точки 24 перед стиранием выходило не более 1 отрезка, то из точек от 25 до 72 в этот момент тоже выходит не более, чем по одному отрезку, и среди команд с номерами от 24 до 72 нетрудно найти 48 команд, сыгравшие менее 24 матчей. Итак, матчей сыграно не менее 72 . Пример на 72 матча: команды выстраиваются по кругу, и каждая играет со следующей по часовой стрелке. В самом деле, уберем 24 из этих 72 команд. Они уменьшили число сыгранных матчей максимум на $2 \times 24=48$ , поэтому оставшиеся 48 команд сыграли между собой не меньше 24 матчей.

Задача 009

01.01.2025 от

В день Св. Валентина $n$ влюбленных пар провели два однокруговых турнира по пинг-понгу — один для юношей, другой для девушек. Юноша и девушка из каждой пары вместе выиграли $n-1$ игру. Докажите, что количество троек юношей ( $A, B, C$ ), в которых $A$ обыграл $B, B$ обыграл $C$ и $C$ обыграл $A$ , равно количеству таких троек девушек.

Подсказка

Попробуйте сравнить не количество циклических троек, а количество оставшихся троек.

Решение

Занумеруем все пары числами от 1 до $n$ . Пусть в паре с номером $k$ юноша выиграл $a_{k}$ , а девушка $-n-1-a_{k}$ партий. Заметим, что тогда девушка из этой пары проиграла $a_{k}$ партий.

Заметим, что общие количества троек юношей и девушек равны. Поэтому, чтобы сравнить количества троек юношей и девушек ( $A, B, C$ ), в которых $A$ обыграл $B, B$ обыграл $C$ и $C$ обыграл $A$ (далее будем называть такие тройки циклическими) достаточно сравнить количества оставшихся (нециклических) троек. Заметим, что в каждой нециклической тройке есть ровно один человек, выигравший обе свои партии и ровно один человек, обе партии проигравший.

Рассмотрим теперь пару номер $k$ . Легко видеть, что количество троек юношей, в которых юноша из $k$ -й пары выиграл обе партии равно $\frac{a_{k}\left(a_{k}-1\right)}{2}$ . Поскольку в каждой нециклической тройке юношей есть ровно один юноша, одержавший две победы, количество таких троек равно $\sum_{k=1}^{n} \frac{a_{k}\left(a_{k}-1\right)}{2}$ . Аналогично, количество троек девушек, в которых девушка из $k$ -й пары обе партии проиграла, также равно $\frac{a_{k}\left(a_{k}-1\right)}{2}$ и, следовательно, количество нециклических троек девушек также равно $\sum_{k=1}^{n} \frac{a_{k}\left(a_{k}-1\right)}{2}$ .

Задача 010

01.01.2025 от

В лагере $2012^{2012}$ детей, у каждого не более трех друзей. Всегда ли можно их построить в ряд так, чтобы между любыми двумя друзьями стояло не более чем 2012 человек?

Подсказка

Попробуйте построить контрпример в виде дерева

Решение

Ответ: Не всегда.

Решение: Пусть Петя знаком с двоими, каждый из его знакомых — с двоими новыми, каждый из этих четверых — снова с двоими новыми и т.д., пока не перезнакомим всех $2012^{2012}$ детей. В получившемся «двоичном дереве» знакомств на $k$ -ом от Пети ярусе (кроме, возможно, самого последнего) — $2^{k}$ детей, поэтому ярусов в нем не больше, чем $m$ , где $m$ таково, что $2^{m-1}<2012^{2012}<2^{m}$ . Поскольку $2^{11}=2048>2012, m<11 \cdot 2012$ . Допустим, нам удалось построить детей нужным образом. Возьмем самого левого и самого правого. Между ними в построенном нами дереве есть путь длины не более $2 m<22 \cdot 2012$ . Но между любыми двумя соседями на этом пути в строю стоят не более 2012 человек. Поэтому длина строя должна быть не больше 2013•22•2012, что, очевидно, намного меньше, чем $2012^{2012}$ . Противоречие.

Задача 014

01.01.2025 от

На Луне п городов, некоторые из которых соединены платными дорогами так, что из любого города можно добраться до любого другого. Стоимость проезда по пути, проходящему через несколько городов, определяется как цена проезда по самой дорогостоящей дороге этого пути, а стоимость турпоездки из города $A$ в город $B$ — как стоимость проезда из А в В по самому дешевому пути. Докажите, что в прайс-листе лунного турагентства не более $n-1$ различных цен.

Подсказка

Предположите, что в графе есть цикл. Все ли рёбра цикла используются?

Решение

Если граф дорог — дерево, у него $n-1$ ребро, и утверждение задачи очевидно. Если же нет, выбросим самую дорогую из дорог, входящих в циклы. Поскольку можно считать, что эта дорога не используется (обходной путь по циклу не дороже), стоимости проезда между городами эта процедура не изменит. Будем повторять ее, пока не останется дерево.

Задача 017

01.01.2025 от

Известно, что некоторые сенаторы между собой в ссоре. Проверено, однако, что как бы мы не посадили их всех или любую группу (3 или более) из них по кругу, найдется пара соседей не в ссоре. Весь сенат усадили за круглый стол. Если два соседа не в ссоре, они могут поменяться местами. Докажите, что сенаторы могут расположиться в любом круговом порядке (порядки, полученные поворотом, не различаются).

Подсказка

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

Решение

Докажем индукцией по числу сенаторов. База. Для трех сенаторов есть только два круговых порядка. Они получаются друг из друга пересадкой двух соседей, которые не в ссоре. Шаг индукции. Найдется сенатор А, который в ссоре не более чем с одним сенатором (иначе часть сенаторов можно будет рассадить по кругу так, что у каждого соседями будут враги). Пусть Б в ссоре с А (а если А дружит со всеми, то Б — любой другой). По предположению индукции, если А уйдет из-за стола, то есть способ рассадить оставшихся в нужном круговом порядке. Однако это можно сделать и при наличии А. Придвинем А к Б (это можно сделать) и попросим А и Б взяться за руки. Считая эту пару сенатором Б, рассадим всех в нужном порядке вышеуказанным способом. Теперь можно А посадить на нужное место, последовательно «отодвигая» его от Б.

Задача 024

01.01.2025 от

В некотором графе степень каждой вершины не превосходит 1000. Докажите, что рёбра графа можно так покрасить в 10 цветов, что не найдется нечетного одноцветного цикла.

Подсказка

Лемма: Ребра полного графа на $2^{n}$ вершинах можно раскрасить в $n$ цветов так, чтобы граф с ребрами любого цвета был двудольным.

Решение

Доказательство: Лемма легко доказывается индукцией по $n$ , база для $n=1$ очевидна. Переход тоже несложен: разобьем вершины на две группы по $2^{n-1}$ вершине, все ребра между группами покрасим в цвет $n$ , граф из ребер этого цвета будет очевидно двудольным. Теперь для каждой из половинок покрасим ребра в цвета $1,2, \ldots, n-1$ (это можно по индукционному предположению). Графы этих цветов также будут двудольными, так как состоят из двух несвязанных двудольных частей каждый.

Теперь перейдем к решению задачи. Легко покрасить вершины данного графа $G$ степени не более 1000 правильным образом в $1024=2^{10}$ цветов (и даже в 1001 цвет). Теперь, рассмотрим раскраску в 10 цветов ребер полного графа на 1024 вершинах (вершины которого занумерованы цветами вершин графа $G$ ), в которой граф каждого цвета двудолен. Покрасим все ребра графа $G$ между вершинами цветов $i$ и $j$ также, как и ребро между вершинами $i$ и $j$ в раскраске полного графа. Очевидно, нечетных циклов в графе ребер любого цвета не будет.

Задача 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$ .