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

Отмечены вершины и середины сторон правильного десятиугольника (то есть всего отмечено 20 точек).

Сколько существует треугольников с вершинами в отмеченных точках?

Дан правильный девятиугольник.

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

В шахматном турнире было 12 участников (каждый сыграл с каждым по одному разу). По итогам турнира оказалось, что есть 9 участников, каждый из которых набрал не более 4 очков. Известно, что Петя набрал ровно 9 очков. Как он сыграл с каждым из двух остальных шахматистов? (Победа – 1 очко, ничья – 0,5 очка, поражение – 0 очков.)

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

Боря и Миша едут в поезде и считают столбы за окном: "один, два, ...". Боря не выговаривает букву "Р", поэтому при счете он пропускает числа, в названии которых есть буква "Р", а называет сразу следующее число без буквы "Р". Миша не выговаривает букву "Ш", поэтому пропускает числа с буквой "Ш". У Бори последний столб получил номер "сто". Какой номер этот столб получил у Миши?

У Алёши есть пирожные, разложенные в несколько коробок. Алёша записал, сколько пирожных в каждой коробке. Серёжа взял по одному пирожному из каждой коробки и положил их на первый поднос. Затем он снова взял по одному пирожному из каждой непустой коробки и положил их на второй поднос – и так далее, пока все пирожные не оказались разложенными по подносам. После этого Серёжа записал, сколько пирожных на каждом подносе. Докажите, что количество различных чисел среди записанных Алёшей равно количеству различных чисел среди записанных Серёжей.

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

Круглая мишень разбита на 20 секторов, которые нумеруются по кругу в каком-либо порядке числами 1, 2, ..., 20. Если секторы занумерованы, например, в следующем порядке  1, 20, 5, 12, 9, 14, 11, 8, 16, 7, 19, 3, 17, 2, 15, 10, 6, 13, 4, 18,  то наименьшая из разностей между номерами соседних (по кругу) секторов равна  12 – 9 = 3.

Может ли указанная величина при нумерации в другом порядке быть больше 3?

Каково наибольшее возможное значение этой величины?

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

Рассмотрим лист клетчатой бумаги со стороной клетки, равной 1. Пусть <i>P_k</i> – число всех непересекающихся ломаных длины <i>k</i>, начинающихся в точке <i>O</i> – некотором фиксированном узле сетки. Доказать, что  <i>P_k</i>·3^–<i>k</i> < 2  для любого <i>k</i>.

Имеется 1959 положительных чисел<i>a</i>₁,<i>a</i>₂...,<i>a</i>₁₉₅₉, сумма которых равна 1. Рассматриваются всевозможные комбинации из 1000 чисел, причём комбинации считаются совпадающими, если они отличаются только порядком чисел. Для каждой комбинации рассматривается произведение входящих в неё чисел. Доказать, что сумма всех этих произведений меньше 1.

  а) Выбраны 6 различных цветов; требуется раскрасить 6 граней куба, каждую в особый цвет из числа избранных. Сколькими геометрически различными способами можно это сделать? Геометрически различными называются две такие расцветки, которые нельзя совместить одну с другой при помощи вращений куба вокруг его центра.

  б) Решить ту же задачу для случая раскраски граней додекаэдра в 12 различных цветов.

На совместный симпозиум лжецов (всегда лгут) и правдолюбов (всегда говорят правду) собрались 100 участников, среди которых не все лжецы и не все правдолюбы. Каждые два участника либо знакомы, либо незнакомы друг с другом. Каждый ответил «да» или «нет» на вопрос «Знакомы ли вы?» про каждого из остальных. Какое наименьшее количество ответов «да» могло быть получено?

На совместный симпозиум лжецов (всегда лгут) и правдолюбов (всегда говорят правду) собрались 12 участников, среди которых не все лжецы и не все правдолюбы. Каждые два участника либо знакомы, либо незнакомы друг с другом. Каждый ответил «да» или «нет» на вопрос «Знакомы ли вы?» про каждого из остальных. Какое наименьшее количество ответов «да» могло быть получено?

а) У Полины есть волшебная шоколадка в форме клетчатой лесенки со стороной 10 (см. рисунок), в каждой дольке своя начинка. Каждую минуту Полина отламывает верхний ряд долек шоколадки, поворачивает его на 90 градусов <i>против часовой стрелки</i> и приставляет её к оставшейся части в виде столбца слева, как показано на рисунке (после этого столбец слипается с другой частью, и снова получается цельная лесенка). Как только каждая долька вернётся на то же место, в котором она была изначально, Полина съест всю шоколадку. Через сколько минут это произойдёт?

Как только каждая долька вернётся на то же место, в котором она была изначально, Саша съест шоколадку. Через сколько минут это произойдёт?

<img src="/storage/problem-media/67331/problem_67331_img_2.png">

б) У...

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

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

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

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

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

Имеется выпуклый многогранник со 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.  Найдите вероятность того, что Знатоки все же выиграют.