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

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

Пусть<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.

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

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

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

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

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

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

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

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

<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> ходов было бы столько же.