Комбинаторика на ОММО: графы, турниры, логика, Дирихле

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

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

Всего у каждого из семи подписанных на канал учеников может быть не более трёх хороших друзей. Следовательно, изначально количество хороших пар не превышает 21. Рассмотрим момент, когда на канал подписались все ученики, кроме одного. Тогда в момент, когда подпишется последний ученик, количество хороших пар уменьшится уже на 3, следовательно, подписок может быть не более чем 19. Так как в классе всего 28 человек, то весь класс не может быть подписан на канал.

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

У кроме есть ещё знакомых, а у , кроме ещё Поскольку то у и есть хотя бы один общий знакомый Тройка и есть искомая тройка человек.

Заметим, что количество авантюристов, у которых есть сапфиры, равняется суммарному количеству авантюристов, у которых есть изумруды или бриллианты. Тогда из первого условия следует, что у 9 авантюристов есть сапфиры и изумруды, а у 6 — сапфиры и бриллианты. Т.е. у каждого авантюриста, у которого есть изумруды, обязательно есть сапфиры. Тогда, из второго условия, не может быть авантюриста, у которого есть и изумруды, и рубины. Значит, авантюристов как минимум

Столько авантюристов и правда может быть: пусть у нас есть 9 авантюристов, у которых есть сапфиры и изумруды, 6 авантюристов, у которых есть сапфиры, бриллианты и рубины, а также 7 авантюристов, у которых есть только рубины. Можно убедиться, что этот пример подходит под все условия.

Посмотрим на числа Пусть

Заметим, что отображение переводит числа в числа соответственно, а отображение — в числа соответственно.

Кроме того, заметим, что

Поэтому если то каждое из чисел лежит в причём этот набор переходит в себя под действием и

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

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

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

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

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

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

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

противоречие.

• Пусть соврал Андрей. Тогда он первый или последний, но Игорь и Коля сказали правду — отсюда они занимают первое и последнее место, противоречие.
• Пусть соврал Максим. Отсюда он и Коля одновременно последние, снова противоречие.
• Пусть соврал Игорь, то есть он не первый. Тогда Коля последний, Андрей может быть вторым, а Максим — первым, отсюда Игорь — третий и все остальные сказали правду.
• Пусть соврал Коля, то есть он не последний. Но Максим и Андрей не последние, раз они сказали правду, а Игорь — первый, то есть последнее место никто не занимал, противоречие.

В итоге соврать мог только Игорь, в этом случае есть несколько распределений, в решении выше приведён пример одного из них.

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

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

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

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

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

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

Заметим, что борец с номером может проиграть только борцу с номером или , поэтому после каждого тура наименьший номер не может увеличиться больше, чем на номера. На турнире с участниками туров, следовательно, номер победителя турнира не превосходит

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

Аналогично, после второго тура останутся борцы с номерами и , после третьего: и , после седьмого: и Значит, в последнем, финальном, бою встретятся борцы с номерами и . Противоречие с предположением, что борец с номером может победить.

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

Первое решение.

Обозначим детей, давших ответы через А, Б, В соответственно. Заметим, что если в классе мальчиков, то первое число в ответах девочек имеет ту же чётность, что и , а в ответах мальчиков - противоположную. Следовательно, дети А и Б одного пола, а В - другого.

Первые числа в ответах А и Б отличаются на 4, значит, они оба неправильные. Таким образом, количество одноклассников у А и Б равно 15 , а количество одноклассниц - 11 .

Если А и Б - мальчики, то в классе 16 мальчиков и 11 девочек. При этом у девочки В тогда 16 одноклассников и 10 одноклассниц, и ее ответ противоречит условию. Значит, А и Б девочки, и в классе 15 мальчиков и 12 девочек. ______________________

Второе решение.

Пусть какой-то ребёнок написал числа . Если бы оба числа он написал правильно, то он бы написал один из четырёх вариантов: .

Тогда, если этот ребёнок — мальчик, то существует четыре варианта количества мальчиков и девочек в классе: и .

Аналогично, если этот ребёнок — девочка; возможные варианты в этом случае: .

Таким образом, каждый из ответов даёт нам восемь вариантов, сколько мальчиков и девочек могло быть в классе, один из которых должен быть верным:

для это ;

для это ;

для это .

Осталось заметить, что только вариант встречается во всех трёх строчках.

Разберём два возможных случая:

• Если A сказал правду, что В — рыцарь, то слова В о том, что А — не рыцарь, должны быть верны. В этом случае А сказал правду и А — не рыцарь, так что условие задачи выполняется.
• Если А солгал, что В — рыцарь, то и А не может быть рыцарем (потому что рыцарь не мог солгать). Так что В сказал правду. При этом В не является рыцарем, потому что А солгал. Под условие задачи подходит человек В.

Итак, в обоих случаях получаем требуемое.

Рассмотрим два возможных случая:

• А сказал правду, то есть В выше С.

  Если В сказал правду, то оба они выше А. Тогда А — лжец. Противоречие с тем, что мы рассматриваем случай, когда А сказал правду.

  Если же В солгал, то он обычный человек среднего ранга (не ниже всех), отсюда С — лжец и А — рыцарь. Тогда С скажет, что В выше А, то есть соврёт.

• А солгал, то есть на самом деле С выше В.

  Если В сказал правду, то он обычный человек среднего ранга, а С — рыцарь. То есть А — лжец, что соответствует словам В. Отсюда С скажет, что В выше А.

  Если же В солгал, то А выше С, а также С выше В. Отсюда А — рыцарь. Противоречие с тем, что мы рассматриваем случай, когда А солгал.

Итак, С скажет, что В выше А.

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

В первом А — лжец. Тогда А соврал о том, что В — рыцарь и В на самом деле лжец. Но тогда В сказал правду !?

Во втором А — рыцарь. Тогда А сказал правду и В действительно рыцарь. Но В сказал, что А — лжец !?

Итого, А может быть только обычным человеком. Следовательно, получили противоречие с предположением.

Рассмотрим случаи:

В первом А — рыцарь. Тогда В и С действительно однотипны. Если В и С — рыцари, то С ответит “Да”, как и в случае, если В и С — лжецы.

Во втором А — лжец. Тогда В и С не однотипные. Если В — лжец, а С — рыцарь, то С ответит “Да”, как и в случае, если В — рыцарь, а С — лжец.

Итого, в любом случае С ответит “Да”.

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

то существует набор чисел, в сумме дающих единицу, таких, что каждое больше соответствующей дроби. Любой такой набор подходит.

Первое решение.

На четыре вопроса каждый рыцарь даёт один утвердительный ответ, а лжец — три. Всего было получено утвердительных ответов. Если бы все жители города были рыцарями, в сумме всех утвердительных ответов было бы 200. 100 лишних ответов «да» происходят от вранья лжецов. Таким образом, лжецов . Пусть в квартале Б живет рыцарей, тогда —число утвердительных ответов на второй вопрос, которые дали лжецы. Значит число лжецов, живущих в квартале Б, равно . В остальных кварталах число лжецов меньше числа рыцарей.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Пусть и — количества рыцарей и лжецов в -м квартале из соответственно, — рыцарей всего, — лжецов всего. Тогда

Введём обозначения — насколько в квартале больше лжецов, получим

В итоге наибольшее достигается для . Далее просуммируем уравнения, получим

Имеем . Отсюда лжецов больше только во втором квартале на .