Олимпиадные задачи по теме «Теория множеств» для 11 класса - сложность 1-3 с решениями
Теория множеств
НазадПосле обеда на <i>прозрачной</i> квадратной скатерти остались тёмные пятна общей площади <i>S</i>. Оказалось, что если сложить скатерть пополам вдоль любой из двух линий, соединяющих середины противоположных её сторон, или же вдоль одной из двух её диагоналей, то общая видимая площадь пятен будет равна <i>S</i><sub>1</sub>. Если же сложить скатерть пополам вдоль другой её диагонали, то общая видимая площадь пятен останется равна <i>S</i>. Какое наименьшее значение может принимать величина <i>S</i><sub>1</sub> : <i>S</i>?
На собрание пришло <i>n</i> человек (<i>n</i> > 1). Оказалось, что у каждых двух из них среди собравшихся есть ровно двое общих знакомых.
а) Докажите, что каждый из них знаком с одинаковым числом людей на этом собрании.
б) Покажите, что <i>n</i> может быть больше 4.
В Академии Наук 999 академиков. Каждая научная тема интересует ровно троих академиков, и у каждых двух академиков есть ровно одна тема, интересная им обоим. Докажите, что можно выбрать 250 тем из их общей области научных интересов так, чтобы каждый академик интересовался не более чем одной из них.
При каком наименьшем $n$ для любого набора $A$ из $2007$ множеств найдется такой набор $B$ из $n$ множеств, что каждое множество набора $A$ является пересечением двух различных множеств набора $B$?
Дано 101-элементное подмножество <i>A</i> множества <i>S</i> = {1, 2, ..., 1000000}.
Докажите, что для некоторых <i>t</i><sub>1</sub>, ..., <i>t</i><sub>100</sub> из <i>S</i> множества <i>A<sub>j</sub></i> = {<i>x + t<sub>j</sub></i> | <i>x</i> ∈ <i>A; j</i> = 1, ..., 100} попарно не пересекаются.
В пространстве даны<i> n </i>точек общего положения (никакие три не лежат на одной прямой, никакие четыре не лежат в одной плоскости). Через каждые три из них проведена плоскость. Докажите, что какие бы<i> n-</i>3точки в пространстве ни взять, найдется плоскость из проведенных, не содержащая ни одной из этих<i> n-</i>3точек.
В классе каждый болтун дружит хотя бы с одним молчуном. При этом болтун молчит, если в кабинете находится нечетное число его друзей – молчунов. Докажите, что учитель может пригласить на факультатив не менее половины класса так, чтобы все болтуны молчали.
Члены Государственной Думы образовали фракции так, что для любых двух фракций<i> A </i>и<i> B </i>(не обязательно различных)<i> <img src="/storage/problem-media/109909/problem_109909_img_2.gif"> </i>– тоже фракция (через<i> <img src="/storage/problem-media/109909/problem_109909_img_3.gif"> </i>обозначается множество всех членов Думы, не входящих в<i> C </i>). Докажите, что для любых двух фракций<i> A </i>и<i> B </i><i> A<img src="/storage/problem-media/109909/problem_109909_img_4.gif"> B </i>– также фракция.
Числовое множество<i> M </i>, содержащее 2003 различных положительных числа, таково, что для любых трех различных элементов<i> a,b,c </i>из<i> M </i>число<i> a</i>2<i>+bc </i>рационально. Докажите, что можно выбрать такое натуральное<i> n </i>, что для любого<i> a </i>из<i> M </i>число<i> a<img src="/storage/problem-media/109780/problem_109780_img_2.gif"> </i>рационально.
Часть подмножеств некоторого конечного множества выделена. Каждое выделенное подмножество состоит в точности из2<i>k </i>элементов (<i> k </i>– фиксированное натуральное число). Известно, что в каждом подмножестве, состоящем не более чем из(<i>k+</i>1)<i><sup>2</sup> </i>элементов, либо не содержится ни одного выделенного подмножества, либо все в нем содержащиеся выделенные подмножества имеют общий элемент. Докажите, что все выделенные подмножества имеют общий элемент.
Фигура Ф представляет собой пересечение <i>n</i> кругов (<i>n</i> ≥ 2, радиусы не обязательно одинаковы). Какое максимальное число криволинейных "сторон" может иметь фигура Ф? (Криволинейная сторона – это участок границы Ф, принадлежащий одной из окружностей и ограниченный точками пересечения с другими окружностями.)
На прямоугольном экране размером <i>m</i>×<i>n</i>, разбитом на единичные клетки, светятся более (<i>m</i> – 1)(<i>n</i> – 1) клеток. Если в каком-либо квадрате 2×2 не светятся три клетки, то через некоторое время погаснет и четвёртая. Докажите, что тем не менее на экране всегда будет светиться хотя бы одна клетка.
Дано натуральное число <i>N</i>. С ним производится следующая операция: каждая цифра этого числа заносится на отдельную карточку (при этом разрешается добавлять или выбрасывать любое число карточек, на которых написана цифра 0), и затем эти карточки разбивают на две кучи. В каждой из них карточки располагаются в произвольном порядке, и полученные два числа складываются. С полученным числом <i>N</i><sub>1</sub> проделывается такая же операция, и т.д. Докажите, что за 15 шагов из <i>N</i> можно получить однозначное число.
Имеется бесконечное количество карточек, на каждой из которых написано какое-то натуральное число. Известно, что для любого натурального числа <i>n</i> существуют ровно <i>n</i> карточек, на которых написаны делители этого числа. Доказать, что каждое натуральное число встречается хотя бы на одной карточке.
Улитка должна проползти вдоль линий клетчатой бумаги путь длины 2<i>n</i>, начав и кончив свой путь в данном узле.
Доказать, что число различных её маршрутов равно <img align="absmiddle" src="/storage/problem-media/78237/problem_78237_img_2.gif">
Два подмножества множества натуральных чисел называют конгруэнтными, если одно получается из другого сдвигом на целое число.<span class="prim">(Например, множества чётных и нечётных чисел конгруэнтны.)</span>Можно ли разбить множество натуральных чисел на бесконечное число<nobr>(не пересекающих</nobr>друг друга) бесконечных конгруэнтных подмножеств?
24 студента решали 25 задач. У преподавателя есть таблица размером 24×25, в которой записано, кто какие задачи решил. Оказалось, что каждую задачу решил хотя бы один студент. Докажите, что
а) можно отметить некоторые задачи "галочкой" так, что каждый из студентов решил чётное число (в частности, может быть, нуль) отмеченных задач;
б) можно отметить некоторые из задач знаком "+", а некоторые из остальных – знаком "–" и приписать каждой задаче некоторое натуральное число баллов так, чтобы каждый студент набрал поровну баллов за задачи, отмеченные знаками "+" и "–".
Пусть <i>k</i> и <i>n</i> – натуральные числа, <i>k ≤ n</i>. Расставьте первые <i>n</i>² натуральных чисел в таблицу <i>n</i>×<i>n</i> так, чтобы в каждой строке числа шли в порядке возрастания и при этом сумма чисел в <i>k</i>-м столбце была а) наименьшей; б) наибольшей.
В множестве, состоящем из <i>n</i> элементов, выбрано 2<sup><i>n</i>–1</sup> подмножеств, каждые три из которых имеют общий элемент.
Докажите, что все эти подмножества имеют общий элемент.
Некоторые из чисел 1, 2, 3, ..., $n$ покрашены в красный цвет так, что выполняется условие: если для красных чисел $a, b, c$ (не обязательно различных) $a(b - c)$ делится на $n$, то $b = c$.
Докажите, что красных чисел не больше чем φ($n$).
Неправдоподобная легенда гласит, что однажды Стирлинг размышлял над числами Стирлинга второго рода и в задумчивости бросал на стол 10 правильных игральных костей. После очередного броска он вдруг заметил, что в выпавшей комбинации очков присутствуют все числа от 1 до 6. Тут же Стирлинг задумался, а какова же вероятность такого события? Какова вероятность, что при бросании 10 костей каждое число очков от 1 до 6 выпадет хотя бы на одной кости?
В стране есть <i>n</i> > 1 городов, некоторые пары городов соединены двусторонними беспосадочными авиарейсами. При этом между каждыми двумя городами существует единственный авиамаршрут (возможно, с пересадками). Мэр каждого города <i>X</i> подсчитал количество таких нумераций всех городов числами от 1 до <i>n</i>, что на любом авиамаршруте, начинающемся в <i>X</i>, номера городов идут в порядке возрастания. Все мэры, кроме одного, заметили, что их результаты подсчётов делятся на 2016. Докажите, что и у оставшегося мэра результат также делится на 2016.
Назовём непустое (конечное или бесконечное) множество <i>A</i>, состоящее из действительных чисел, <i> полным</i>, если для любых действительных <i>a</i> и <i>b</i> (не обязательно различных и не обязательно лежащих в <i>A</i>), при которых <i>a + b</i> лежит в <i>A</i>, число <i>ab</i> также лежит в <i>A</i>. Найдите все полные множества действительных чисел.
В классе учится 23 человека. В течение года каждый ученик этого класса один раз праздновал день рождения, на который пришли некоторые (хотя бы один, но не все) его одноклассники. Могло ли оказаться, что каждые два ученика этого класса встретились на таких празднованиях одинаковое число раз? (Считается, что на каждом празднике встретились каждые два гостя, а также именинник встретился со всеми гостями.)
Пусть <i>A</i> – угловая клетка шахматной доски, <i>B</i> – соседняя с ней по диагонали клетка. Докажите, что число способов обойти всю доску <i>хромой ладьей</i> (ходит на одну клетку по вертикали или горизонтали), начиная с клетки <i>A</i>, больше, чем число способов обойти всю доску хромой ладьей, начиная с клетки <i>B</i>. (Ладья должна побывать на каждой клетке ровно один раз.)