11 класс

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

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

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

Построим следующий граф: вершины — игроки, рёбра — сыгранные партии. Согласно условию, для обоих турниров этот граф один и тот же. Рассмотрим первый турнир и выберем те партии, победители которых до этого не выигрывали (например, такова первая партия).

Ответ. 3.

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

Теперь рассмотрим тот же граф как граф кубкового турнира. Если из него выбросить висячие вершины, останется граф турнира на победителях первого этапа. Он, очевидно, является путём лишь при , в противном случае победитель турнира будет иметь степень не меньше 3 . Значит, .

Осталось привести пример при . Пусть участники пронумерованы от 1 до 8 и пары в кубке таковы (первым указан проигравший, вторым победитель): , тогда при игре навылет пары могли быть такими (победитель снова указан вторым): , .