Множества → .01 Соответствия, сравнения, количества

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На первом шаге в группе разместим логарифмы нечетных чисел, а в группе — четных:

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

Перенесем число из группы в группу а число наоборот — из в Поскольку разность уменьшилась на величину

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

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

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

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

(a) Давайте попробуем придумать контрпример. Пусть у нас есть элементы Все двухэлементные множества, которые из них могут получится выглядят так: и Как можно по другому сформулировать условие задачи? Можно сказать, что у нас нет трёх двухэлементных множеств, которые не пересекаются между собой. Тогда для наших множеств условие выполняется, так как тут всего различных элемента, а в противном случае их должно быть минимум Пусть мы смогли прибить это множество. Не умаляя общности, пусть множества прибили элементами и Но тогда существует множество которое оказалось не прибито. Значит, не всегда можно прибить такое семейство двумя гвоздями.

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

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

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

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

Итак, каждый элемент присутствует не более, чем в множествах. Предположим, множеств всего Тогда рассмотрим всевозможные пары вида “множество — его элемент”. С одной стороны, таких пар (у каждого множества числа), а с другой — не более, чем (если считать по числам). Таким образом,

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

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

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

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

Пусть и — префикс последнего вхождения слова Во-первых, периодична с периодом Во-вторых, является префиксом слова но тогда она так же периодична с периодом Докажем, что тогда она периодична с периодом

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

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

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

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

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

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

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

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

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

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

и добавив к нему получим однозначно представление

Значит, количества представлений чисел и совпадают.

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

получаем, что — противоречие.