Тема Множества

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела множества

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#80769

Дан клетчатый прямоугольник $100×400$ . Сколькими способами можно закрасить 8 клеток этого прямоугольника так, чтобы закрашенное множество обладало хотя бы одной из следующих симметрий: относительно центра прямоугольника, относительно любой из двух "средних линий"прямоугольника ("средней линией"прямоутольника назовём отрезок, соединяющий середины двух его противоположных сторон). Ответ дайте в виде выражения, содержащего не более трёх членов (в них могут входить факториалы, биномиальные коэффициенты).

Источники: Физтех - 2024, 11.5 (см. olymp-online.mipt.ru)

Подсказки к задаче

Подсказка 1

Давайте начнём распутывать клубок симметрий с того, что обозначим за A₁ множество восьмёрок симметричных относительно одной горизонтальной средний линии, за A₂ - вертикальной, за B - относительно центра прямоугольника. Давайте подумаем, сколько нам нужно зафиксировать точек для каждой из симметрий и где, чтобы однозначно восстановить всю восьмёрку?

Подсказка 2

Верно, для A₁ нужны 4 точки не выше (не ниже), чем горизонтальная средняя линия, для A₂ - 4 точки не правее (не левее), чем вертикальная средняя линия, для B - 4 точки в любой одной из указанных ранее областей. Теперь стоит задуматься о том, пересекаются ли данные множества или какая-то комбинация симметрий даёт другую симметрию?

Подсказка 3

Верно, если восьмёрка лежит в любых двух множества A₁, A₂, B, то она лежит во всех трёх, отсюда, вспоминая формулу включений-исключений, мы понимаем, что ответ уже очень близко, осталось только его расписать.

Показать ответ и решение

Назовем восьмеркой набор из $8$ клеток. Пусть $A 1$ — множество восьмерок, симметричных относительной $l 1$ , $A 2$ — относительно $l 2$ , $B$ — относительно центра прямоугольника. $l1$ и $l2$ это средние линии прямоугольника.

Если выбрать какие-то $4$ точки в верхней половине прямоугольника, то остальные точки легко находятся в силу одной из рассматриваемой симметрий относительно $l1, l2$ и центра прямоугольника. Тогда количество элементов во множествах $A1, A2, B$ будет одинаковым. Тогда количество элементов в $A1$ будет равно количеству способов выбрать $4$ очки в одной половине фигуры относительно $l1.$ Остальные $4$ точки будут располагаются в другой половине. Тогда количество способов равняется $4 C100⋅200.$

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

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

S = |A1∪ A2∪ B|= |A1|+|A2|+|B|− 2|A1∩ A2∩B |,

где $|M |$ — означает количество элементов во множестве $M,$ $S$ — искомое число

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

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

S = |A1 ∪A2 ∪B|= |A1|+ |A2|+ |B|− 2|A1 ∩A2∩ B|=

= 3C420000− 2C210000

Ответ:

$3C4 − 2C2 20000 10000$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#34162

Сколько чисел от 1 до 1000 делятся хотя бы на одно из чисел 2, 3, 5?

Показать ответ и решение

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

Чисел, кратных 2 ровно $1000∕2= 500$ .

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

Чисел, кратных 3 ровно $1000∕5= 200$ .

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

Чисел, кратных 2 и 5 ровно $1000∕10= 100$ .

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

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

Тогда ответ: $500+ 333 +200− 166− 100− 66+ 33= 734$ .

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 3#39370

Среди $40$ друзей Кати $23$ друга любят малину, $22$ — клубнику, а $21$ — землянику. При этом и малину, и клубнику любит $12$ друзей, и малину, и землянику — $9$ друзей, а клубнику и землянику — $10$ друзей. Сколько среди друзей Кати тех, кто любит все три ягоды, если известно, что каждый хоть какую-то из этих ягод любит?

Показать ответ и решение

Если сложить $23+ 22+21$ , получится, что каждого однолюба мы считаем один раз, каждого двулюба — два раза, а каждого трилюба — три раза. Если сложить $12+9 +10$ , то каждого двулюба мы считаем один раз, а каждого трилюба — три раза. Тогда после вычитания из первой суммы второй суммы, и однолюбы, и двулюбы посчитаны по разу, а трилюбы не посчитаны вообще. Значит, число $23+ 22 +21− 12− 9 − 10= 35$ отличает от $40$ только количество трилюбов. Тогда их $5$ .

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 4#69856

Какое число окажется на 2022-м месте в бесконечной последовательности $6,7,8,9,10,...$ , если в ней удалить все квадраты и кубы каких-либо натуральных чисел (то есть удалить числа $3 2 2 ) 8= 2 ,9 =3 ,16= 4,...$ ?

Источники: ПВГ-2022, 11.1 (см. pvg.mk.ru)

Подсказки к задаче

Подсказка 1

Наверное, чтобы найти число, которое стоит на 2022 месте, надо посчитать количество полных квадратов и кубов среди чисел от 6 до 2027. Как это можно сделать?

Подсказка 2

Для начала найдем количество квадратов. Можно заметить, что 2116=46²>2027>45²=2025. Поэтому количество квадратов равно 43 (1² и 2² не лежат в нашей последовательности). А сколько кубов находится в этой последовательности...

Подсказка 3

Их 11, ведь 2197=13³>2027>12³=1728 (1³ мы не считаем). Кажется, что некоторые числа мы посчитали дважды... Какие же?

Подсказка 4

Если n=t⁶, то n мы посчитали дважды. Таких n всего 2: 64 и 729. Как завершить решение?

Подсказка 5

Так как мы вычеркнули 43+11-2=52 числа, то надо прибавить к 2027 52. Осталось только проверить, не было ли среди чисел от 2027 до 2079 точных квадратов или кубов и наслаждаться победой!

Показать ответ и решение

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

Среди первых $2022$ членов последовательности $43$ полных квадрата, так как $2 46 = 2116$ уже больше 2027, а $2 45 = 2025$ ещё меньше и при этом из 45 первых квадратов не учитываются $2 1$ и $2 2 .$

Среди первых $2022$ членов последовательности $11$ полных кубов, так как $3 13 =2197$ уже больше 2027, а $3 12 = 1728$ ещё меньше и при этом из 12 первых кубов не учитывается $3 1 .$

При удалении квадратов и кубов числа, являющиеся $6$ степенью натуральных чисел, были посчитаны дважды. Их среди первых $2022$ членов последовательности $2$ , а именно $6 6 2 и 3$ , так как $6 4096= 4$ уже больше, чем 2027, а $6 3 =729$ ещё меньше, и при этом $6 1$ учитывать не надо.

Итак, после удалений на $2022$ месте будет стоять число $2027+ 43+ 11 − 2= 2079.$

Ответ: 2079

Ошибка.
Попробуйте повторить позже

Задача 5#69819

В ряд выписано $2021$ простое натуральное число. Каждое, кроме крайних, отличается от одного из своих соседей на $12,$ а от другого — на $6.$ Докажите, что среди этих чисел есть равные.

Источники: СпбОШ - 2021, задача 10.2 (см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Если мы хотим сказать, что все числа различные, то такая последовательность достаточно быстро, линейно растет. И при этом, почти все идут подряд, если смотреть на целую часть при делении на 6. То есть, число может «прыгать» через 1(после того как нацело поделили всю нашу последовательность на 6), но не больше чем на 1. Вот так «на пальцах», не строго, мы поняли, что было бы очень удачно, если бы мы смогли найти два каких-то соседних числа, которые отличаются на хотя бы 18. А это можно сделать, если мы(допустим) сможем разделить нашу последовательность на что-то большее ,чем некоторое число , и на что-то меньшее , чем некоторое число. И наименьшее и наибольшее из соответствующих групп отличались хотя бы на 18. То есть, иными словами, мы хотим сказать, что какие - то два подряд идущих числа, отличающиеся на 6, не могут быть в последовательности. Попробуйте придумать, как к такой конструкции прийти.

Подсказка 2

Одна из таких конструкций - остатки. По китайской теореме об остатках найдется такое k, что p + 6k делится на 5,а p + 6(k+1) на 7, при этом p - наименьшее простое число, большее 7(чтобы существовало число перед ним, которое входит в последовательность), входящее в последовательность. При этом 0 < k <= 5*7(по КТО найдется такое k). Теперь подумайте, откуда здесь возникает противоречие.

Подсказка 3

А возникает оно из - за того, что оба этих числа не простые, при этом они идут через одно. То есть, как раз мы получили конструкцию, в которой все разделилось на две кучи, в одной из которых числа которые хотя бы p+6(k+2), а в другой p+6(k-1). То есть разность хотя бы 18. Что теперь это значит? Какие теперь числа точно не могут быть в последовательности? А сколько теперь может быть чисел максимум в последовательности?

Подсказка 4

Верно, числа больше или равные p + 6(k+2), поскольку множество «меньших» непустое. Значит, чисел в наборе останется не больше чем 36(самое p и всевозможные 0 < k <= 5*7) и 2,3,5,7 - то есть не более 40 чисел. Но у нас 2021 число. Противоречие.

Показать доказательство

Способ 1

Предположим, что все числа в ряду различны. Выберем в нашем ряду число $p,$ у которого с каждой стороны не меньше пяти соседей, причём среди них нет числа $5.$ Такое $p$ найдётся, так как число $2021$ достаточно большое, а число $5$ в нашем ряду встречается не более одного раза. Если $p≡ ±1 (mod 5),$ рассмотрим соседа числа $p,$ отличающегося от него на $6.$ А если $p≡ ±2 (mod 5),$ рассмотрим его соседа, отличающегося на $12.$ Не умаляя общности, будем считать, что этот сосед находится справа от $p.$ На приведённой ниже схеме выберем среди первых четырёх чисел то, которое равно остатку числа $p$ при делении на $5.$ Число над стрелкой показывает, на сколько должен отличаться его правый сосед, а число после стрелки — какой остаток при делении на $5$ этот сосед будет иметь. Все числа над стрелками однозначно определяются условиями, что разности $± 6$ и $±12$ чередуются и в ряду нет остатка $0 :$

+6 +12 − 6 −12 +6 +12 −6 1−−→ 2 −−−→ 4−−→ 3 −−−→ 1−−→ 2 −−−→ 4−−→ 3

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

Способ 2

Пусть $p$ — наименьшее простое число в этом ряду большее $7.$ По китайской теореме об остатках существует такое число $k$ ( $0< k≤ 35$ ), что

p+ 6k≡ 0 (mod 5)

p+ 6(k+ 1)≡ 0 (mod 7).

Тогда числа $p+ 6k$ и $p+ 6(k+ 1)$ не простые, поэтому в нашем ряду они не встречаются. Но тогда в нашем ряду не может быть и чисел, больших $p+ 6(k+1),$ так как иначе нашлось бы два соседних числа, одно из которых не превосходит $p+ 6(k− 1),$ а второе не меньше числа $p+ 6(k +2),$ что невозможно. Следовательно, в ряду может встретиться не более $40$ различных простых чисел: $2,3,5,7$ и $p,p+ 6,...,p+ 6⋅35.$ Но в ряду $2021$ число, значит, среди чисел есть равные.

Способ 3

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

p,p+6,p+ 12,...,p+ 18⋅1010(∗)

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

N =d5+ d7+ d11− d35 − d55− d77+ d385.

Если $(6,n)= 1,$ то на $n$ делится каждое $n$ -ое число в ряду (*) и $[3031] dn = n$ или $[3031] dn = n + 1.$ Следовательно,

[ ] [ ] [ ] [ ] [ ] [ ] [ ] N ≥ 3031- + 3031 + 3031-− 3031- − 1− 3031 − 1 − 3031 − 1+ 3031-= 606+433+ 275 − 87− 56− 40+ 7= 1129. 5 7 11 35 55 77 385

Итого, в ряду (*) не менее $1129$ чисел, кратных $5,7$ и $11.$ Из этих $1129$ чисел не более трёх являются простыми — это сами числа $5,7$ и $11,$ если они там есть. Поэтому в ряду (*) не более $3031− 1129+ 3= 1905$ простых.

Ошибка.
Попробуйте повторить позже

Задача 6#99641

Найдите сумму натуральных чисел от $1$ до $3000$ включительно, имеющих с числом $3000$ общие делители, большие $1.$

Источники: ИТМО - 2021, 11.2 (см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1

В условии задачи сказано, что надо просуммировать числа от 1 до 3000, которые не взаимнопросты с 3000. Какие нам тогда числа не подходят, если 3000 = 2³ * 3¹ * 5³?

Подсказка 2

Это значит, что нам подходят числа, которые делятся на 2, или на 3, или 5. Давайте поймём, что если нам подходит число x, то подходит и число 3000-x. При том, все числа, которые подходят под условие выше, разбиваются на пары. Или почти все? А когда тогда посчитать их сумму?

Подсказка 3

Числа 3000 и 1500 не составляют те самые пары, а вот все остальные числа, подходящие под условия все таки разбиваются на пары. Это значит, что нам теперь достаточно найти количество таких чисел и домножить их на 3000 (учтя особую роль в этой сумме исключений выше). Как найти количество таких чисел? Мы ведь не можем просто сложить количество чисел кратных 2, 3 и 5 и получить ответ. У нас есть числа которые кратны сразу двум каким-то, а также числа, кратные сразу всем. Подумайте, как тогда считать их количество?

Подсказка 4

Мы можем посчитать с помощью формулы включений и исключений количество таких чисел, а именно сначала количество просто кратных какому-то, минус сумма кратных сразу двум и плюс сумма кратных всем трём. Получится 2200. Чему тогда равна наша сумма?

Показать ответ и решение

$3000= 23 ⋅3 ⋅53$ , то есть нас интересуют числа, деляющиеся на $2,3$ или $5.$ Найдём сначала количество таких чисел. Для этого воспользуемся принципом включений и исключений. Чётных чисел от $1$ до $3000$ ровно $3000 2 = 1500$ , кратных трём — $3000 3 =1000$ , кратных пяти — $3000 5 =600$ . Однако, если просто сложить числа 1500,1000 и 600 , мы посчитаем некоторые числа 2 раза, а именно, числа, делящиеся на $2⋅3= 6,2⋅5= 10$ и $3⋅5= 15$ , поэтому из полученной суммы надо вычесть $3000 6 =$ $3000 500,10 = 300$ и $3000 15 = 200$ . Однако, $1500+1000+ 600− 500− 300− 200=2100$ всё ещё неправильный ответ, Поскольку в этом выражение числа, имеющие все три простых множителя, сначала считаются три раза, а потом их количество вычитается опять же три раза, поэтому надо снова добавить эти числа. Количество таких чисел $3000 − 2⋅3⋅5 =100$ , значит, количество чисел, имеющих с $3000$ общие делители и не превосходящих его, это $2200.$

Заметим теперь, что если какое-то число $x$ имеет с числом $N$ общие делители, то число $N − x$ тоже имеет с $N$ те же самые общие делители. Значит, все интересующие нас числа, кроме чисел $1500$ и $3000,$ разбиваются на пары с суммой $3000$ (числу 3000 в пару пришлось бы сопоставить $0,$ а числу $1500−$ само себя). Таких пар получаается $1099,$ поэтому итоговый ответ $1099⋅3000+ 3000+ 1500 =$ $1100⋅3000+ 1500 =3301500.$

Замечание.

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

N(N +-1)−-N ⋅φ(N). 2

Ответ:

$3301500$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#74601

Каждый из 2017 учащихся средней школы изучает английский или немецкий язык. Английский язык изучают от $70%$ до $85%$ от общего числа учащихся, а оба языка изучают от $5%$ до $8%$ . Какое наибольшее число школьников может изучать немецкий язык?

Подсказки к задаче

Подсказка 1

Что надо сделать с количеством учеников, которые изучают английский язык или оба языка, чтобы максимизировать число тех, кто изучает немецкий?

Подсказка 2

Для ответа на предыдущий вопрос, давайте составим уравнение на количество учеников! 2017 = A + C - B(это можно понять с помощью кругов Эйлера), где A - те, кто изучает только английский, C - количество тех, кто изучает только немецкий, B - оба языка! Отсюда видно, что C = 2017 - A + B, то есть надо минимизировать число тех, кто изучает английский и максимизировать число тех, кто изучает обо языка!

Подсказка 3

Английский изучает не менее 2017*0.7 = 1411.9, а оба языка изучают не более 2017*0.08 = 161.31, остаётся в правильную сторону округлить числа, и задача решена!

Показать ответ и решение

Пусть $A$ человек изучают английский язык, $B$ – немецкий язык, а $C$ – оба языка. Тогда $B = 2017 − A +C.$ Известно, что $A ≥ 2017⋅0,7= 1411,9$ и $C ≤ 0,08⋅2017= 161,31.$