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

Сумма в левой части описывает количество элементов в пересечениях троек множеств. Можно задаться вопросом: в какое количество пересечений троек входит каждый элемент? Посчитаем и ответим на этот вопрос!

Пусть й элемент исходного элементного множества входит в подмножеств Тогда он входит ровно в пересечений троек. Тогда

Заметим, что так как обе суммы подсчитывают двумя способами одну и ту же величину: количество пар (множество; элемент множества). Таким образом, задача свелась к доказательству неравенства

А это неравенство эквивалентно неравенству между средним арифметическим и средним кубическим!

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

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

Осталось предъявить пример хорошего набора из подмножеств в Для этого покажем индукцией по что существует хороший набор подмножеств в причём содержит элемент. В базовом случае годятся подмножества и

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

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

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

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

при остальных

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

Зафиксируем число Тогда достаточно показать, при любом достаточно большом и произвольном

то есть

Пусть значение зафиксированного таково, что

Тогда для любого имеем

что и требовалось показать.

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

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

Пусть четно. Тогда, поскольку четных и нечетных чисел среди поровну, среди сумм четныx — четное количество. Но две или больше четных сумм простыми числами быть не могут, так как число 2 можно представить в виде суммы натуральных чисел единственным способом: 1+1. Следовательно, все суммы в этом случае нечетны, то есть четным соответствуют нечетные и наоборот. Но в таком случае число искомых перестановок равно где — количество таких биекций из в что — простое число при любом Пусть нечетно. Тогда среди сумм есть четная — иначе четное число окажется суммой нечетного количества нечетных. Единственная возможность для этого — 1+1 = 2. Таким образом, Рассматривая теперь отдельно как перестановку чисел оказываемся в ситуации, уже рассмотренной в первой половине решения.

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

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

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

Пусть в множестве есть число тогда поскольку в множестве есть и

Тогда если конечно и в нём имеется максимальный элемент то в нём имеются все числа от до Притом если то что противоречит максимальности элемента Нетрудно убедиться, что при от до множества вида {1, 2, …n} являются решениями.

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

Установим взаимно-однозначное соответствие между словами Пети и Васи. Разобьём Васино слово из букв на блоки из двух букв. Заменим каждый блок на букву блок — на букву блок — на букву и блок — на букву Получится слово из букв, в котором букв и поровну (изначально их было поровну, замена блоков и убирает равное число букв и а значит, и блоков будет столько же, сколько блоков ). Итак, каждому слову Васи мы сопоставили слово Пети.

Наоборот, по каждому -буквенному слову Пети легко восстановить, из какого слова Васи оно получилось по описанному выше правилу: надо заменить буквы по тому же правилу.

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

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

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

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

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

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

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

База при очевидна.

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

— посчитали все элементы выкинутого множества.

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

Тогда по ранее проведённым рассуждениям при возврате выкинутого множества сумма из условия увеличится на

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

Получаем противоречие. Значит, нашлись комитета, имеющих более общих членов.

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

Любые две стрелки определяют «плохой» сектор между их продолжениями, попав в который, третья стрелка создает плохой момент времени. Этот сектор не превосходит

Через целое число часов положение минутной и секундной стрелок будет таким же.

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

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

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

отсюда будет следовать:

т.е. что противоречит условию задачи.

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

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

а из первой тройки:

Отсюда вытекает первое утверждение: Теперь рассмотрим тройку которая также представительна. Подставляя вместо получим представительную тройку Сравнение этих троек приводит ко второму утверждению:

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

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

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

Итак, число кружков не превосходит числа учеников в классе.

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