Олимпиадные задачи по теме «Комбинаторика» для 11 класса - сложность 2 с решениями

В клуб любителей гиперграфов в начале года записались $n$ попарно незнакомых школьников. За год клуб провёл $100$ заседаний, причём каждое заседание посетил хотя бы один школьник. Два школьника знакомились, если было хотя бы одно заседание, которое они оба посетили. В конце года оказалось, что количество знакомых у каждого школьника не меньше, чем количество заседаний, которые он посетил. Найдите минимальное значение $n$, при котором такое могло случиться.

Петя расставляет 500 королей на клетках доски 100×50 так, чтобы они не били друг друга. А Вася – 500 королей на белых клетках (в шахматной раскраске) доски 100×100 так, чтобы они не били друг друга. У кого больше способов это сделать?

В школе провели турнир по настольному теннису. Турнир состоял из нескольких туров. В каждом туре каждый участник играл ровно в одном матче, а каждый матч судил один из не участвовавших в нем игроков. После нескольких туров оказалось, что каждый участник сыграл по одному разу с каждым из остальных. Может ли оказаться, что все участники турнира судили одинаковое количество встреч?

За круглым вращающимся столом, на котором стоят 8 белых и 7 чёрных чашек, сидят 15 гномов. Они надели 8 белых и 7 чёрных колпачков. Каждый гном берёт себе чашку, цвет которой совпадает с цветом его колпачка, и ставит напротив себя, после этого стол поворачивается случайным образом. Какое наибольшее число совпадений цвета чашки и колпачка можно гарантировать после поворота стола (гномы сами выбирают, как сесть, но не знают, как повернётся стол)?

В зале стоят шесть стульев в два ряда – по три стула в каждом, один ряд ровно за другим. В зал пришли шесть человек различного роста.

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

Имеется 21 ненулевое число. Для каждых двух из них вычислены их сумма и произведение. Оказалось, что половина всех сумм положительна и половина – отрицательна. Каково наибольшее возможное количество положительных произведений?

Жили-были двадцать шпионов. Каждый из них написал донос на десять своих коллег.

Докажите, что не менее, чем десять пар шпионов донесли друг на друга.

Имеется выпуклый многогранник со 100 рёбрами. Все его вершины срезали плоскостями-ножами близко от самих вершин (то есть так, чтобы плоскости-ножи не пересекались друг с другом внутри или на границе многогранника). Найдите у полученного многогранника

  a) число вершин;

  б) число рёбер.

Дана таблица 3×3 (как для игры в крестики-нолики). В четыре случайно выбранные ячейки случайным образом поставили четыре фишки.

Найдите вероятность того, что среди этих четырёх фишек найдутся три, которые стоят в один ряд по вертикали, по горизонтали или по диагонали.

Василий Петров выполняет задание по английскому языку. В этом задании есть 10 английских выражений и их переводы на русский в случайном порядке. Нужно установить верные соответствия между выражениями и их переводами. За каждое правильно установленное соответствие даётся 1 балл. Таким образом, можно получить от 0 до 10 баллов. Вася ничего не знает, поэтому выбирает варианты наугад. Найдите вероятность того, что он получит ровно 9 баллов.

Сколько существует разных способов разбить число 2004 на натуральные слагаемые, которые <i>приблизительно равны</i>? Слагаемых может быть одно или несколько. Числа называются <i>приблизительно равными</i>, если их разность не больше 1. Способы, отличающиеся только порядком слагаемых, считаются одинаковыми.

На плоскости проведены <i>n</i> прямых так, что каждые две пересекаются, но никакие четыре через одну точку не проходят. Всего имеются 16 точек пересечения, причём через 6 из них проходят по три прямые. Найдите <i>n</i>.

Имеется несколько юношей, каждый из которых знаком с некоторыми девушками. Две свахи знают, кто с кем знаком. Одна сваха заявляет: "Я могу одновременно поженить всех брюнетов так, чтобы каждый из них женился на знакомой ему девушке!" Вторая сваха говорит: "А я могу устроить судьбу всех блондинок: каждая выйдет замуж за знакомого юношу!" Этот диалог услышал любитель математики, который сказал: "В таком случае можно сделать и то, и другое!" Прав ли он?

Точка выходит из начала координат на прямой и делает <i>a</i> шагов на единицу вправо, <i>b</i> шагов на единицу влево в каком-то порядке, причём  <i>a > b</i>.  Размахом блуждания точки назовём разность между наибольшей и наименьшей координатами точки за всё время блуждания.

  а) Найдите наибольший возможный размах блуждания.

  б) Найдите наименьший возможный размах.

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

Знатоки и Телезрители играют в "Что? Где? Когда" до шести побед – кто первый выиграл шесть раундов, тот и победил в игре. Вероятность выигрыша Знатоков в одном раунде равна 0,6, ничьих не бывает. Сейчас Знатоки проигрывают со счетом  3 : 4.  Найдите вероятность того, что Знатоки все же выиграют.

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

 а) муха окажется в точке  (8, 10);

  б) муха окажется в точке  (8, 10),  по дороге пройдя по отрезку, соединяющему точки  (5,6)  и  (6. 6);

  в) муха окажется в точке  (8, 10),  пройдя внутри круга радиуса 3 с центром в точке  (4, 5). <div align="center"><img align="middle" src="/storage/problem-media/65317/problem_65317_img_2.png"></div>

В городе, где живет Рассеянный Ученый, телефонные номера состоят из 7 цифр. Ученый легко запоминает телефонный номер, если этот номер палиндром, то есть он одинаково читается слева направо и справа налево. Например, номер 4435344 Ученый запоминает легко, потому что этот номер палиндром. А номер 3723627 не палиндром, поэтому Ученый такой номер запоминает с трудом. Найдите вероятность того, что телефонный номер нового случайного знакомого Ученый запомнит легко.

В финал конкурса спектаклей к 8 Марта вышли два спектакля. В первом играли <i>n</i> учеников 5 класса А, а во втором – <i>n</i> учеников 5 класса Б. На спектакле присутствовали 2<i>n</i> мам всех 2<i>n</i> учеников. Лучший спектакль выбирается голосованием мам. Известно, что ровно половина мам честно голосует за лучший спектакль, а другая половина в любом случае голосует за спектакль, в котором участвует её ребенок.

  а) Найдите вероятность того, что лучший спектакль победит с перевесом голосов.  б) Тот же вопрос, если в финал вышло больше двух спектаклей.

В Анчурии проходит чемпионат по шашкам в несколько туров. Дни и города проведения туров определяются жеребьёвкой. По правилам чемпионата никакие два тура не могут пройти в одном городе, и никакие два тура не могут пройти в один день. Среди болельщиков устраивается лотерея: главный приз получает тот, кто до начала чемпионата правильно угадает, в каких городах и в какие дни пройдут все туры. Если никто не угадает, то главный приз перейдёт в распоряжение оргкомитета чемпионата. Всего в Анчурии восемь городов, а на чемпионат отведено всего восемь дней. Сколько туров должно быть в чемпионате, чтобы оргкомитет с наибольшей вероятностью получил главный приз?

Монету бросают 10 раз. Найдите вероятность того, что ни разу не выпадут два орла подряд.

Вероятность того, что купленная лампочка будет работать, равна 0,95.

Сколько нужно купить лампочек, чтобы с вероятностью 0,99 среди них было не менее пяти работающих?

Прямоугольный параллелепипед размером <i>m</i>×<i>n</i>×<i>k</i> разбит на единичные кубики. Сколько всего образовалось параллелепипедов (включая исходный)?

На новогодний вечер пришли несколько супружеских пар, у каждой из которых было от 1 до 10 детей. Дед Мороз выбирал одного ребёнка, одну маму и одного папу из трёх разных семей и катал их в санях. Оказалось, что у него было ровно 3630 способов выбрать нужную тройку людей. Сколько всего могло быть детей на этом вечере?

На плоскости отметили все вершины правильного <i>n</i>-угольника, а также его центр. Затем нарисовали контур этого <i>n</i>-угольника, и центр соединили со всеми вершинами; в итоге <i>n</i>-угольник разбился на <i>n</i> треугольников. Вася записал в каждую отмеченную точку по числу (среди чисел могут быть равные). В каждый треугольник разбиения он записал в произвольном порядке три числа, стоящих в его вершинах; после этого он стёр числа в отмеченных точках. При каких <i>n</i> по тройкам чисел, записанным в треугольниках, Петя всегда сможет восстановить число в каждой отмеченной точке?

В каждой клетке квадрата 8×8 клеток проведена одна из диагоналей. Рассмотрим объединение этих 64 диагоналей. Оно состоит из нескольких связных частей (к одной части относятся точки, между которыми можно пройти по одной или нескольким диагоналям). Может ли количество этих частей быть больше

  а) 15;

  б) 20?

  в) Может ли в аналогичной задаче про квадрат <i>n×n</i> клеток получиться больше чем ^<i>n</i>²/₄ частей (для  <i>n</i> > 8)?