Графы и турниры

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

Матчей всего . Если матч закончился вничью, то в нём было разыграно очка, иначе – . Ничейных матчей не более , поэтому суммарно очков в турнире было набрано не менее .

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

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

 Если ответ угадан и приведѐн пример турнира: 1 балл.

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

Не приведѐн пример турнира: минус 1 балл.

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

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

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

Мы проверили, что при всех Тогда по формуле т. е. граф оказался неконтрпримером.

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

1.

В какой-то момент встретился полный граф. То есть мы выбрали таким образом несколько пар а в оставшемся графе без этих пар вершин не нашлось несмежной пары вершин, причём . Тогда в оставшейся части рёбер

Теперь учтём остальные посчитанные рёбра. Их хотя бы

по формуле арифметической прогрессии. Итого, хотя бы

рёбер в графе. Так как — парабола с ветвями вверх и где — абсцисса вершины параболы, то при рёбер в графе хотя бы

2.

Полный граф не встретился, значит, , а вершины закончились, тогда аналогично предыдущему пункту рёбер в графе хотя бы

Таким образом, в графе в любом случае хотя бы рёбер. То есть у нас есть оценка, осталось построить пример на рёбер.

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

_________________________________________________________________________________________________________________________________________________________________________________

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

База индукции: Оценка очевидна.

Шаг индукции: Пусть доказано для , докажем для .

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

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

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

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

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

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

Рассмотрим октаэдр. Пусть каждый человек соответствует вершине октаэдра.

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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Первое решение на самом деле дает оценку на человека, второе — даже на человек.

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

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

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

Всего было фигур, каждая фигура использована раза. Поэтому Н называли только Аня один раз и Глеб три раза. Значит, у Бори и Вовы три раза Б и три раза К.

В сумме набрано баллов. Если бы у Глеба был балл или больше, на месте было бы балла или больше, на втором балла или больше, на первом балла или больше и в сумме было бы баллов или больше. Поэтому у Глеба или баллов. Глеб ни разу не выигрывал и максимум раз сыграл вничью. Аналогично, Аня не могла набрать балла или меньше. Т. е. у Ани или балла. Аня ни разу не проигрывала и максимум раз сыграла вничью.

У Бори и Вовы раза Б и раза К. Значит, вничью с Глебом они сыграть не могли, поэтому оба у него выиграли, поэтому оба показали Глебу К. У одного из них ББК, у другого ККБ.

Теперь рассмотрим случая. Боря и Вова показали друг другу Б. Или Боря и Вова показали друг другу КБ.

Боря и Вова показали друг другу Б. Тогда Ане все три мальчика показали разные фигуры. Если бы Аня хоть один раз сыграла вничью, то другие игры либо тоже вничью, либо одна выигрыш, другая проигрыш. Поэтому Аня вничью с ними играть не могла и должна была все три игры выиграть. Но тогда у Бори и Вовы было бы одинаковое количество баллов балла). Поэтому этот случай невозможен.

Боря и Вова показали друг другу КБ. Тогда Ане оба показали Б. Аня не могла проиграть Глебу, поэтому Глебу она показала не Б. Значит, Б она показала Боре или Вове, сыграв вничью. Поэтому у других двоих она должна была выиграть. Т. е. Глебу показала К, а третьему парню — Н. Аня набрала балла. Если бы в борьбе Бори и Вовы выиграл тот, что сыграл с Аней вничью, у него тоже было бы балла. Поэтому в борьбе Бори и Вовы выиграл тот, который проиграл Ане. И он на месте (2 балла у него). Боря выиграл у Вовы, показав Б. Вова, соответственно, показал Боре К.

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

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

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

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

Что и является ответом.

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

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

Так как Буратино отдал сначала золотых, а проиграл то ему вернули золотых, значит, ровно его прогноза были верными. Если верен прогноз (ничья), то автоматически верен и прогноз тогда остальные прогнозы ошибочны, значит, из неверного прогноза следует, что Кроты не пропустили ни одного гола, т.е. матч закончился со счетом Если прогноз — ошибочный, то окажется ошибочным и прогноз т.к. иначе будут верны ещё прогнозы и уже три верных прогноза — противоречие. Значит, ошибочны прогнозы и верны и тогда Кроты выиграли матч, пропустив хотя бы гол, а в сумме с Канарейками забили три, т.е. матч закончился со счётом

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

А игр между девочками было

Посчитаем разницу между количеством парнтий между мальчиками и девочками во всём турнире:

Итак, мы получили, что число партий между мальчиками больше числа партий между девочками на что кратно 5, а, значит, не может быть равно 23.

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