Формула включений-исключений

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

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

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

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

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

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

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

Нарисуем три круга Эйлера для трех множеств чисел: кратные 2, кратные 3, кратные 5. Чтобы вычислить количество чисел в объединении всех трех множеств, нужно посчитать количество чисел в каждом множестве отдельно, в их попарных пересечениях и в пересечении всех трех.

Чисел, кратных 2 ровно .

Чисел, кратных 3 ровно целая часть от , то есть 333.

Чисел, кратных 3 ровно .

Чисел, кратных 2 и 3 ровно целая часть от , то есть 166.

Чисел, кратных 2 и 5 ровно .

Чисел, кратных 3 и 5 ровно целая часть от , то есть 66.

Чисел, кратных 2, 3 и 5 ровно целая часть от , то есть 33.

Тогда ответ: .

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

Так как чисел от 1 до 5 нет в последовательности, то изначально на месте стоит число

Среди первых членов последовательности полных квадрата, так как уже больше 2027, а ещё меньше и при этом из 45 первых квадратов не учитываются и

Среди первых членов последовательности полных кубов, так как уже больше 2027, а ещё меньше и при этом из 12 первых кубов не учитывается

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

Итак, после удалений на месте будет стоять число

Способ 1

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

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

Способ 2

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

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

Способ 3

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

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

Если то на делится каждое -ое число в ряду (*) и или Следовательно,

Итого, в ряду (*) не менее чисел, кратных и Из этих чисел не более трёх являются простыми — это сами числа и если они там есть. Поэтому в ряду (*) не более простых.

, то есть нас интересуют числа, деляющиеся на или Найдём сначала количество таких чисел. Для этого воспользуемся принципом включений и исключений. Чётных чисел от до ровно , кратных трём — , кратных пяти — . Однако, если просто сложить числа 1500,1000 и 600 , мы посчитаем некоторые числа 2 раза, а именно, числа, делящиеся на и , поэтому из полученной суммы надо вычесть и . Однако, всё ещё неправильный ответ, Поскольку в этом выражение числа, имеющие все три простых множителя, сначала считаются три раза, а потом их количество вычитается опять же три раза, поэтому надо снова добавить эти числа. Количество таких чисел , значит, количество чисел, имеющих с общие делители и не превосходящих его, это

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

Замечание.

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

Пусть человек изучают английский язык, – немецкий язык, а – оба языка. Тогда Известно, что и

Следовательно,

Тогда наибольшее а достигается при