Тема КОМБИНАТОРИКА

Количество способов, исходов, слагаемых

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела комбинаторика

Разделы подтемы Количество способов, исходов, слагаемых

Правила сложения и умножения

Счастливые билеты

Зачем делить в комбинаторике

Раскрываем скобки комбинаторными рассуждениями

Перебор случаев

Числа сочетаний (цэ изэн пока)

Метод шаров и перегородок

Рекурренты в комбинаторике и числа Фибоначчи f(n)

Числа Каталана

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#104848

Найти количество пар целых чисел $(a;b)$ таких, что $1 ≤a ≤700,1≤ b≤ 700,$ сумма $a +b$ делится на $7,$ а произведение $ab$ делится на $5.$ (При $a ⁄=b$ пары $(a;b)$ и $(b;a)$ считаются различными.)

Подсказки к задаче

Подсказка 1

Давайте разберем два случая: a делится на 5 и a не делится на 5. Сколько для каждого варианта есть подходящих b? Какие они?

Подсказка 2

В случае "a делится на 5" на b накладываются только ограничения по остатку при делимости на 7. Какой должна быть сумма остатков при делении на 7 у a и b?

Подсказка 3

В первом случае подходит каждое седьмое b. Аналогично можно разобрать второй случай, но накладывается ещё одно ограничение на b ;)

Показать ответ и решение

Рассмотрим два случая.

1) Пусть $a$ делится на 5 (на отрезке $[1;700]$ имеется $700:5 =140$ таких значений $a$ ). Для каждого такого значения $a$ подходят те и только те значения $b$ , при которых сумма остатков от деления $a$ на 7 и $b$ на 7 равна 0 или 7, т. е. подходит одно из каждых семи последовательных значений $b$ . Итого, для каждого значения $a$ получаем по 100 вариантов.

2) Пусть $a$ не делится на 5 (на отрезке $[1;700]$ имеется $700− 140= 560$ таких значений $a$ ). Для каждого такого $a$ подходят те и только те значения $b$ , кратные 5, при которых сумма остатков от деления $a$ на 7 и $b$ на 7 равна 0 или 7, т. е. подходит одно из каждых $5 ⋅7 =35$ последовательных значений $b$ . Итого, для каждого значения $a$ получаем по 20 вариантов.

Суммируем количество пар: $100⋅140 +560⋅20=25200$ .

Ответ: 25200

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#111331

Сколькими способами можно представить число $n= 2401 ⋅3500$ в виде произведения двух натуральных чисел $x$ и $y,$ где $y$ делится на $x?$

Источники: Физтех 2025 11.2 (olymp-online.mipt.ru)

Подсказки к задаче

Подсказка 1

Заметим, что x и y имеют в разложении на простые множители только двойки и тройки. Как соотносятся их степени вхождения, если y делится на x?

Подсказка 2

Да, степень вхождения и двойки, и тройки в y больше, чем в x. Тогда можно обозначить эти степени вхождения переменными, а дальше перемножить варианты степени вхождения двойки и тройки в y.

Показать ответ и решение

Заметим, что делитель числа $n$ не может иметь простые множители кроме 2 и 3, так как само $n$ имеет только эти простые числа в своем каноническом разложении. Отсюда любой делитель $n$ имеет вид $a b 2 3,$ где $a,b∈ ℤ$ и $0≤ a≤401,0≤ b≤500.$

Тогда $y$ так же имеет вид $a b y = 23$ с аналогичными условиями на $a$ и $b.$ Отсюда

n 24013500 401−a 500−b x= y = -2a3b--=2 3

Рассмотрим отношение чисел $y$ и $x:$

a b y = -4012−a3500−b = 22a−40132b−500 x 2 3

Получившееся число является целым, так как $y$ делится на $x$ по условию. Это значит, что $2a− 401≥ 0$ и $2b− 500≥ 0,$ то есть $a ≥201$ и $b≥250.$

Таким образом, у нас есть $401 − 201+ 1= 201$ способ выбрать число $a,$ на каждый из которых есть $500− 250+1 =251$ способ выбрать число $b,$ откуда количество способов выбрать пару $a$ и $b$ равно $201⋅251= 50451.$ При этом каждая такая пара задаёт разложение числа $n$ на множители $x$ и $y,$ где $y$ делится на $x,$ поэтому $50451$ и будет ответом.

Ответ:

50451

Ошибка.
Попробуйте повторить позже

Задача 3#119820

Пусть $n >3$ — натуральное число. Сколько существует способ выбрать два не пересекающихся прямоугольника внутри квадрата $n× n,$ идущих по линиям сетки? Прямоугольники пересекаются, если у них есть хотя бы одна общая внутренняя клетка или общая точка на границе.

Источники: Турнир Ломоносова - 2025, 11.2(см. turlom.olimpiada.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Давайте попробуем задать прямоугольники при помощи двух интервалов: один для горизонтальной стороны, а другой — для вертикальной! Тогда несложно вывести условие того, что прямоугольники не пересекаются.

Подсказка 3

Для начала разберите случай, когда не пересекаются "горизонтальные" интервалы. А сколько тогда способов будет для "вертикальных" интервалов?

Подсказка 4

Если "горизонтальные" интервалы не пересекаются, то вертикальные можно выбрать абсолютно любыми! Аналогично и со случаем, когда не пересекаются "вертикальные" интервалы. Осталось лишь проверить, не посчиталось ли ничего лишнего ;)

Показать ответ и решение

Прямоугольник можно задать двумя интервалами: один определяет его горизонтальную сторону, а другой — вертикальную. Чтобы прямоугольники не пересекались, необходимо и достаточно, чтобы либо горизонтальные, либо вертикальные интервалы были непересекающимися (возможно, оба).

Сначала посчитаем количество способов, при которых горизонтальные интервалы не пересекаются. Пусть эти интервалы — $[a,b]$ и $[c,d].$ Поскольку порядок прямоугольников не имеет значения, без потери общности можно предположить, что $a< c,$ то есть $a <b< c< d.$ Тогда количество способов выбрать $a,b,c,d$ равно $4 Cn+1.$ На вертикальные интервалы ограничений нет, поэтому количество способов выбрать их равно $2 2 (C n+1) .$ Таким образом, общее количество пар прямоугольников с непересекающимися горизонтальными интервалами равно $4 2 2 Cn+1⋅(C n+1) .$ По симметрии, количество пар прямоугольников с непересекающимися вертикальными интервалами такое же.

Осталось посчитать и вычесть количество способов, при которых и горизонтальные, и вертикальные интервалы не пересекаются. Пусть горизонтальные интервалы — $[a,b]$ и $[c,d],$ а вертикальные — $[e,f]$ и $[g,h].$ Без потери общности можно предположить $a< b< c< d,$ поэтому оличество способов выбрать горизонтальные интервалы равно $C4n+1.$ Однако случаи $e <f <g <h$ и $g <h < e<f$ теперь различны, поэтому количество способов выбрать вертикальные интервалы равно $2⋅C4n+1.$ Следовательно, количество пар прямоугольников, у которых и горизонтальные, и вертикальные интервалы не пересекаются, равно $2 ⋅(C4n+1)2.$

Ответ:

$2⋅C4 ⋅(C2 )2 − 2⋅(C4 )2 n+1 n+1 n+1$

Ошибка.
Попробуйте повторить позже

Задача 4#120565

У скольких наборов из $4$ натуральных чисел с суммой $1001$ среди чисел есть равные?

Источники: Бельчонок - 2025, Вариант 1, 11.3(см. dovuz.sfu-kras.ru)

Подсказки к задаче

Подсказка 1

Пусть (k, k, a, b) — такой набор. Что можно сказать про a и b? Как по ним построить k?

Подсказка 2

a и b разной чётности. А каким методом привыкли искать количество способов разложить что-то в фиксированную сумму?

Подсказка 3

Воспользуемся методом шаров и перегородок! Только вот следить за тем, чтобы какие-то области были равны, сложно. Так что делать с k?

Подсказка 4

Можно разлагать 1002 в три слагаемых — 2k, a, b+1! Но как быть с тем, что нам нужны именно чётные количества?

Подсказка 5

Можно разложить сначала сумму в 501, а затем все количества умножить на 2!

Показать ответ и решение

Пусть $(k,k,a,b)$ — такой набор. Так как $a +b= 1001− 2k$ нечётно, то числа $a$ и $b$ разной чётности и между собой не равны. Пусть $a$ чётно. Упорядоченной парой $(a,b)$ набор однозначно определяется, поскольку $k$ вычисляется однозначно, а двух пар равных чисел в наборе нет ввиду нечётности суммы.

Сопоставим набору строку $(2k,a,b+1)$ . В ней все слагаемые чётны, а их сумма равна $1002$ . По такой строке набор тоже однозначно восстанавливается. Число таких строк можно посчитать так: выложим ряд из $501$ двухрублёвой монет, в который в два разных промежутка вставлены две перегородки. Числа $2k$ , $a$ и $b+ 1$ будут равны сумме монет (в рублях) до первой перегородки, между перегородками и после второй перегородки соответственно. Так как между монетами $500$ промежутков, есть ровно $2 C500$ способов выбрать два из них.

500! 499⋅500 C2500 = 2!⋅498! =-2---= 124750

Ответ:

$C2 = 124750 500$ наборов

Ошибка.
Попробуйте повторить позже

Задача 5#120572

Собрав $1001$ орех, бельчата Боря, Вася и Петя решили разделить их. Каждый должен что-то получить, все — разное число орехов, Боря — больше всех. Сколькими способами можно так поделить орехи?

Источники: Бельчонок - 2025, Вариант 4, 11.3(см. dovuz.sfu-kras.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Совпасть количества орехов могли только у каких-то двух, и орехов у них может быть любое число от 1 до 500. Осталось лишь аккуратно посчитать количество таких способов и вычесть из общего!

Подсказка 4

Не забудьте про то, что иногда у Бори не наибольшее число орехов. Но это можно исправить.

Показать ответ и решение

Сосчитаем способы без учёта ограничений на повторы и максимум у Бори. Метод шаров и перегородок даёт $C2 =499500 1000$ способов деления.

Теперь вычтем способы с повторами. Так как 1001 не кратно 3, число орехов может совпасть только у двоих, это число $n$ может быть любым от 1 до 500. Для каждого возможного $n$ есть 3 способа распределить $n,$ $n$ и $1000 − 2n$ орехов между троими. Значит, число способов с повторами равно $500⋅3= 1500,$ а без повторов — $499500− 1500 =498000.$

Пусть теперь бельчата делят ”случайно”, так, что каждый получает разное число. Однако дальше они распределение ”исправляют” : тот, кто получит больше всех, меняется своей долей с Борей. Тогда одно и то же ”исправленное” распределение получается из трёх ”случайных”: Боря мог получить максимум либо сразу, либо поменявшись с Васей, либо поменявшись с Петей. Тогда ”исправленных” распределений втрое меньше, чем ”случайных”, т.е. $498000:3 =166000.$

Ответ:

$166000$ наборов

Ошибка.
Попробуйте повторить позже

Задача 6#121577

На полосе из $2025$ клеток стоит топотун, который может перемещаться на одну или две клетки. Ему необходимо пройти сначала в один конец полосы, затем в другой и вернуться в начальное положение, причем на каждом из трех этапов двигаться можно только в сторону своей цели. Общее количество различных последовательностей ходов, которыми топотун может осуществить желаемое, искать не требуется. Необходимо выяснить, при каком начальном положении общее количество таких вариантов будет наибольшим.

Источники: Надежда Энергетики - 2025, 11.4(см. www.energy-hope.ru)

Подсказки к задаче

Подсказка 1

Давайте посчитаем количество способов попасть на конкретную клетку с номером k. Назовем это число Nₖ. Как его как можно проще выразить или посчитать?

Подсказка 2

Nₖ = Nₖ₋₁ + Nₖ₋₂. Теперь мы можем предположить, что изначально мы стояли на клетке с номером k, и явно записать через N количество вариантов для нашего пути.

Подсказка 3

Если всё будет посчитано правильно, то необходимо будет найти максимум у выражения Nₖ*N₂₀₂₅₋ₖ₊₁. Но сравнивать между собой такие числа сразу при всех k неудобно, значит, надо с чем-то одним. Можно выдвинуть гипотезу об ответе, какую?

Подсказка 4

Можно сравнить указанное выше число с N₂₀₂₅. Выдвигаем гипотезу о конце полосы!

Подсказка 5

Доказать неравенство можно как комбинаторно, так и по индукции, используя равенство, которое мы получили для Nₖ.

Показать ответ и решение

Пусть $N k$ — количество способов попасть на $k−$ ю по счету клетку. Туда топотун может попасть двумя способами: с клетки $k− 1$ либо $k− 2.$ Поэтому

Nk = Nk−1+ Nk−2

Если задать клетке, на которой стоит топотун, номер 1, то $N =1, 2$ $N =2. 3$

Таким образом, количество ходов задается хорошо известной последовательностью чисел Фибоначчи (начиная со второго).

Если топотун начинает с клетки с номером $k,$ то количество способов дойти до клетки с номером $L= 2025$ равно $N . L−k+1$ Количество способов дойти от клетки с номером $L= 2025$ до первой клетки (пройти всю полосу) составляет $NL,$ а количество способов вернуться с клетки номер один на клетку с номером $k$ равно $Nk.$ Общее количество вариантов есть $NL−k+1⋅NL ⋅Nk.$ Если же движение начинается из конца полосы, то общее количество вариантов есть $NL ⋅NL.$

Таким образом, необходимо найти максимум по параметру $k$ выражения

Nk⋅NL−k+1

(для $L = 2025$ ) и сравнить его с $N . L$

Если провести расчеты при небольших значениях $L,$ то можно выдвинуть гипотезу, что

Nk⋅NL−k+1 < NL

1 вариант. Рассмотрим выражения $N ⋅N k L−k+1$ и $N L$ как количество способов передвинуться по полосе. Первое из них соответствует количеству способов переместиться на $L −$ ю клетку вправо, но с обязательным посещением

клетки с номером $k.$ Второе $(N ) L$ есть общее количество способов переместиться на такое же количество клеток, которое включает в себя как варианты с посещением клетки с номером $k,$ так и варианты с перепрыгиванием этой клетки.

Следовательно, $NL > Nk ⋅NL −k+1.$

2 вариант. Перепишем доказываемую формулу в виде

Nk ⋅Nm <Nk+m −1

и докажем ее индукцией по $k$ при фиксированном $m.$

Базу проверим для $k =2.$ $N2 ⋅Nm =1⋅Nm < N2+m− 1.$

Теперь рассмотрим значение параметра $k+ 1$ в предположении, что для всех предыдущих значений $k$ неравенство верно.

N(k+1)+m−1 = Nk+m−1 +Nk+m −2 > Nk⋅Nm + Nk−1⋅Nm =(Nk +Nk−1)Nm = Nk+1⋅Nm

Таким образом, максимальное количество вариантов будет при начале движения из любого конца полосы.

Ответ:

При начале движения из любого конца полосы

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#121754

В комплекте для сборки игрушечного поезда есть один локомотив (который всегда расположен спереди), $2n$ одинаковых красных вагонов и $3n$ одинаковых желтых вагонов. Назовем поезд длинным, если в нем есть хотя бы $n$ вагонов (не считая локомотива). Сколько различных длинных поездов можно собрать, используя этот комплект? (Ответ должен быть дан в замкнутом виде: в ответе не должно быть сумм с переменным числом слагаемых, многоточий и т.д.)

Источники: Высшая проба - 2025, 11.4(см. olymp.hse.ru)

Подсказки к задаче

Подсказка 1

Сначала хотим найти количество всевозможных поездов, которые можем собрать. Так как длины поездов могут быть различны, удобно рассматривать каждую отдельно. Также, так как количество красных и жёлтых вагонов различно, хотим не рассматривать отдельные случаи (для больших длин, например, когда есть верхняя граница для красных вагонов). В этом случае удобно для каждой длины зафиксировать количество вагонов какого-то одного цвета, а потом выбрать другой цвет. Как это можно обобщить на сумму всех случаев?

Подсказка 2

В общем виде, для длины x, и, допустим, количества красных вагонов y, получаем, что количество поездов будет равно C из x по y (так как вагоны считаются одинаковыми, и нас интересует только расположение цветов). Теперь зафиксируем количество красных вагонов и просуммируем по всевозможным длинам поезда. Получаем какую-то неприятную сумму "цешек", которую, однако, можно упростить, если применить тождество Паскаля. Как нам это помогло?

Подсказка 3

Получаем телескопичесекю сумму, где остается только один биномиальный коэффициент. А теперь вспомним, что нам необходимо просуммировать эти результаты для всевозможного количества красных вагонов. Снова сводим к телескопической сумме. Что дальше?

Подсказка 4

Теперь остается только посчитать количество поездов, в которых менее n вагонов, чтобы вычесть его из общего количества поездов. Здесь задача проще: каждого цвета по количеству вагонов хватает для того, чтобы заполнить поезд любой длины, так что можно не так утруждаться. Как легко посчитать?

Подсказка 5

Можем просто считать, что для каждой позиции имеем 2 варианта: красный или жёлтый. Суммируем по всевозможным длинам (от 0 до n не включительно), вычитаем из ранее найденного и получаем ответ.

Показать ответ и решение

Посчитаем количество всех поездов, которые можно собрать в данном наборе, и потом вычтем количество поездов, в которых не более $n − 1$ вагонов.

Зафиксируем число $k$ $(0≤ k≤ 2n)$ и посчитаем, сколько всего поездов с ровно $k$ красными вагонами. Жёлтых вагонов может быть от $0$ до $3n,$ и для каждого числа $l$ жёлтых вагонов от $0$ до $3n$ мы выбираем $k$ мест в строке длины $k+l.$ Таким образом, искомое количество поездов с $k$ красными вагонами равно сумме

Ckk +Ckk+1 +⋅⋅⋅+ Ckk+3n

Докажем, что эта сумма равна $k+1 Ck+3n+1.$

Распишем каждое слагаемое, пользуясь следующим тождеством Паскаля:

b+1 Cba = Ca+1− Cb+a1

Мы получим:

( k+1 k+1) ( k+1 k+1) ( k+1 k+1) ( k+1 k+1 ) ( k+1 k+1) Ck+1 − Ck + C k+2 − Ck+1 + Ck+3 − Ck+2 + ⋅⋅⋅ + Ck+3n− Ck+3n−1 + Ck+3n+1− Ck+3n

В каждой скобке вычитаемое равно уменьшаемому из предыдущей скобки. Нетронутым останется лишь уменьшаемое в последней скобке, равное $k+1 Ck+3n+1,$ — это и есть искомый результат сложения.

Заметим, что в силу симметрии биномиальных коэффициентов этот результат можно переписать как

k+1 3n Ck+3n+1 = Ck+3n+1

Теперь нужно сложить эти числа по всем $k$ от $0$ до $2n.$ Получим сумму

3n 3n 3n C3n+1 +C3n+2+ ⋅⋅⋅+ C5n+1

которая суммируется аналогичным образом через тождество Паскаля, и результат этого суммирования равен

3n+1 3n 2n+1 C5n+2 − C3n = C5n+2 − 1

Мы посчитали количество всех поездов. Осталось лишь вычесть количество поездов, в которых не более $n − 1$ вагонов, но для каждого $l≤ n− 1$ количество поездов длины $l$ очевидно равно $2l,$ а всего в сумме таких поездов $2n− 1.$ Таким образом, длинных поездов $C2n+1− 2n. 5n+2$

Ответ:

$C2n+1− 2n 5n+2$

Ошибка.
Попробуйте повторить позже

Задача 8#126198

Найдите количество перестановок ( $a ,a,...,a 1 2 10$ ) набора чисел $(1,2,...,10),$ таких, что $a ≤2a ≤ ...≤ 10a . 1 2 10$

Источники: Курчатов - 2025, 10.5 ( см. olimpiadakurchatov.ru)

Подсказки к задаче

Подсказка 1

Для решения данной задачи необходимо доказать, что количество перестановок чисел a₁; a₂;...; aₙ равно F(n + 1), где F(n) — число Фибоначчи с номером n.

Подсказка 2

Будем доказывать это утверждение по индукции. Для n = 1 и n = 2 можно проверить утверждение перебором (получается, база индукции уже есть!). Для того, чтобы доказать данное утверждение для больших n будем рассматривать такой индекс k, что k-ый член последовательности равен n. Посмотрим тогда внимательно на отрезок [k + 1;n] и подумаем, какие числа могут на нём лежать.

Показать ответ и решение

Докажем следующее утверждение: количество перестановок $a ,a ,...,a 1 2 n$ чисел $1,2,...,n$ таких, что $a ≤ 2a ≤ ...≤ na , 1 2 n$ равно $F , n+1$ где $Fn$ — $n$ -е число Фибоначчи $(F1 =F2 =1,$ $Fk+1 = Fk+ Fk−1).$ Отсюда будет следовать, что ответом является число $F11 = 89.$

Обозначим через $Pn$ количество искомых перестановок длины $n.$ Заметим, что $P1 = 1,$ $P2 = 2.$ Докажем, что $Pn+1 = Pn+ Pn− 1$ при $n ≥ 2.$ Для этого поймем, на какой позиции может стоять в нашей перестановке число $n.$

Пусть $k$ — такой индекс, что $ak = n.$ При $k= n$ мы получаем $an = n,$ количество таких перестановок равно $Pn−1.$ При $k =n − 1$ имеем $nan ≥ n(n − 1),$ тогда $an ≥ n− 1.$ Но $an ⁄= n,$ поэтому $an = n− 1,$ количество перестановок равно $Pn−2.$

Предположим, что существует такая перестановка, что $ak =n$ при $k ≤n − 2.$ Для каждого $i∈(k,n)$ имеем

kn = kak ≤iai < nai,

поэтому $ai ≥ k+ 1.$ Кроме того,

nan ≥ (n − 1)an−1 ≥(n− 1)(k+ 1)

Из этого следует

an ≥ k+1

Получается, что все числа $ak,ak+1,...,an$ лежат на отрезке $[k+1;n].$ Но на этом отрезке лишь $n− k$ чисел, значит, мы получили противоречие.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 9#126641

Дана фраза:

$□□□$ -гранная пирамида имеет:

1.: столько же вершин, сколько $□□□$ -гранная призма,
2.: столько же рёбер, сколько $□□□$ -гранная призма,
3.: и столько же граней, сколько $□□□$ -гранная призма.

Сколько способов вписать в каждый квадрат по цифре так, чтобы получить верное утверждение? Напомним, что натуральное число не может начинаться с нуля.

Источники: ФЕ - 2025, 10.3 ( см. www.formulo.org)

Показать ответ и решение

Заметим, что $n$ -гранная пирамида имеет $n$ вершин и $2(n− 1)$ ребер, а $n$ -гранная призма — $2(n− 2)$ вершины и $3(n− 2)$ ребра. Таким образом, если вместо пропусков подставить по порядку трёхзначные числа $x,y,z,w,$ то

( x =(2y− 2) |{ |( 2(x− 1)= 3(z− 2) x =w

Тогда

2(2(y− 2)− 1)= 3(z − 2)

4(y− 1)= 3z

Сделаем замену: $y =3k+ 1,$ $z = 4k,$ $x= w= 6k− 2,$ $k∈ℤ.$ Трехзначность исходных чисел выполняется при $33 ≤k ≤166.$ Получим $166− 33 +1 =134$ варианта.

Ответ:

$134$

Ошибка.
Попробуйте повторить позже

Задача 10#126991

На конференции по теории графов собралось много учёных. Они выяснили следующие вещи:

(1) У каждого из них ровно 81 знакомых на конференции.

(2) У любых двух знакомых ровно 60 общих знакомых на конференции.

(3) У любых двух незнакомых ровно 54 общих знакомых на конференции.

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

Источники: ИТМО - 2025, 10.7 ( см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1

Будем пытаться вычленить из имеющихся данных новые сведения о наших учёных, чего нам не хватает для ответа на вопрос задачи?

Подсказка 2

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

Подсказка 3

Итак, мы узнали сколько всего учёных, а сколько незнакомых для каждого из них присутствует на конференции?

Подсказка 4

Чтобы ответить на вопрос задачи достаточно рассмотреть два случая: когда напротив оказались двое знакомых и когда напротив оказались двое незнакомых людей. Сколько существует способов выбрать каждую из таких пар? А сколькими способами можно достроить каждый из случаев до нужной нам конфигурации?

Показать ответ и решение

Пусть у каждого из ученых ровно $a$ знакомых на конференции, у любых двух знакомых ровно $b$ общих знакомых,a у любых двух незнакомых ровно $c$ общих знакомых.

Найдём сначала общее количество учёных $n.$ Рассмотрим какого-то одного учёного. У него есть $a$ знакомых. У каждого из них также $a$ знакомых, но среди этих $a$ уже посчитаны $b$ общих знакомых с первым учёным и сам первый учёный. Остаётся ещё $a − b− 1$ знакомый у каждого, итого $a(a− b− 1).$ В это число вошли все незнакомые с первым учёным люди, причём каждый ровно $c$ раз благодаря третьему условию. Значит, всего получаем

a(a− b− 1) n= 1+ a+ ----c----

учёных. У каждого из них при этом ровно

d= a(a−-b−-1) c

незнакомых на конференции.

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

Рассмотрим два случая: первый человек выбирается $n$ способами. Незнакомого человека напротив можно выбрать $d$ способами. Тогда оставшиеся два выбираются $c(c− 1)$ способами так как мы знаем, сколько у первых двоих общих знакомых. Получаем

n⋅d⋅c(c− 1)

способов.

Во втором случае мы выбираем человека напротив из $a$ знакоммых первого человека, а дальше $b(b− 1)$ способами выбираем их общих знакомых. Получаем всего

n⋅a⋅b(b− 1)

способов.

Полученные два числа необходимо сложить для получения ответа.

При изначальных данных $a =81,$ $b= 60,$ $c=54$ получим, что $n= 112,$ $d= 30,$ первое и второе слагаемые равны соответственно $9616320,$ и $32114880$ . Их сумма равна $41731200.$

Ответ:

41731200

Ошибка.
Попробуйте повторить позже

Задача 11#36173

Сколько существует 5-значных чисел, в которых есть хотя бы одна цифра 5?

Подсказки к задаче

Подсказка 1

Подумаем, как же удобнее всего учитывать условие на 5? Удобно ли считать конкретно те способы, которые нам нужны, или можно поступить хитрее с помощью тех чисел, которые мы умеем искать?

Подсказка 2

Мы умеем искать количество всех пятизначных чисел, а еще умеем учитывать те числа, в которых нет пятёрки) Для этого просто исключим её из "возможных вариантов" для каждой позиции пятизначного числа! Осталось лишь понять, что же делать с полученными количествами)

Показать ответ и решение

В данном случае проще сначала посчитать количество пятизначных чисел, в записи которых нет цифры $5$ , а затем вычесть их из $90000$ , то есть количества пятизначных чисел.

Итак, считаем пятизначные числа, в которых нет $5$ . На первом месте может стоять любая из $8$ цифр (кроме $0$ и $5$ ), на втором, третьем, четвёртом и пятом местах — любая из $9$ цифр (кроме $5$ ). Так как цифры выбираются последовательно и выбор очередной цифры не зависит от выбора предыдущих, то эти способы перемножаются. Значит, всего есть $8⋅9⋅9⋅9⋅9= 52488$ пятизначных чисел без $5$ в записи. Тогда пятизначных чисел с цифрой $5$ в записи всего $90000 − 52488 =37512.$

Замечание. Если бы мы считали сразу количество чисел с цифрой $5$ , то у нас возникло бы две проблемы. Во-первых, пятерка может стоять на любом из $5$ мест, и все эти способы надо учесть. Во-вторых, пятерок может быть несколько, и такие числа, как, например, $53552$ мы можем посчитать несколько раз. Поэтому-то, чтобы решить эти две проблемы одним махом, мы считаем числа, в записи которых нет $5$ .

Ответ:

$9⋅104− 8⋅94 =37512$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#76651

Найдите количество функций $f :{1,2,3,4,5,6} → {1,2,3,4,5,6}$ для которых верно $f(f(f(x)))=x$ для всех $x∈ {1,2,3,4,5,6}$ .

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

Показать ответ и решение

Возьмем какое-нибудь число $a ∈{1,2,3,4,5,6}.$ Тогда возможны два варианта:

1. Если $f(a)= a,$ то и $f(f(f(a)))= a.$

2. Предположим $f(a)= b и b⁄= a.$ Тогда $f(b)= c, где c⁄= a,c⁄= b.$ Иначе
(а) Если $f(b)= a, то f(f(f(a)))= f(f(b)) =f(a)=b ⁄=a.$
(b) Если $f(b)= b, то f(f(f(a)))= f(f(b))= f(b) =b⁄= a.$
И так как $a =f(f(f(a)))= f(f(b))= f(c),$ то $f(c)=a.$

Таким образом, для любого $a∈ {1,2,3,4,5,6}$ либо $f(a)=a,$ либо есть три различных числа таких, что $f(a)= b,f(b) =c и f(c)= a.$

При этом любая функция с таким свойством подходит. Тогда найдем число функций с необходимым свойством.

1. Нет ни одной тройки элементов, что $f(a)= b,f(b)= c, и f(c)= a.$ Значит, для всех чисел $a∈{1,2,3,4,5,6}$ верно $f(a)= a.$ Такая функция одна.

2. Есть одна тройка элементов, что $f(a)= b,f(b)= c, и f(c)=a.$ Выбрать тройку можно $C36$ способами. При этом есть два способа задать функцию в тройке. Итого $2C36$ функций.

3. Есть две тройки элементов, что $f(a)= b,f(b)= c, и f(c)= a.$ Выбрать первую тройку можно $C36$ способами, остальные три элемента образуют вторую тройку. Но варианты, в которых выбрали в первую тройку $a,b,c$ и выбрали все кроме $a,b,c$ одинаковые. То есть $C36 :2$ способов разбить элементы на две тройки. При этом в каждой тройке есть два способа задать функцию. Итого $2⋅2⋅C36 :2 =2C36$ функций.

Всего число функций равно

1 +2C36 + 2C36 = 81

Ответ: 81

Ошибка.
Попробуйте повторить позже

Задача 13#80741

Есть $4n$ отрезков длины $x 1$ , $x 2$ , …, $x 4n$ , где $x = 1 1$ , $x =2 2$ , а при $k> 2$ выполнено $x = x + x k k−1 k−2$ . Сколькими способами эти отрезки можно разбить на четвёрки так, чтобы из отрезков каждой четвёрки можно было составить четырёхугольник?

Источники: Высшая проба - 2024, 11.4 (см. olymp.hse.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Да, из отрезком a < b < c < d можно составить четырёхугольник <=> a+b+c > d, попробуйте рассмотреть произвольную четвёрку, которая образует четырёхугольник и расписать свойство x_k = x_{k-1} + x_{k-2} более подробно, т.е. для x_{k-1} применить его же и посмотреть чему тогда должно быть равно c и b.

Подсказка 3

Верно, если d = x_{k}, то b = x_{k-2}, c = x_{k-1}, иначе четырёхугольник не построится. Теперь задача свелась к подсчету количества способов выбрать n пар из тройки элементов и одного элемента, который не превосходит по номеру элементы выбранной тройки.

Подсказка 4

Введем понятие "хорошей" последовательности, состоящей из 2n чисел, в которой каждое из чисел 1, ..., n участвует ровно два раза. Как мы можем восстановить способ разбиения последовательности отрезков по хорошей последовательности? Может мы можем первому вхождению числа в "хорошую" последовательность сопоставить число, а второму - тройку?

Подсказка 5

Теперь давайте подсчитаем количество хороших последовательностей. Сколькими способами можно выбрать индексы для двух единиц? А сколько тогда останется возможных индексов для двух двоек? А сколько всего получится способов сопоставить каждому числу 2 индекса?

Подсказка 6

А не посчитали ли мы что-либо несколько раз? Меняет ли перестановка чисел в "хорошей" последовательности набор отрезков?

Показать ответ и решение

Из отрезков $a< b< c< d$ можно сложить четырехугольник тогда и только тогда, когда $a+ b+ c> d$ . Рассмотрим четверку $xs < xi < xj < xk$ , заметим, что $xk =xk−1+ xk−2 = 2xk−2 +xk−3 > xk−2+xk−3+ xk−4$ , следовательно, $xj = xk−1$ , иначе проверяемое неравенство не выполнено. Аналогично, можно показать, что $xi =xk−2$ .

Назовем последовательность $4n {xi}i=1$ интересной. Таким образом, необходимо посчитать количество способов выбрать в интересной последовательности $n$ пар из тройки элементов и одного элемента, который не превосходит по номеру элементы выбранной тройки.

Рассмотрим последовательность, состоящую из $2n$ чисел, в котором каждое из чисел $1,...,n$ участвуют ровно два раза и назовем ее хорошей. Восстановим по хорошей последовательности способ разбиения интересной последовательности. На первом шаге рассмотрим первое число в каждой из последовательности. На каждом следующем шаге, если рассматриваемое число в хорошей последовательности встречается впервые, то ставим ему в соответствие рассматриваемое число в интересной последовательно, после чего рассматриваем следующий числа в каждой из последовательностей. Если рассматриваемое число в хорошей последовательности встречается во второй раз, то ставим ему в соответствие тройку из рассматриваемого элемента в интересной последовательности и двух элементов, идущих после него. Таким образом, к концу процесса, каждому первому вхождению числа в хорошей последовательности стоит в соответствие один элемент интересной последовательности, а каждому второму тройка подряд идущих элементов интересной последовательности.

Посчитаем количество хороших последовательностей. Существует $C22n$ способов выбрать индексы двум единичкам, после этого останется $2n− 2$ возможных индекса, следовательно, существует ровно $C22n−2$ способов выбрать индексы для двух двоек. Продолжая ставить каждому из чисел в соответствие два индекса, получим что общее количество способов сделать это, равно $(2n)!∕2n$ . Осталось заметить, что каждая перестановка чисел в хорошей последовательности не меняет набор разбиение интересной последовательности, следовательно, каждое разбиение было посчитано $n!$ раз (количество перестановок длины $n$ ), а значит общее количество разбиений равно

(2n)!= --(2n)!---= (2n− 1)!! 2nn! 2⋅4⋅...⋅2n

Ответ:

$(2n− 1)!!$

Ошибка.
Попробуйте повторить позже

Задача 14#82691

В азбуке Морзе любой символ (буква или цифра) зашифрован последовательностью точек и тире.

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

(b) А если использовать последовательность, содержащую не более пяти символов?

Показать ответ и решение

$(a)$ Каждый из 5 элементов последовательности точек и тире можно выбрать двумя способами, поэтому количество символов, которые можно закодировать, равно $5 2 ⋅2 ⋅2 ⋅2 ⋅2 =2 = 32.$

$(b)$ Символ может кодироваться последовательностью из одного, двух, трех, четырех или пяти элементов. В каждом случае ответ считается аналогично предыдущему пункту и равны соответственно $2 3 4 5 2,2 ,2 ,2,2 .$ Осталось сложить все эти числа: $2 3 4 5 2+ 2 + 2 +2 + 2 = 2+4 +8+ 16+ 32 =62.$

Ответ:

$(a) 32;$

$(b) 62.$

Ошибка.
Попробуйте повторить позже

Задача 15#82692

Будем называть номером последовательность из 6 цифр.

(a) Сколько всего существует различных номеров? А номеров, все цифры которых чётны?

(b) Сколько номеров, в которых любые две соседние цифры различны?

(d) Сколько номеров, все цифры которых имеют одинаковую четность?

(e) Сколько номеров, у которых есть хоть одна нечетная цифра?

(f) Сколько номеров, содержащих цифру 7 и не содержащих цифры 0?

Показать ответ и решение

(a) На каждую позицию номера можно выбрать одну из $10$ цифр, поэтому всего номеров $106.$ Так как четных цифр всего $5$ , то, выбирая на каждую позицию одну из пяти четных цифр, получаем, что номеров с четными цифрами всего $6 5 .$

(b) Пусть первая цифра выбирается произвольным образом - для нее есть $10$ вариантов. Тогда следующая цифра может быть выбрана девятью способами, так как нельзя использовать ту цифру, которая была выбрана первой. Аналогичными рассуждениями приходим к тому, что на каждой из позиций цифра может быть выбрана произвольным образом из некоторых девяти цифр. Тогда число номеров, в которых соседние цифры различны, равно $5 10×9 .$

(c) Первую цифру можно выбрать $10−$ ю способами. Вторую цифру - $9−$ ю, так как нельзя использовать цифру, стоящую на первом месте. Третья цифра может быть выбрана $8−$ ю способами, так как теперь не могут быть использованы цифры с первого и второго мест. Рассуждая аналогично, получаем, что для оставшихся мест имеется $7,$ $6$ и $5$ способов соответственно. Получаем, что искомое число равно $10× 9×8 ×7× 6× 5.$

(d) Выберем первую цифру произвольным образом (есть $10$ способов.) После того, как первая цифра была выбрана, была выбрана и четность оставшихся пяти цифр, и для каждой из них остается ровно $5$ вариантов выбора. Тогда количество номеров с четными или нечетными цифрами равно $10× 55.$

(e) Если из общего числа номеров вычесть число номеров, в которых все цифры четны, получим число номеров, в которых есть хотя бы одна нечетная цифра. Тогда число номеров с нечетной цифрой равно $106 − 56.$

f Вычтем из числа номеров, не содержащих $0$ , число номеров, не содержащих цифр $7$ и $0.$ Ясно, что это и будет искомым числом, так как тогда останутся номера, не содержащие $0,$ но в которых есть $7.$ Номеров без нулей всего $96,$ так как каждую цифру можно выбрать девятью способами. Число цифр, в которых нет еще и цифры $7$ равно $86,$ так как каждая из цифр может быть выбрана восьмью способами. Таким образом, искомое число номеров равно $96 − 86.$

Ответ:

$(a)$ $106,$ $56;$

$(b)$ $5 10⋅9;$

$(c)$ $151200;$

$(d)$ $5 10⋅5 ;$

$(e)$ $6 6 10 − 5;$

$(f)$ $6 6 9 − 8 .$

Ошибка.
Попробуйте повторить позже

Задача 16#82693

Сколько десятизначных чисел, в которых все цифры различны, и при этом цифры 4 и 5 стоят рядом?

Показать ответ и решение

Так как все 10 цифр различны, то надо использовать все 10 цифр. Так как 4 и 5 стоят рядом, будем воспринимать 45 или 54 как один знак, тогда остаётся 9-значное число. На первом месте не должен стоять 0, поэтому можно использовать 8 знаков. На вторую позицию остаётся любой из знаков, кроме того который уже использовали, то есть 8. На третью позицию 7 вариантов, далее 6 и так далее.

Получаем $8 ⋅8 ⋅7 ⋅...⋅2 ⋅1.$ Теперь учтём, что может быть 45, а может быть 54, для этого нужно количество способов умножить ещё на 2.

Ответ:

$16⋅8!$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#82694

Сколько существует пятизначных чисел, сумма цифр которых делится на 5?

Показать ответ и решение

Будем последовательно выбирать цифры от первого места к последнему.

На первом месте могла оказаться любая цифра, кроме $0.$ На втором, третьем и четвертом местах могла оказаться любая цифра. Осталось выбрать цифру на последнее место. Для этого рассмотрим, какие могли быть остатки у суммы первых четырех выбранных цифр. Обозначим этот остаток через $s,$ а последнюю цифру через $r.$

Если $s =0,$ то $r =0$ или $r= 5$
Если $s =1,$ то $r =4$ или $r= 9$
Если $s =2,$ то $r =3$ или $r= 8$
Если $s =3,$ то $r =2$ или $r= 7$
Если $s =4,$ то $r =1$ или $r= 6$

Заметим, что для каждого $s$ можно выбрать последнюю цифру двумя способами. Это значит, что последнюю цифру нашего числа можно выбрать двумя способами. Тогда количество чисел, сумма цифр которых делится на 5, равно

9× 10× 10 ×10× 2= 18000

Ответ: 18000

Ошибка.
Попробуйте повторить позже

Задача 18#82700

Человек-Паук и Человек-Муравей поспорили о том, кто из них раньше получит новый костюм. За костюмом выстроились $10$ мстителей, включая этих двоих. Известно, что в споре победил Человек-Паук. Сколько всего существует очередей, в которых побеждает Человек-Паук?

Показать ответ и решение

Рассмотрим любую очередь, в которой побеждает человек-паук. Тогда, поменяв местами человека-паука и человека-муравья, получим очередь, в которой победителем выходит человек-муравей. Получается, что все возможные очереди разбиваются на пары, в одной из которых побеждает человек паук, а в другой - человек-муравей. Значит, ровно половина всех очередей - те, в которых побеждает человек паук.

Всего возможных очередей имеется

10⋅9⋅...⋅2⋅1= 10!

Тогда победных очередей для человека-паука ровно $10!. 2$

Ответ:

$10! 2$

Ошибка.
Попробуйте повторить позже

Задача 19#82701

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

Показать ответ и решение

Будем выбирать 4 точки - вершины прямоугольника. Первую вершину можно выбрать произвольным образом в одном из узлов квадрата $10× 10,$ которых всего имеется $11⋅11= 121,$ так как в строке и в столбце по $11$ узлов. Далее выбираем точку в той же горизонтали одним из $10$ способов. После этого выбираем точку в той же вертикали, тоже одним из $10$ способов. Последняя вершина задается однозначно тремя предыдущими. Тогда получаем $121⋅10⋅11⋅1$ вариантов. Заметим, что каждый прямоугольник посчитан 4 раза, так как есть 4 способа выбрать первую вершину прямоугольника. Таким образом, всего прямоугольников

121⋅10⋅10⋅1:4= 3025

Ответ: 3025

Ошибка.
Попробуйте повторить позже

Задача 20#82778

Болельщики должны выбрать 6 лучших хоккеистов чемпионата: одного вратаря, двух защитников и трех нападающих. Среди претендентов: 2 вратаря, 5 защитников, 6 нападающих и 3 “универсала”. “Универсал” — игрок, хороший в разных ролях, который поэтому может быть выбран как в качестве защитника, так и в качестве нападающего (но не вратаря). Сколько существует способов выбрать эту шестёрку? Требуется получить числовое значение.

Источники: Ломоносов - 2024, 11.1 (см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Давайте сначала выберем вратаря, ведь место вратаря мажет занять только вратарь. Всего у нас два варианта на эту позицию. Обратите внимание, что защитников нужно выбрать только двое, и наша задача легко разбивается на три случая. Первый случай — это 0 универсалов среди защитников, второй — 1 универсал, третий — 2 универсала.

Подсказка 3

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

Показать ответ и решение

Начнём считать с вратарей. Место вратаря может занять только вратарь, поэтому у нас всегда всего 2 способа выбрать его.

Дальше рассмотрим три случая по количеству универсалов на месте защитников:

1. Среди выбранных защитников нет универсалов. Значит, количество так выбрать двух защитников в команду равно

2 5⋅4 C5 =-2- =10

На место нападающих в этом случае мы можем поставить либо нападающих, либо универсалов, следовательно, способов

C39 = 9⋅83⋅!7 =84

Следовательно, вариантов команд в этом случае

2⋅10 ⋅84= 1680

2. Среди выбранных защитников один универсал. Значит, количество так выбрать двух защитников в команду равно

5⋅3= 15

На место нападающих в этом случае мы можем поставить либо нападающих, либо оставшихся универсалов, следовательно, способов

C38 = 8⋅7⋅6 =56 3!

Следовательно, вариантов команд в этом случае

2⋅15 ⋅56= 1680

3. Среди выбранных защитников оба являются универсалами. Значит, количество так выбрать двух защитников в команду равно

C23 = 3

На место нападающих в этом случае мы можем поставить либо нападающих, либо оставшегося универсала, следовательно, способов

7⋅6⋅5 C37 =--3!- =35

Следовательно, вариантов команд в этом случае

2 ⋅3 ⋅35= 210

В итоге способов выбрать команду равно

1680+ 1680+ 210 =3570

Ответ: 3570

Следующая подтема