Низкая сложность

Для каждой комиссии создайте антикомиссию из всех не входящих в эту комиссию депутатов.

Ответ: 9.

Решение: Для каждой комиссии создадим антикомиссию из всех не входящих в эту комиссию депутатов. В каждой антикомиссии не меньше 11 депутатов, и разные антикомиссии не пересекаются (иначе в две соответствующие комиссии входили бы не все депутаты). Поэтому антикомиссий, а, стало быть, и комиссий не больше 9. Пример на 9: нумеруем депутатов числами от 1 до 100, и в -ую комиссию включаем всех, чей номер при делении на 9 даёт остаток, не равный .

Пусть первую республику со второй соединяют дорог. Тогда сколько дорог внутри республик?

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

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

Ответ: 11.

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

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

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

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

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

Ответ: 5.

Решение. Назовем невезучими детей, которые ни разу еще не побывали в хорошей команде. Стратегия Дмитрия Андреевича состоит в том, чтобы каждый раз называть хорошей команду, куда попала большая часть невезучих. Так ему после первого боя удастся сделать так, чтобы невезучих было не более 15, после второго — не более 7 , после третьего — не более 3 , после четвертого — не более одного. С другой стороны, если дети каждый раз будут делиться так, чтобы количества невезучих в двух командах отличались не более, чем на 1 , Дмитрию Андреевичу не удастся сделать всех везучими за 4 боя.

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

Отметим мальчиков синими точками, девочек — красными, а тех, кто танцевал друг с другом, соединим линиями. По условию из всех синих точек выходит поровну линий, и потому общее число линий делится на 30 . Из красных точек может выходить линий. Заметим, что . Чтобы не нашлось двух девочек, танцевавших с одним и тем же количеством юношей, надо вычесть из этой суммы число от 0 до 30 так, чтобы разность разделилась на 30 . Но единственное подходящее для этого число 15 по условию вычесть нельзя.

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

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

Цикл длины 4 можно получить, только соединив концы цепи длины 3. Поэтому тот, после хода которого образуется цепь длины 3, проиграл.

Ответ. Вася.

Решение. Цикл длины 4 можно получить, только соединив концы цепи длины 3. Поэтому тот, после хода которого образуется цепь длины 3, проиграл. Значит, концы цепи длины 2 соединять с другими точками нельзя. Стратегия Васи: после каждого хода Пети соединять ту же красную точку с какой-то синей, которая ещё не соединена ни с какой другой. Тогда после каждой пары ходов Пети и Васи число не соединённых с другими синих точек будет уменьшаться на 2 , и после 50 -го хода Васи каждая синяя точка будет концом цепи длины 2. Своим 51-м ходом Петя создаст цепь длины 3 и проиграет.

Пример. Пусть в группе 20 девочек и 20 мальчиков. Все девочки знакомы со всеми мальчиками, но никакие девочки не знакомы друг с другом и никакие мальчики не знакомы друг с другом. Легко видеть, что такая группа удовлетворяет условию.

Ответ: 40 школьников.

Решение. Пример. Пусть в группе 20 девочек и 20 мальчиков. Все девочки знакомы со всеми мальчиками, но никакие девочки не знакомы друг с другом и никакие мальчики не знакомы друг с другом. Легко видеть, что такая группа удовлетворяет условию.

Оценка. Предположим, что у какого-то школьника есть хотя бы 21 знакомый . По условию, все его знакомые незнакомы. Но тогда у школьника есть 20 незнакомых и они незнакомы друг с другом. Противоречие. Следовательно, у каждого школьника не более 20 знакомых и, аналогично, не более 20 незнакомых. Тогда школьников всего не более 41. Осталось доказать, что невозможен случай, когда школьников ровно 41 . Пусть так. Тогда у школьника ровно 20 знакомых и ровно 20 незнакомых . Причем все попарно незнакомы, а все попарно знакомы. У также должно быть ровно 20 знакомых, которые незнакомы между собой. Он уже знает и не знает никого из . Следовательно, он знаком с хотя бы 19 школьниками из . Но попарно знакомы. Противоречие.

Подвесим граф за вершину-столицу С. Вспомним, что вершины -го яруса определяются в точности как те вершины, расстояние от которых до C равно .

Введём граф, в котором вершины — города, рёбра — наличие авиасообщения. Подвесим граф за вершину-столицу С. Вспомним, что вершины -го яруса определяются в точности как те вершины, расстояние от которых до C равно . В таком графе рёбра могут быть либо внутри одного яруса, либо между ярусами с номерами, отличающимися на 1. Мы рассматриваем множества ребер, при удалении которых сохраняется ярус каждой вершины в нашем графе, будем называть их интересными. Если некоторое ребро соединяет две вершины одного яруса, то при включении или исключении интересность множества ребер не меняется. Таким образом, все интересные множества разбиваются на пары, что противоречит условию. Следовательно, в графе нет ребер, соединяющих вершины одного яруса. Тогда в любом цикле ярусы соседних вершин отличаются на 1 , тем самым они имеют разную четность. Значит, любой цикл в данном графе имеет четную длину, что и требовалось.