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

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

Доказательство. Обозначим через множество исходных чисел, через — множество без а через — наибольший общий делитель чисел из Наибольший общий делитель любых чисел и равен наибольшему общему делителю всех чисел то есть следовательно, попарно взаимно просты.

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

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

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

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

Следовательно, у каких-то четырёх пар суммы совпадают. Пары, для которых совпадают суммы, не могут пересекаться: если то и пары совпадают.

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

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

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

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

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

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

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

Проинтерпретируем задачу следующим образом: дано несколько синих и красных множеств, в каждом ровно элементов. Известно, что любое синее и любое красное множество имеют непустое пересечение. Надо доказать, что все элементы множеств можно покрасить в три цвета (назовём эти цвета и ) так, чтобы в каждом множестве были элементы всех трёх цветов.

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

Случай Остались и синие, и красные множества. Выберем такие два множества — синее и красное — пересечение которых содержит больше всего элементов; пусть элементов. Отметим, что

) Если то раскрасим в цвет два элемента из и в цвет все остальные элементы не из в цвет Эта раскраска подходит. Действительно, любое множество пересекается или с или с то есть его элементы не могут быть только -го цвета. Но и только -го или -го цвета они быть не могут, так как -го цвета ровно элементов, а -го цвета – элемента.

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

Случай Осталось только одно множество. Как угодно покрасим его элементы в два цвета.

Рассмотрим диаграмму Юнга для каждого разбиения на сумму. Дополним её до прямоугольника (поскольку слагаемых и каждое из них то мы так можем сделать). Заметим, что дополнение можно рассматривать как диаграмму Юнга для разбиения числа на слагаемые. Причем получится, что слагаемых тоже не более, чем и каждое из них не будет превосходить В итоге, каждому разбиению на слагаемые числа мы сопоставили разбиение числа

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

Пусть имеется разложение

где — различные нечетные числа, причем повторяется в разложении раз. Рассмотрим разложение чисел по различным степеням двойки: Тогда легко видеть, что число разлагается в сумму

причем все слагаемые в этой сумме различны.

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

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

Если цифра в разряде десятков нечётна (таких случаев 5), то каждому подходящему числу можно сопоставить неподходящее число на единицу больше. В каждом таком десятке будет 5 пар, поэтому сумма неподходящих чисел в таких десятках на больше.

Если цифра в разряде десятков чётна (таких случаев 4, потому что 0 не может быть числом десятков двузначного числа), то каждому подходящему числу можно сопоставить неподходящее число на единицу меньше. В каждом таком десятке будет 5 пар, поэтому сумма неподходящих чисел в таких десятках на меньше.

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

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

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

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

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

Второй случай: не существует множеств, содержащих элемент и второй не из и не существует множеств, содержащих элементы и не содержащие и помимо и и Тогда искомые подсемейства можно предъявить так: в первом все множества, содержащие во втором множества и и и в третьем все оставшиеся.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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