Уральский Турнир Юных Математиков

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

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

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

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

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

Ответ: 56.

Решение: Пример на 56 команд получаем, выбрав 8 задач и рассмотрев все 56 составленных из них троек: они удовлетворяют всем условиям задачи. Допустим, мы выбрали больше 56 троек задач. Назовём две непересекающиеся тройки задач запрещённой парой, если задачи, не входящие ни в одну из этих двух троек, образуют выбранную тройку. Понятно, что хотя бы одна из двух троек, образующих запрещённую пару, не должна быть выбранной. Поскольку из шести задач можно выбрать три способами, каждая выбранная тройка порождает 10 запрещённых пар, причём, очевидно, разные тройки порождают разные запрещённые пары. При этом для каждой тройки задач существует 20 не пересекающихся с ней, то есть каждая тройка входит не больше, чем в 20 запрещённых пар. Если мы выбрали хотя бы 57 троек, у нас не меньше 570 запрещённых пар, в которые входит не менее различных троек задач. Но из 9 задач можно образовать лишь тройки, поэтому невыбранными останутся максимум 27 троек. Значит, какие-то две выбранные задачи образуют запрещённую тройку. Противоречие.

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

Ответ: 11.

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ. Вася.

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