Соответствия, сравнения, количества

(a) Будем выбирать подмножества и следующим образом: сначала выберем множество мощности и выберем из него подмножество Тогда

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

Просуммируем по всем и получим:

(b) Этот пункт можно решить аналогично предыдущему (сказав, что достаточно выбрать непересекающиеся множества и но мы сделаем немного иначе.

Для каждого элемента имеется состояния: не лежит ни в ни в лежит в но не в лежит и в и в Тогда, поскольку определение состояния каждого элемента однозначно задает нам и и наоборот, то мы получаем, что всего случаев будет

Пусть — множество всех таких наборов , что

— множество всех таких наборов что

Построим биекцию между множествами и Для этого каждому набору из множества поставим в соответствие набор который лежит в поскольку

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

Обозначим за количество -элементных неизолированных подмножеств множества Вычислим зная Рассмотрим произвольное подмножество множества Если оно не содержит число то значит мы его посчитали уже в Поэтому, рассмотрим которое содержит число По условию оно также должно содержать число Далее рассмотрим два случая, первый если а второй если В первом случае, оставшиеся числа множества должны быть вида и где — натуральное число, которое меньше, чем Следовательно, в первом случае количество таких множеств равно Во втором же случае мы получим, что оставшиеся числа множества будут иметь вид: где — натуральное число, которое меньше Поэтому в этом случаем количество множеств получается равно Откуда следует, что для Заметим, что Следовательно,

Это можно преобразовать используя формулу суммы чисел от до в такое:

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

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

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

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

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

Петя просто считает количество диаграмм Юнга с весом высотой и шириной Вася же считает те же диаграммы Юнга, но в которых нет столбца высоты Теперь давайте у каждой такой диаграммы, у которой есть столбец высоты его уберем. Тогда мы как раз получим диаграммы Юнга с весом с высотой и шириной А это то что считала Маша. Поэтому в сумме они насчитали столько же сколько и Петя.

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

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

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

Далее, пусть — все числа множества из интервала аналогично, пусть — все числа множества из интервала Применив условие к числам и получаем, что число лежит в поскольку два других возможных числа находятся вне (в самом деле, и При этом — различные числа из интервала Значит, каждое должно совпадать с каким-то при этом последовательно получаем, что в частности, видим, что Аналогично, применив условие к числам и получаем, что При этом — числа из интервала совпадающие с какими-то Последовательно получаем, что в частности, видим, что

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

Решая эту систему, получаем, что Значит, никакие числа интервалов и за исключением точек не могут принадлежать множеству Следовательно, и значит,

______________________________________________________________________________________________________________________________________________________

Замечание. Предложим другой возможный путь доказательства оценки. Снова пусть причем и — это минимальное и максимальное числа из Предположим, что в множестве есть число отличное от Не умаляя общности, пусть положим Применяя условие к и получаем, что

при этом Затем применяя условие к и получаем, что

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

Пример. Достаточно выбрать наибольших элементов из множества.

Оценка. Для каждого нечетного натурального зададим множество

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

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

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

Оценим количество ребер между людьми из разных множеств и

С одной стороны, не больше суммы степеней вершин множества откуда

С другой стороны, из каждой вершины множества не более ребер идет в вершины множества и значит, не менее ребер идет в вершины множества Отсюда

Получаем неравенство:

откуда Это означает, что всего лжецов не менее

Пример. Как и прежде, номер человека будет означать его ответ. Возьмем два множества людей:

и

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

У человека будет всего друзей:

из множества и все люди множества кроме него самого. При этом все люди в — лжецы, а в — рыцари. Видим, что все условия задачи выполняются.

Если код составлен из чисел от до , то для каждого числа

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

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

Рассмотрим произвольное -элементное подмножество. Назовём сдвигом множества прибавление к каждому элементу. Будем двигать рассматриваемое подмножество до тех пор, пока не сдвинем его раз. Мы получили подмножеств из элемента. Во-первых, эти множества имеют различные суммы по модулю Предположим противное, пусть у множество была сумма его сдвинули раз и получили такой же остаток при делении на В таком случае то есть кртано но это невозможно, потому что и взаимнопросты, а — число от до Следовательно, среди этих подмножеств сумма элементов делится на только в одном.

Таким образом, -элементые подмножества разбиваются на группы по подмножеств, в каждой из которых только у одного сумма элементов делится на Значит, ответом будет — количество -элементных подмножеств, поделённое на

Сначала покажем, что можно выбрать не более чем подмножество из элементов, чтобы условие выполнялось. Для достаточно взять все -элементные подмножества и условие будет выполнено, а таких множеств поэтому формула выполняется.

Для подмножество такого размера единственно, поэтому формула снова верна.

Для докажем по индукции. База индукции тогда а при таких формула выполняется.

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

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

Далее удалим из набора подмножество Теперь объединение всех подмножеств не совпадает с иначе бы опять встретилось подмножество Опять-таки по предположению индукции подмножеств станет Тогда изначально с подмножество было не более

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

Рассмотрим все подмножества вида где Тогда и так как то содержит наименьшие элементов объединения.

Каждому остатку от деления на 19 сопоставим остаток такой, что

Заметим, что остаткам сопоставлены остатки соответственно. Более того, по остатку восстанавливается остаток такой, что и (из аналогичных соображений).

Обозначим теперь через множество чисел из условия, не содержащих цифр , а через — множество таких чисел, не содержащих . Каждому числу сопоставим число . Заметим, что — цифра (причём ), так что получилось 100 -значное число. Кроме того,

так что делится на 19 и . Поскольку разным числам из соответствуют разные числа из , количество чисел в не меньше, чем в .

Наконец, каждому числу соответствует число , которое по аналогичным причинам лежит в . Отсюда следует, что количества чисел в и равны.

На -м шаге у каждого из человек было выписано одно из чисел множества

На -м шаге — одно из чисел множества

На -м шаге выписано одно из чисел множества

где — сумма всех чисел (а вычитается — число на оставшейся в конце карточке).

Видим, что так что Далее, но числа принадлежат значит,

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

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

— множества участников каждой олимпиады такие, что пересечение любых 30 из них непусто, а пересечение всех — пусто.

Пусть среди множеств

нашлись два множества и имеющие общих элементов

Для каждого элемента среди множеств

найдём подмножество не содержащее такое подмножество найдётся, иначе — общий элемент множеств

(Заметим, что среди подмножеств могут быть совпадающие.)

Тогда пересечение не более подмножеств

— пусто. Это противоречит нашему предположению (к данным подмножествам можно добавить еще несколько, чтобы стало 30 подмножеств, при таком добавлении пересечение остается пустым).

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

содержит в точности элементов. Пусть

так что

Найдём подмножество (пусть, для определённости, это подмножество — ), не содержащее Так как

то обязано содержать все элементы

Этих элементов (все они различны), поэтому

Рассмотрим любое подмножество из подмножеств Предположим, что содержит элемент, лежащий вне -элементного множества

Тогда должно пересекаться с каждым из подмножеств по одному и тому же -элементному подмножеству множества Но

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

Начнем раздавать конфеты по одной домовикам. Возможны три варианта.

1) Конфеты кончились, а домовики еще остались. Тогда каждой конфете соответствует свой домовик, но не всем домовикам достались конфеты. Значит, домовиков больше, чем конфет.

2) Все домовики получили конфеты, но конфеты в мешке еще остались. Это означает, что каждому домовику соответствует своя конфета, но все равно остались лишние конфеты. Значит, конфет больше, чем домовиков.

3) Все домовики получили конфеты, и все конфеты закончились. В таком случае каждой конфете соответствует свой домовик, а каждому домовику — своя конфета. Это означает, что конфет и домовиков поровну.