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

Всего способов расставить знаки .

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

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

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

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

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

Таким образом, по сути — количество троек таких, что и

______________________________________________________________________________________________________________________________________________________

Мысль 1. Начнём решение с простого, но важного наблюдения: если то

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

В частности,

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

______________________________________________________________________________________________________________________________________________________

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Теперь у нас есть все, чтобы решить задачу. Ранее мы показали, что и Тогда

Используя и получаем, что последнее равно

Рассмотрим отрезок где Мы хотим выбрать из такого отрезка числа, которые делятся на Количество целых чисел на таком отрезке

причём первое число очевидно, делится на Значит, всего подходящих чисел на отрезке будет

В нашей задаче в исследуемый интервал целиком входят отрезки для Там искомых чисел

На отрезке только одно число делится на а на отрезке всего чисел, причём снова певрвое число делится, поэтому мы берём чисел. Всего число.

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

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

Домножая на знаменатели, получаем систему из трех уравнений:

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

Когда переменная будет пробегать все возможные положительные значения, эти две формулы будут описывать соответствующие значения переменных и

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

Случай 2. В этом случае мы получаем аналогичную серию равенств:

Домножая на знаменатели, получаем систему из трех уравнений:

Складывая эти равенства, получаем формулу Учитывая, что находим Тогда и первое уравнение нашей системы переписывается в виде Вновь вспоминая, что находим Остается решить несложную систему:

Решая ее, находим ответ и (мы учитываем, что

Вновь циклически переставляя найденные ответы, получаем еще три тройки:

Рассмотрим одно из выбранных множеств, назовём его Каждое из оставшихся имеет с ним как минимум один общий элемент, при этом ни один из элементов множества не может принадлежать больше чем двум другим множествам, поэтому остальных множеств не более а вместе с — не более

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

Это число должно быть целым, однако, ни ни на 3 не делятся, так как сравнима с 2 по модулю 3, откуда наше предположение не верно, то есть множеств не более

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

Наш ряд будет состоять из 33 блоков выложенных друг за другом в этом порядке. Блок выглядит как:

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

Действительно, предположим, что нашёлся идеальный набор, в котором нет особых карточек. Найдётся индекс такой, что буква этого набора встречается не правее блока (подходит хотя бы ); выберем наименьшее такое Если карточка нашего набора встречается левее то и также встречается в наборе левее то есть не правее это противоречит минимальности Значит, встречается именно в блоке то есть написана на особой карточке, что и требовалось.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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