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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы воплотить этот план в жизнь, нам осталось доказать следующее утверждение.

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

Доказательство. Когда нам не важен порядок элементов, мы будем в этом доказательстве наряду со словом “последовательность” использовать слово “множество”.

Индукция по Базу при нетрудно получить хотя бы перебором.

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

Дана последовательность И пусть — несколько её подпоследовательностей, причём и подпоследовательности содержат от до элементов. Тогда существует перенумерация, в которой ни одна из подпоследовательностей не является интервалом.

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

К оставшимся элементам и множествам можно применить предположение индукции, так как все полученные множества содержат от до элементов. Посмотрим, в какое место полученной последовательности можно вставить так, чтобы все требуемые условия выполнились. Если было выброшено произвольное множество то достаточно вставить так, чтобы элементы не стояли подряд — очевидно, это можно сделать. Иначе, если есть пара то нельзя вставить в два места (соседних со вторым элементом пары), а если есть множество то также появляются два “запрещенных” места — края последовательности. Поскольку можно было вставить в различных мест, то хотя бы одно осталось незапрещенным. Вставив туда получаем требуемую последовательность.

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

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

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

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

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

Итак, можно представить в виде суммы не более чем элементов из Пусть — последовательность, состоящая из этих не более чем Положим Ясно, что сумма элементов кратна и Если бы оказалось, что то мы бы легко составили подпоследовательность из элементов, кратных добавив к несколько элементов, кратных Следовательно, Применим снова утверждение, доказанное выше, и построим подпоследовательность не более чем из элементов, сумма которой кратна Положим Опять имеем, что сумма элементов равна нулю и Продолжая дальше в том же духе, мы всё-таки сумеем построить последовательность длины c суммой, кратной

Если прибавить к каждому элементу одно и то же число, остатки сумм из элементов при делении на не поменяются, поэтому можно считать, что наибольшую кратность имеет Обозначим через подпоследовательность состоящую из всех нулей; пусть — количество элементов в Ясно, что Среди всех подпоследовательностей длины не более выберем самую длинную подпоследовательность с суммой, кратной обозначим ее длину через (возможно, и ).

Тогда так как в противном случае, дополнив нескольким нулями, мы получили бы подпоследовательность из элементов с суммой, кратной Итак, в последовательности не меньше элементов. Возьмем любые из них, пусть они образуют последовательность Пусть — наибольшая кратность элемента в Тогда по определению числа Разобьем каноническим образом в объединение непересекающихся множеств (не последовательностей!) и положим Заметим теперь, что не принадлежит и что при никакие элементов не дают в сумме Действительно, так как то если бы какие-то элементов из давали бы в сумме мы могли бы объединить эти элементы с и получили бы более длинную подпоследовательность с суммой, кратной что противоречит определению Таким образом, мы проверили, что к набору можно последовательно применять теорему Кемпермана-Шерка (подробнее про эту теорему см. ниже), что даёт нам неравенство

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

Теорема Кемпермана — Шерка. Пусть  — натуральное число, и  — два подмножества содержащие и пусть уравнение где имеет относительно и единственное решение Тогда

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

Ясно, что не лежит в поэтому по-прежнему лежит в Очевидно, лежит в

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

Наконец, отметим, что

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

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

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

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

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

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

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

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

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

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

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

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

Следовательно, (множество вычетов по модулю ), откуда и следует требуемое утверждение.