Подсчёты в графах — Задачи на Графы

Задача 005

01.01.2025 от

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

Подсказка

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

Решение

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

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

Задача 007

01.01.2025 от

На вечеринку собрались несколько мальчиков и несколько девочек. После вечеринки выяснилось, что для каждой пары девочек есть ровно три мальчика, которые танцевали и с той, и с другой, а для каждой пары мальчиков есть ровно три девочки, которые танцевали и с тем, и с другим. Докажите, что на вечеринке было поровну мальчиков и девочек.

Подсказка

Рассмотрите отдельно пары из двух мальчиков, знакомые с парами из двух девочек.

Решение

Скажем, что пара мальчиков и пара девочек сопряжены, если каждый мальчик из первой пары танцевал с каждой девочкой из второй. Из условия следует, что каждая пара мальчиков сопряжена ровно с тремя парами девочек, а каждая пара девочек — ровно с тремя парами мальчиков. Отсюда следует, что пар мальчиков столько же, сколько пар девочек, а именно — втрое меньше общего числа сопряжённых пар. Таким образом, если мальчиков на вечеринке было $m$ , а девочек — $d$ , то $m(m-1)=d(d-1)$ , откуда $m=d$ .

Задача 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 матчей.

Задача 011

01.01.2025 от

В некоторой стране 100 городов. Любые два города этой страны соединены дорогой. От этой страны отделилась независимая республика, причем количество дорог, соединяющих города этой республики, равно количеству дорог, ведущих из республики в остальные города этой страны. Сколько городов в отделившейся республике? (Приведите все варианты и докажите, что других нет).

Подсказка

Обозначьте число городов в республике за х.

Решение

Ответ: 67.

Решение: Пусть в отделившейся республике $x$ городов. Тогда количество дорог, соединяющих ее города, равно $x(x-1) / 2$ (из каждого из $x$ городов выходит по $x-1$ дороге, и каждая дорога при этом считается дважды), а количество дорог, ведущих из республики в остальные города страны, равно $x(100-x)$ . По условию $x(x-1) / 2=x(100-x)$ . Сократив на $x$ и решив получившееся уравнение, находим ответ.

Задача 012

01.01.2025 от

Существует ли такая компания из 125 человек, в которой каждый человек имеет ровно 50 знакомых и любые двое людей имеют общего знакомого тогда и только тогда, когда они сами незнакомы?

Подсказка

Разбейте 125 человек на 5 групп.

Решение

Ответ. Существует.
Решение: Разобьём 125 человек на 5 групп по 25 человек, расставим группы по кругу, и пусть каждый дружит со всеми пятьюдесятью из двух соседних групп. Легко проверить, что все условия задачи при этом выполнены.

Задача 015

01.01.2025 от

В классе 29 детей. Каждый из детей послал новогодние подарки 9 своим одноклассникам. Всегда ли найдутся трое детей, ни один из которых не посылал подарки никому из двух других?

Подсказка

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

Решение

Ответ: Нет.

Решение: Построим пример. Выстроим учеников по кругу, и пусть каждый пошлёт подарки 9 следующим по часовой стрелке. Возьмём любых троих и рассмотрим три десятки учеников каждая из которых состоит из одного из трёх взятых и девятерых, которым он послал подарки. Если никто из этих троих не посылал никому подарка, то три этих десятки учеников не должны пересекаться. Но тогда в классе не меньше 30 учеников, а по условию их там 29.

Задача 018

01.01.2025 от

На танцах было $2 n$ мальчиков и $2 n$ девочек. Боря танцевал со всеми девочками, Аня танцевала со всеми мальчиками, и для любых двух девочек есть ровно n мальчиков, танцевавших ровно с одной из них. Докажите, что каждый мальчик, кроме Бори, танцевал ровно с $n$ девочками.

Подсказка

Рассмотрите вместе с Аней ещё одну (любую) девочку. Что следует их условия?

Решение

Возьмём Аню и любую другую девочку Д. По условию, ровно с одной девочкой из этих двух танцевало ровно $n$ мальчиков. Так как с Аней танцевали все мальчики, то эти $n$ мальчиков танцевали именно с ней, а остальные $n$ мальчиков танцевали и с ней, и с Д. Итак, с каждой девочкой, кроме Ани, танцевали ровно $n$ мальчиков. Возьмём любых двух таких девочек. Пусть с обеими танцевали $m$ мальчиков. Тогда ровно с одной танцевали $n=2(n-m)$ мальчиков, откуда $m=n / 2$ .

Забудем про Аню и Борю. Тогда каждая из девочек танцевала с $n-1$ мальчиком, а с каждыми двумя девочками танцевали $n / 2-1$ мальчиков. Занумеруем мальчиков и пусть $i$ -ый мальчик танцевал с $d_{i}$ девочками. Тогда троек, состоящих из мальчика и двух девочек, с которыми он танцевал, будет $d_{1}\left(d_{1}-1\right) / 2+\ldots+d_{2 k-1}\left(d_{2 k-1}-1\right) / 2$ . С другой стороны, число таких троек равно $n / 2-1$ , умноженному на количество пар девочек, то есть $(n / 2-1)(2 n-1)(n-1)$ .
Заметим, что

$d_{1}\left(d_{1}-1\right) / 2+\ldots+d_{2 k-1}\left(d_{2 k-1}-1\right) / 2=\left(d_{1}^{2}+\ldots+d_{2 n-1}^{2}\right) / 2-\left(d_{1}+\ldots+d_{2 n-1}\right) / 2 \text {. }$

Так как $d_{1}+\ldots+d_{2 k-1}=(n-1)(2 n-1)$ (считаем ту же сумму «со стороны девочек»), то получаем, что

$d_{1}^{2}+\ldots+d_{2 n-1}^{2}=2(n / 2-1)(2 n-1)(n-1)+(n-1)(2 n-1)=(n-1)^{2}(2 n-1) .$

С другой стороны, по неравенству между средним арифметическим и средним квадратическим

$d_{1}^{2}+\ldots+d_{2 n-1}^{2} \geq\left(d_{1}+\ldots+d_{2 n-1}\right)^{2} /(2 n-1)=(n-1)^{2}(2 n-1)$

причём равенство достигается только при $d_{1}=\ldots=d_{2 k-1}$ . Итак, все $d_{i}$ равны между собой, откуда $d_{i}=n-1$ , что и (вспомним про Аню!) требовалось доказать.

Задача 020

01.01.2025 от

В классе поровну мальчиков и девочек, и все ученики разного роста. Оказалось, что если мальчик дружит с девочкой, то он дружит и со всеми девочками выше неё; и наоборот — если девочка дружит с мальчиком, то она дружит и со всеми мальчиками выше него. Учитель физкультуры хочет выстроить детей в ряд, начиная с мальчика, так, чтобы любые двое соседей в ряду были друзьями разного пола. Оказалось, что количество способов это сделать — натуральное число $N$ , делящееся на 101. Каким наименьшим количеством нулей может оканчиваться десятичная запись числа $N$ ?

Подсказка

Для начала докажите лемму.

Лемма. $N=\left(a_{1} a_{2} \ldots a_{k}\right)^{2}$ , где $a_{1}, \ldots, a_{k}$ — некоторая последовательность неотрицательных целых чисел такая, что $i \geq a_{i} \geq a_{i+1}-1$ при всех $i=1,2, \ldots, k-1$ .

Решение

Ответ. 48.
Решение: Назовём исследуемые расстановки легальными. Пусть $k$ количество мальчиков. Пример получается при $k=101$ , когда все дружат. Действительно, тогда $N=(101!)^{2}$ , причём 2 входит в 101 ! хотя бы в 50 степени, а 5 — в степени $[101 / 5]+\left[101 / 5^{2}\right]=24$ , ибо $101<5^{3}$ . Значит, $N$ оканчивается ровно 48 нулями.

Сначала выведем оценку из леммы. Поскольку $N$ натурально, $a_{1} \geq 1$ , то есть $a_{1}=1$ . Если $N$ делится на 101 , то одно из чисел $a_{1}, \ldots, a_{k}$ делится на $101-$ скажем, это $a_{j}$ . Из условий $a_{i-1} \geq a_{i}-1$ следует, что среди чисел $a_{1}, \ldots, a_{j-1}$ встретятся все числа от 1 до 100 , то есть $N$ делится на ( $100!)^{2}$ и, следовательно, на $10^{48}$ .

Осталось доказать лемму. Числа $a_{k-i}$ будут определяться так. Выкинем из компании $i$ самых маленьких девочек и $i$ самых больших мальчиков. Тогда $a_{k-i}$ — это количество оставшихся мальчиков, знакомых со всеми оставшимися девочками. Из этого описания немедленно следуют условия на $a_{i}$ , указанные в лемме.

Индукция по $k$ . При $k=1$ имеем $N=1=a_{1}$ . Пусть теперь $k>1$ . Рассмотрим самую маленькую девочку $d$ ; пусть $M$ — множество мальчиков, которые с ней дружат, $|M|=a_{k}$ . Заметим, что $M$ состоит из $a_{k}$ самых высоких мальчиков.

В любой легальной расстановке перед $d$ стоит мальчик $m$ из $M$ , а после неё — либо мальчик $m^{\prime}$ из $M$ , либо никто. Так как $m^{\prime}$ , если он существует, знаком со всеми девочками, то после выбрасывания пары ( $m, d$ ) из расстановки получится легальная расстановка оставшихся детей. Наоборот, в любую легальную расстановку $2(k-1)$ детей, отличных от $m$ и $d$ , пару ( $m, d$ ) можно вставить либо перед произвольным $m^{\prime} \in M\{m\}$ , либо в конец, то есть $a_{k}$ способами.

Далее, поскольку $m$ дружит со всеми, для всех $m \in M$ после выкидывания пары ( $m, d$ ) останутся «одинаковые» компании детей (научным языком, графы их дружб изоморфны). Поэтому в них будет поровну легальных расстановок, и эти количества будут по предположению индукции иметь вид $N^{\prime}=\left(a_{1} a_{2} \ldots a_{k-1}\right)^{2}$ . Итак, для каждого из $a_{k}$ мальчиков из $M$ в каждую из $N^{\prime}$ перестановок можно вставить пару ( $m, d$ ) ровно $a_{k}$ способами. Значит, $N=N^{\prime} a_{k}^{2}$ , что и требовалось.

Задача 021

01.01.2025 от

В компании из 300 человек каждый знаком ровно с тремя другими. При каком наименьшем $k$ про такую компанию можно наверняка утверждать, что среди любых $k$ человек найдутся двое знакомых?

Подсказка

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

Решение

Ответ: 151.
Решение: Допустим, удалось выбрать 151 человека, не знакомых друг с другом. У них вместе 453 знакомства с оставшимися 149 людьми, но у тех вместе всего 447 знакомств — противоречие. Таким образом, среди любых 151 человека найдутся двое знакомых. Покажем, что 150 человек, не знакомых друг с другом, могут найтись. Разобьём компанию на 50 шестёрок, каждую шестёрку — на две тройки, и пусть в каждой шестёрке каждый человек из одной тройки знаком с каждым человеком из другой; в набор из 150 человек возьмём по одной тройке из каждой шестёрки.

Задача 023

01.01.2025 от

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

Подсказка

Сколько боёв было сыграно в любой из школ?

Решение

Каждая команда сыграла в чемпионате 15 боев. Чтобы поиграть во всех школах, кроме своей, она должна была сыграть в каждой из них по одному разу. Но это значит, что в любой данной школе за время чемпионата должны были сыграть по одному разу 15 команд (все, кроме своей). Но в каждом бое участвуют две команды, поэтому общее число команд, игравших в данной школе, должно быть чётным. Полученное противоречие показывает, что так, как сказано в условии задачи, случиться не могло.