Олимпиадные задачи по теме «Теория множеств» для 11 класса - сложность 4 с решениями
Теория множеств
НазадНа плоскости рассматривается конечное множество равных, параллельно расположенных квадратов, причем среди любых<i> k+</i>1квадратов найдутся два пересекающихся. Докажите, что это множество можно разбить не более чем на2<i>k-</i>1непустых подмножеств так, что в каждом подмножестве все квадраты будут иметь общую точку.
Пусть<i> M={x<sub>1</sub>, .., x</i>30<i>} </i>– множество, состоящее из 30 различных положительных чисел;<i> A<sub>n</sub> </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<sub>1</sub>></i>1.
У каждого из жителей города<i> N </i>знакомые составляют не менее 30 населения города. Житель идет на выборы, если баллотируется хотя бы один из его знакомых. Докажите, что можно так провести выборы мэра города<i> N </i>из двух кандидатов, что в них примет участие не менее половины жителей.
В школе изучают 2<i>n</i> предметов. Все ученики учатся на 4 и 5. Никакие два ученика не учатся одинаково, ни про каких двух нельзя сказать, что один из них учится лучше другого. Доказать, что число учеников в школе не больше <img align="absmiddle" src="/storage/problem-media/78166/problem_78166_img_2.gif"> .
(Мы считаем, что ученик <i>p</i> учится лучше ученика <i>q</i>, если у <i>p</i> оценки по всем предметам не ниже, чем у <i>q</i>, а по некоторым предметам – выше.)
а) На рисунке слева изображены шесть точек, которые лежат по три на четырёх прямых. Докажите, что можно 24 разными способами отобразить это множество из шести точек на себя так, чтобы каждые три точки, лежащие на одной прямой, отобразились в три точки, лежащие на одной прямой. <div align="center"><img src="/storage/problem-media/73735/problem_73735_img_2.gif"></div>б) На рисунке справа девять точек лежат по три на девяти прямых, причём через каждую точку проходит по три таких прямых. Эти девять точек и девять прямых образуют знаменитую <i>конфигурацию Паскаля</i>. Сколькими способами можно множество наших девяти точек отобразить на себя так, чтобы каждая тройка точек, лежащая на одной из девяти наших прямых, отобразилась на тройку точек, ко...
<i>P</i> и <i>Q</i> – подмножества множества выражений вида (<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>n</sub></i>), где <i>a<sub>i</sub></i> – натуральные числа, не превосходящие данного натурального числа <i>k</i> (таких выражений всего <i>k<sup>n</sup></i>). Для каждого элемента (<i>p</i><sub>1</sub>, ..., <i>p<sub>n</sub></i>) множества <i>P</i> и каждого элемента (<i>q</i><sub>1</sub>, ..., <i>q<sub>n</sub></i>) множества <i>Q</i> существует хотя бы один такой номер <i>m</i>, что...
<i>m</i> и <i>n</i> – натуральные числа, <i>m</i> < <i>n</i>. Докажите, что <img align="absmiddle" src="/storage/problem-media/73673/problem_73673_img_2.gif">
Учащиеся одной школы часто собираются группами и ходят в кафе-мороженое. После такого посещения они ссорятся настолько, что никакие двое из них после этого вместе мороженое не едят. К концу года выяснилось, что в дальнейшем они могут ходить в кафе-мороженое только поодиночке. Докажите, что если число посещений было к этому времени больше 1, то оно не меньше числа учащихся в школе.
У фокусника и помощника есть колода с картами; одна сторона ("рубашка") у всех карт одинакова, а другая окрашена в один из 2017 цветов (в колоде по 1000000 карт каждого цвета). Фокусник и помощник собираются показать следующий фокус. Фокусник выходит из зала, а зрители выкладывают на стол в ряд <i>n</i> > 1 карт рубашками вниз. Помощник смотрит на эти карты, а затем все, кроме одной, переворачивает рубашкой вверх, не меняя их порядка. Затем входит фокусник, смотрит на стол, указывает на одну из закрытых карт и называет её цвет. При каком наименьшем <i>k</i> фокусник может заранее договориться с помощником так, чтобы фокус гарантированно удался?
На прямой сидит конечное число лягушек в различных целых точках. За ход ровно одна лягушка прыгает на 1 вправо, причём они по-прежнему должны быть в различных точках. Мы вычислили, сколькими способами лягушки могут сделать <i>n</i> ходов (для некоторого начального расположения лягушек). Докажите, что если бы мы разрешили тем же лягушкам прыгать влево, запретив прыгать вправо, то способов сделать <i>n</i> ходов было бы столько же.