7 класс

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

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

Пусть из Иксии в Игрекию ведёт дорог. Сколько ещё дорог в республиках?

Ответ. 500. Решение. Пусть из Иксии в Игрекию ведёт дорог. Тогда из городов Иксии в совокупности выходит дорог, а из городов Игрекии — дорог ( и умножаются на 2 , так как каждая дорога, соединяющая города одной республики, считается тут дважды). Вычитая два полученных равенства и деля результат пополам, получаем ответ.

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

Ответ: Нет. Решение. Допустим, есть команда, не сыгравшая ни одного матча. Тогда каждая из оставшихся команд сыграла не больше 9 матчей: с каждой из остальных восьми плюс один повторный. Получается 9 возможностей матчей) на 19 команд. Но тогда эти команды вместе сыграли матчей, что невозможно.

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

Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим 250 пауков (всего 1000 городов). Если , то в одном из пауков выбраны все 4 города, что противоречит условию.

Ответ. . Решение. Пример. Назовем пауком город, соединенный ровно с тремя другими, попарно не соединенными дорогами. Рассмотрим 250 пауков (всего 1000 городов). Если , то в одном из пауков выбраны все 4 города, что противоречит условию.

Оценка. Рассмотрим граф: вершины — города, рёбра — дороги. Если граф не связный, будем проводить по ребру между компонентами связности, пока он не станет связным. Ясно, что такая процедура не увеличит искомое число и не добавит в граф циклы.

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

База: очевидна.
Переход: от всех меньших к . Подвесим дерево за вершину и рассмотрим вершину самого нижнего уровня. Если у ее предка не менее трёх потомков, то выкинем и всех ее потомков.

В оставшемся дереве выберем хорошее множество и добавим всех потомков . Полученное множество будет хорошим для исходного дерева, и в нём не менее вершины.

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

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

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

Ответ. 2695. Решение. Покажем, как могло оказаться 2695 человек. Разобьём их на 4 группы размером и 673 . Сделаем людей внутри одной группы незнакомыми, а в разных — знакомыми.

Ответ. 2695. Решение. Покажем, как могло оказаться 2695 человек. Разобьём их на 4 группы размером и 673 . Сделаем людей внутри одной группы незнакомыми, а в разных — знакомыми. Тогда у каждого человека знакомых минимум , а пяти попарно знакомых точно нет.
Докажем, что менее 2695 человек быть не могло. Предположим, что у нас людей. Тогда у каждого не более незнакомых. Будем набирать группу из попарно знакомых. Когда мы добавляем к ней любого человека, он запретит с учётом себя не более . Поскольку , то после того как наберём не более четверых, не запрещённые останутся, поэтому можно будет добавить человека в нашу группу. Получается, найдётся группа из 5 попарно знакомых.

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

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

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

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

Ответ. 51 человек.

Решение: Оценка. Рассмотрим граф с 99 вершинами, рёбра соответствуют знакомствам. Выкидывание вершины с рёбрами не увеличивает степени остальных, потому степень каждого следующего выходящего (на момент выхода) хотя бы на 2 меньше предыдущей. Поэтому их степени не больше соответственно. Но удалить вершину степени 2 невозможно, так как есть ещё ненулевые степени, а вершины степени 1 и 0 не подходят по условию. Таким образом, из комнаты выйдет не более 48 человек.

Пример. Пусть человек с номером знаком с людьми с номерами от до 99, других знакомств нет. Уходить они будут по порядку от 1 до 48 . На момент ухода -го человека: ему не знакомы только следующих за ним, остальным из этих 48 — хотя бы следующих и предыдущий, а последним 51 — хотя бы 50 , что тоже не меньше .