Олимпиадные задачи по теме «Теория множеств» для 9 класса - сложность 3-4 с решениями

Можно ли множество всех натуральных чисел разбить на непересекающиеся конечные подмножества  <i>A</i>₁, <i>A</i>₂, <i>A</i>₃, ...  так, чтобы при любом натуральном <i>k</i> сумма всех чисел, входящих в подмножество <i>A_k</i>, равнялась  <i>k</i> + 2013?

Можно ли раскрасить натуральные числа в 2009 цветов так, чтобы каждый цвет встречался бесконечное число раз, и не нашлось тройки чисел, покрашенных в три различных цвета, таких, что произведение двух из них равно третьему?

При каком наименьшем $n$ для любого набора $A$ из $2007$ множеств найдется такой набор $B$ из $n$ множеств, что каждое множество набора $A$ является пересечением двух различных множеств набора $B$?

Дано 101-элементное подмножество <i>A</i> множества  <i>S</i> = {1, 2, ..., 1000000}.

Докажите, что для некоторых  <i>t</i>₁, ..., <i>t</i>₁₀₀  из <i>S</i> множества   <i>A_j</i> = {<i>x + t_j</i> | <i>x</i> ∈ <i>A;  j</i> = 1, ..., 100}   попарно не пересекаются.

Набор из 2003 положительных чисел таков, что для любых двух входящих в него чисел<i> a </i>и<i> b </i>(<i> a>b </i>) хотя бы одно из чисел<i> a+b </i>или<i> a-b </i>тоже входит в набор. Докажите, что если данные числа упорядочить по возрастанию, то разности между соседними числами окажутся одинаковыми.

Каждый голосующий на выборах вносит в избирательный бюллетень фамилии<i> n </i>кандидатов. На избирательном участке находится<i> n+</i>1урна. После выборов выяснилось, что в каждой урне лежит по крайней мере один бюллетень и при всяком выборе(<i>n+</i>1)-го бюллетеня по одному из каждой урны найдется кандидат, фамилия которого встречается в каждом из выбранных бюллетеней. Докажите, что по крайней мере в одной урне все бюллетени содержат фамилию одного и того же кандидата.

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

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

Пусть<i> M={x₁, .., x</i>30<i>} </i>– множество, состоящее из 30 различных положительных чисел;<i> A_n </i>(1<i><img src="/storage/problem-media/109798/problem_109798_img_2.gif"> n<img src="/storage/problem-media/109798/problem_109798_img_2.gif"> </i>30) – сумма всевозможных произведений различных<i> n </i>элементов множества<i> M </i>. Докажите, что если<i> A</i>15<i>>A</i>10, то<i> A₁></i>1.

Числовое множество<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>рационально.

На прямой выбрано 100 множеств<i> A₁, </i><i> A₂, </i><i> .. , </i><i> A</i>100, каждое из которых является объединением 100 попарно непересекающихся отрезков. Докажите, что пересечение множеств<i> A₁, </i><i> A₂, </i><i> .. , </i><i> A</i>100является объединением не более 9901 попарно непересекающихся отрезков (точка также считается отрезком).

Числа от 1 до 1000000 покрашены в два цвета – чёрный и белый. За ход разрешается выбрать любое число от 1 до 1000000 и перекрасить его и все числа, не взаимно простые с ним, в противоположный цвет. Вначале все числа были чёрными. Можно ли за несколько ходов добиться того, что все числа станут белыми?

Часть подмножеств некоторого конечного множества выделена. Каждое выделенное подмножество состоит в точности из2<i>k </i>элементов (<i> k </i>– фиксированное натуральное число). Известно, что в каждом подмножестве, состоящем не более чем из(<i>k+</i>1)<i>² </i>элементов, либо не содержится ни одного выделенного подмножества, либо все в нем содержащиеся выделенные подмножества имеют общий элемент. Докажите, что все выделенные подмножества имеют общий элемент.

В Думе 1600 депутатов, которые образовали 16000 комитетов по 80 человек в каждом.

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

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

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

У каждого из жителей города<i> N </i>знакомые составляют не менее 30 населения города. Житель идет на выборы, если баллотируется хотя бы один из его знакомых. Докажите, что можно так провести выборы мэра города<i> N </i>из двух кандидатов, что в них примет участие не менее половины жителей.

В стране Нашии есть военные базы, соединённые дорогами. Набор дорог называется <i>важным</i>, если после закрытия этих дорог найдутся две базы, не соединённые путем. Важный набор называется <i>стратегическим</i>, если он не содержит меньшего важного набора. Докажите, что множество дорог, каждая из которых принадлежит ровно одному из двух различных стратегических наборов, образует важный набор.

В игре "Десант" две армии захватывают страну. Они ходят по очереди, каждым ходом занимая один из свободных городов. Первый свой город армия захватывает с воздуха, а каждым следующим ходом она может захватить любой город, соединённый дорогой с каким-нибудь уже занятым этой армией городом. Если таких городов нет, армия прекращает боевые действия (при этом, возможно, другая армия свои действия продолжает). Найдётся ли такая схема городов и дорог, что армия, ходящая второй, сможет захватить более половины всех городов, как бы ни действовала первая армия? (Число городов конечно, каждая дорога соединяет ровно два города.)

Фигура Ф представляет собой пересечение <i>n</i> кругов  (<i>n</i> ≥ 2,  радиусы не обязательно одинаковы). Какое максимальное число криволинейных "сторон" может иметь фигура Ф?  (Криволинейная сторона – это участок границы Ф, принадлежащий одной из окружностей и ограниченный точками пересечения с другими окружностями.)

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

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

  а) четырёх вечеров недостаточно,

  б) пяти вечеров также недостаточно,

  в) а десяти вечеров достаточно,

  г) и даже семи вечеров тоже достаточно.

В классе 32 ученика. Было организовано 33 кружка, причём каждый кружок состоит из трёх человек и никакие два кружка не совпадают по составу. Доказать, что найдутся такие два кружка, которые пересекаются ровно по одному ученику.

На плоскости даны 2005 точек (никакие три из которых не лежат на одной прямой). Каждые две точки соединены отрезком. Тигр и Осёл играют в следующую игру. Осёл помечает каждый отрезок одной из цифр, а затем Тигр помечает каждую точку одной из цифр. Осёл выигрывает, если найдутся две точки, помеченные той же цифрой, что и соединяющий их отрезок, и проигрывает в противном случае. Доказать, что при правильной игре Осёл выиграет.

На прямоугольном экране размером <i>m</i>×<i>n</i>, разбитом на единичные клетки, светятся более  (<i>m</i> – 1)(<i>n</i> – 1)  клеток. Если в каком-либо квадрате 2×2 не светятся три клетки, то через некоторое время погаснет и четвёртая. Докажите, что тем не менее на экране всегда будет светиться хотя бы одна клетка.

Можно ли разбить множество целых чисел на три подмножества так, чтобы для любого целого значения<i>n</i>числа<i>n</i>,<i>n</i>- 50,<i>n</i>+ 1987 принадлежали трём разным подмножествам?