Множества

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

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

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

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

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

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

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

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

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

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

Чтобы найти ответ надо найти количество элементов в объединении множеств. Используя формулу включений-исключений, получаем, что

где — означает количество элементов во множестве — искомое число

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

Тогда посчитаем

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

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

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

Если разложим карточки на две кучи: в одной куче карточки, на лицевой стороне которых выписаны множества с четным числом элементов, а в другой — с нечетным. Тогда в каждой из куч величина «число элементов множества на лицевой стороне карточки» принимает лишь различных значений, поэтому ни в одной из куч на лицевых сторонах карточек не найдётся согласованная с последовательностью () возрастающая цепочка из множества. И даже более цинично: расслоим карточки на 2n слов по числу элементов, после чего слоев целиком помещаем в одну кучу, а другие слоев в другую. Ни одна из куч не содержит цепь длины

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Зафиксируем натуральное число Приведем стратегию игры за первого игрока. Проведем итерации следующего алгоритма:

Найдем натуральное число такое, что в каждом из множеств клеток и нет отмеченных.

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

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

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

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

После последней итерации алгоритма в особенном квадрате не более

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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