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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 41#94539Максимум баллов за задание: 7

(a) Найдите сумму коэффициентов выражения (после раскрытия скобочек и приведения подобных членов) $( 3)123 1− 3x +x .$

(b) А теперь найдите сумму коэффициентов при четных степенях $x.$

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

Пусть после раскрытия скобок получились коэффициенты $a,a ,...,a : 0 1 369$

3123 2 369 (1 − 3x+ x ) = a0 +a1x+ a2x +...+ a369x

(a) Подставим $x =1,$ получим сумму коэффициентов:

2 369 123 123 a0+ a1 ⋅1 +a2⋅1 + ...+a369⋅1 = (1 − 3+ 1) = (− 1) = −1.

(1)

(b) Подставим $x= −1:$

a0 − a1+ a2− ...+(−1)369⋅a369 = (1− 3⋅(−1)+ (−1)3)123 = 3123.

(2)

Тогда, если сложить (1) и (2) и потом поделить на 2, получится сумма коэффициентов при чётных степенях:

368 3123−-1 a0+ a2+...+a = 2

Ответ:

(a) $− 1$ ;

(b) $3123−1 2$

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

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

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

Задача 42#94540Максимум баллов за задание: 7

Найдите коэффициент при $x100$ в многочлене $(1+ x+ x2+...+x100)7.$

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

Воспользуемся методом шаров и перегородок. Представим число 100 как сумму 100 единиц. Эти единицы будут нашими шарами. Поскольку из каждой из 7 скобок можно выбрать $x$ любой степени от 0 до 100, перегородок будет 6, и расставлять их мы будем среди 106 мест. Следовательно, коэффициент при $100 x$ равен $6 C106.$

Ответ:

$C6 106$

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

Задача 43#94541Максимум баллов за задание: 7

Докажите, что в произведении

( 2 3 99 100)( 2 3 99 100) 1− x+ x − x +...− x +x 1 +x+ x + x +...+x + x

после раскрытия скобочек и приведения подобных членов не останется членов с нечетными степенями $x.$

Показать доказательство

Рассмотрим какое-то слагаемое нечётной степени после раскрытия скобок. Пусть это $±x2k+1.$ Рассмотрим, как оно могло получиться. Пусть из первой скобки мы выбрали $b a ⋅x ,$ где $a= ±1.$ Тогда из второй скобки мы должны выбрать $2k+1−b x .$ Однако из первой скобки ещё можно выбрать $2k+1−b − a⋅x$ $(− a$ потому что $b$ и $2k+ 1− b$ разной чётности) и из второй $b x$ . Но тогда в сумме слагаемые $b 2k+1−b a⋅x ⋅x$ и $2k+1−b b − a⋅x ⋅x$ дадут 0. Следовательно, все слагаемые с нечётными степенями разбиваются на пары с суммой 0. Таким образом, после раскрытия скобок останутся только слагаемые с чётными степенями.

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

Задача 44#94542Максимум баллов за задание: 7

В каком из выражений $(1+ x2− x3 +x4)100$ и $(1− x2+x3 +x4)100$ (после раскрытия скобочек и приведения подобных членов) коэффициент при $60 x$ будет больше?

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

Рассмотрим степень 60 при $x$ после раскрытия скобок в выражении $(1+ x2− x3+ x4)100.$ Пусть она набрана как $a 2b 3c 4d 1 ⋅(x) ⋅(−x )⋅(x) .$ Однако степени $x$ внутри $2 3 4 100 (1− x + x +x )$ такие же. Значит, здесь точно так же можно набрать $60 x :$ $a 2b 3c 4d 1 ⋅(−x )⋅(x )⋅(x) .$ Видна биекция между слагаемыми, и можно сравнить коэффициент при каждом из них. Запишем равенство для степеней:

60= 2b+ 3c+ 4d

Отсюда видно, что $c$ обязательно чётное, а $b$ может быть любым. Так как $c$ чётное, то $1a⋅(x2)b⋅(−x3)c⋅(x4)d = 1a⋅(x2)b⋅(x3)c⋅(x4)d.$ Следовательно, все коэффициенты при $x60$ в $(1+ x2− x3 +x4)100$ обязательно положительные, а в $(1− x2+x3+ x4)100$ точно есть отрицательные (пример хотя бы одного из них: $60= 2⋅1+ 3⋅2+4 ⋅13).$ Значит, коэффициент при $x60$ больше у $(1+ x2− x3+ x4)100.$

Ответ:

$(1+ x2− x3+ x4)100$

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

Задача 45#94901Максимум баллов за задание: 7

Найти коэффициент $a 74$ многочлена $P(x)= (1+x3+ x17)20$ , если бы он был приведен в форму суммы одночленов вида $k akx ,k = 0,1,2,...,340$ .

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

Подсказка 1

Каждый одночлен — произведение нескольких x³ и x¹⁷ с некоторым коэффициентом. Тогда любой одночлен имеет степень 17n + 3m, где n и m — количества выбранных из скобок соответствующих одночленов. Для начала стоит найти n и m!

Подсказка 2

Верно! Из уравнения 17n + 3m = 74 можно получить, что подходят пары (1,19) и (4,2). Тогда, чтобы найти коэффициент, надо найти количество способов выбрать соответствующее число одночленов x³ и x¹⁷ из 20 скобок!

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

Степень каждого одночлена после раскрытия скобок и привидения подобных слагаемых имеет вид $3n+17m,$ где $n,m ∈ ℕ 0$ — количество выбранных $3 x$ и $17 x$ из каждой скобки соответственно. Решим уравнение $3n +17m =74.$ Заметим, что $m ≤ 4$ и перебором найдем все решения. Тогда $m = 1,n= 19$ или $m = 4,n =2.$ Тогда коэффициент при $a74$ равен сумме количества способов выбрать из одной скобки $17 x$ и в $19$ скобках $3 x$ и количества способов из $4$ скобок выбрать $17 x ,$ из двух — $3 x,$ а из оставшихся — $1.$

C120⋅C1199 + C420⋅C216 = 581420

Ответ:

$581420$

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

Задача 46#94903Максимум баллов за задание: 7

Найдите количество способов расставить 4 одинаковые фигуры на шахматной доске размером $8× 8$ так, что три из них будут находиться либо на одной горизонтали, либо на одной вертикали, либо на одной из двух главных диагоналей.

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

Подсказка 1

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

Подсказка 2

Верно! Будем рассматривать два случая: либо 3 фигуры на одной линии — диагонали, горизонтали и вертикали, либо все 4 фигуры стоят на одной линии. Как посчитать количество способов во втором случае?

Подсказка 3

Всего у нас 18 доступных линий: диагоналей, горизонталей и вертикалей. Посчитаем нужное количество для одной линии. Тогда достаточно выбрать 4 клетки из 8 доступных. А как посчитать количество для одной линии во втором случае и как после этого получить общее количество?

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

Наша задача эквивалентна тому, чтобы найти число способов расставить три одинаковые фигуры на одной линии (диагонали, горизонтали, вертикали) и одну не на этой линии или расставить $4$ одинаковые фигуры на одной линии. Всего у нас $18$ различных линий. Число способов расставить фигуры на одну линию равно $3 1 4 C8 ⋅C56+ C8 = 3206.$ Тогда итоговый ответ равен $3206⋅18 =57708.$

Ответ:

$57708$

Курсы

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

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

Задача 47#97675Максимум баллов за задание: 7

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

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

Если первый мальчик достал карточку с номером $x$ , то, чтобы сумма на карточках была 46, второй мальчик должен достать карточку с номером $46− x.$ Значит, достаточно рассмотреть все возможные варианты $x$ для первого мальчика, так как карточка, которую должен достать второй мальчик, определяется однозначно. А если существует вариант, что второй мальчик достал карточку с номером $y,$ а первый — с номером $46− y,$ и такой случай ещё не рассмотрен, то это значит, что изначально мы рассмотрели не все возможные варианты для первого.

Пусть первый мальчик достал карточку $x,$ а второй — $46− x.$ В задаче $x$ может принимать любое значение от 1 до 31, но нужно проверить, для любого ли такого значения у второго мальчика найдётся карточка с номером $46− x.$ Если первый достал 1, то второй должен был выбрать карточку $46− 1 =45,$ но карточки с номером 45 нет, так как самый большой номер — 31. Тогда самая маленькая карточка, которую может использовать первый, — это $46 − 31= 15.$ Значит, для любой карточки с номером от 15 до 31 второй мальчик может положить свою карточку с таким номером, чтобы в сумме получилось 46. Карточек с номерами от 15 до 31 — 17 штук.

Следовательно, существует 17 способов, чтобы мальчики достали по одной карточке так, чтобы сумма на них была ровно 46.

Ответ: 17

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

Задача 48#98015Максимум баллов за задание: 7

Сколько в $2024$ году дат, где год делится и на день, и на месяц?

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

Число $2024$ делится на следующие числа:

1,2,4,8,11,22,23,44,46,88,92,184,253,506,1012,2024

Месяц — это число от $1$ до $12.$ Из всех этих чисел на $2024$ делятся только: $1,$ $2,$ $4,$ $8,$ $11.$

День — это число от $1$ до $29,$ $30,$ или $31$ в зависимости от месяца. Из всех этих чисел на $2024$ делятся только: $1,$ $2,$ $4,$ $8,$ $11,$ $22,$ $23.$

Тогда для каждого месяца есть по $7$ дней, для которых год делится и на день, и на месяц. Итого получаем $35$ вариантов.

Ответ: 35

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

Задача 49#102018Максимум баллов за задание: 7

Дан прямоугольник $2×n.$ Сколькими способами его можно разрезать на доминошки, состоящие из $2$ клеток?

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

Подсказка 1

Давайте предположим, что мы знаем, сколькими способами можно замостить прямоугольник 2×n. Можно ли зная это, вычислить число способ замещения прямоугольника 2×(n+1)?

Подсказка 2

Чтобы ответить на вопрос из подсказки 1, обратите внимание на крайний столбец прямоугольника 2×(n+1). Как эти клетки могут быть покрыты?

Подсказка 3

Правильно, либо одним прямоугольником, либо двумя. В первом случае остаётся пустой прямоугольник 2×n, а во втором 2×(n-1). Какой вывод можно сделать?

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

Обозначим за $A n$ количество способов разрезать прямоугольник $2× n$ на доминошки. Давайте по индукции докажем, что $A = F . n n+1$ Для $n= 1,2$ очевидно. Теперь переход. Посмотрим на левую верхнюю крайнею клетку прямоугольника $2 ×n.$ Ее содержит вертикальная или горизонтальная доминошка. Если доминошка вертикальная, то остается только разрезать прямоугольник $2×(n− 1),$ а по предположению способов это сделать равно $Fn.$ Если же доминошка будет горизонтальной, то и под ней должна быть горизонтальная, а значит, останется только разрезать прямоугольник $2× (n− 2),$ а опять же по предположению количество способов это сделать равно $Fn−1.$ Следовательно, количество способов разрезать $2×n$ равно $Fn−1+ Fn = Fn+1,$ что и требовалось.

Ответ:

$F n+1$ число Фибоначчи

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

Задача 50#102021Максимум баллов за задание: 7

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

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

Подсказка

Тут стоит ввести последовательность. Пусть X_n - количество растений в n-й день. Как тогда связано X_n с предыдущими членами?

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

Обозначим $X n$ — число растений на $n−$ й год. Ясно, что $X = 0 0$ и $X = 1. 1$ Для $n ≥2$ имеет место соотношение $X = X + 3X n n−1 n−2$ (три черенка от растений, который растут хотя бы $2$ года и все имеющиеся растений за прошлые года). Характеристическое уравнение линейного рекуррентного соотношения имеет вид $2 q − q− 3= 0,$ откуда $1±√13- q = 2 .$ Таким образом,

(1 − √13)n ( 1+ √13)n Xn =A ---2-- + B --2---

Из начальных условий $A +B = 0$ и $(1− √13)A+ (1 +√13)B =2.$ Поскольку $A= −B,$ то $− 2√13A = 2,$ то есть $A = −√1-. 13$ Итак,

1 ((1+ √13)n (1− √13)n) Xn = √13 ---2-- − ---2--

Подставлять сюда $7$ и считать, что получится, очень не хочется, так что удобнее получить ответ через рекурренту.

Ответ:

$97$

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

Задача 51#102023Максимум баллов за задание: 7

Обозначим через $A n$ количество несамопересекающихся ломаных из $n$ звеньев, начинающихся в точке $(0,0),$ каждое звено которых совпадает с одним из векторов $r= (1,0),$ $u =(0,1),$ $d= (0,−1).$ Выразите $An$ через $An−1$ и $An−2.$

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

Подсказка 1

Давайте рассмотрим ломаную из n звеньев и поймём, сколько ломаных с n+1 звеном можно получить. Если ломаная заканчивается звеном вверх или вниз, то две. Если звеном вперёд - то три.

Подсказка 2

Зная количество ломаных, оканчивающихся звеном вверх, вниз, вперёд, мы сможем найти связь между A_(n), A_(n-1), A_(n-2).

Подсказка 3

Тогда давайте введём вспомогательные поcледовательности R_(n) и U_(n), где первая - количество ломаных из n звеньев с последним звеном вверх (количество ломаных с последним звеном вниз такое же), вторая - с последним звеном вперёд. Поработайте с ними и A_(n).

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

Разобьём ломаные на три вида, обозначим их соответствующими буквами:

1.: $R n$ — количество ломаных из $n$ звеньев, в которых последний шаг направо.
2.: $Ln$ — количество ломаных из $n$ звеньев, в которых последний шаг налево.
3.: $Un$ — количество ломаных из $n$ звеньев, в которых последний шаг вверх.

В силу симметрии ясно, что $Ln = Rn.$ Также единственная возможность для самопересечения — это после шага направо пойти налево, поскольку мы не можем опуститься вниз. Тогда напишем рекуррентное соотношение:

Rn = Un−1+ Rn−1, Un = Un−1+ 2Rn−1

А поскольку $Ln = Rn$

An =Un +2Rn, Un+1 = An

Тогда

An = Un+ 2Rn = Un−1+ 2Rn−1+ 2(Un−1+ Rn−1)=

= 2An− 1+Un−1 =2An−1 +An−2

Получаем ответ $An =2An−1+ An−2.$

Ответ:

$A = 2A +A n n− 1 n− 2$

Интенсивы

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

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

Задача 52#102024Максимум баллов за задание: 7

Некоторые клетки доски $2× n$ красятся в красный цвет так, чтобы ни одна красная клетка не имела соседей по стороне того же цвета. Обозначим через $An$ количество таких раскрасок с четным числом красных клеток, через $Bn$ — с нечетным числом. Чему может быть равно $An − Bn?$

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

Подсказка 1

Глобально мы хотим выразить A_(n) через члены последовательностей A и B с меньшими индексами. Аналогично мы хотим поступить с B_(n) в надежде, что разность этих выражений будет красивым числом.

Подсказка 2

Как это сделать? Пусть закрашено четное число клеток. Давайте посмотрим на крайний столбец доски 2×n. Как выразить A_(n) через члены A и B с меньшими индексами, если клетки этого столбца не закрашены?

Подсказка 3

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

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

Разделим доски на два типа: обычные $F n$ — доски $2×n$ и $G n$ — доски $2× n$ с удаленной угловой клеткой. Дополнительно найдем $Cn$ и $Dn$ — количества правильных раскрасок $Gn$ в четное и нечетное число цветов. Клетки будем нумеровать буквой $a$ или $b,$ соответствующей строке и числами от $1$ до $n$ — столбцы. Множество таких раскрасок разбивается на три подмножества: $an$ закрашена, $bn$ закрашена и ни одна из клеток $an,$ $bn$ не закрашена. Если закрашена $an,$ то $an−1$ и $bn$ не закрашены. Среди остальных клеток правильным образом должно быть закрашено нечетное количество, таким образом, в первом и втором случаях число раскрасок равно $Dn−1.$ Если же обе клетки $an,bn$ не закрашены, то остальные должны быть раскрашены в четное количество, то есть в $An−1.$ Таким образом, $An =An −1+2Dn−1.$ Аналогично

Bn =Bn−1 +2Cn−1

Cn = An−1+ Dn−1

Dn = Bn−1+ Cn−1

Пусть $Pn = An− Bn$ и $Qn =Cn − Dn.$ Тогда $Pn = Pn−1− 2Qn−1,$ $Qn = Pn−1− Qn−1.$ Ясно, что $P1 = −1$ и $Q1 = 0.$ Находим последовательно первые несколько членов ${Pn}$ и ${Qn}:$ $(−1,−1,1,1,−1)$ и $(0,−1,0,1,0).$ Далее последовательности периодичны. Таким образом, $Pn ∈ {±1}.$

Ответ:

$±1$

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

Задача 53#102025Максимум баллов за задание: 7

Сколько имеется $2016$ -значных чисел, у которых все цифры принадлежат множеству ${1,2,3,4,5}$ и любые две соседние цифры отличаются на $1?$

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

Подсказка 1

Неочевидно, как сразу выразить интересующее нас количество рекуррентной формулой. Зато, если ввести свою переменную на каждый вариант последней цифры, несложно понять, что происходит при приписывании ещё одной цифры.

Подсказка 2

Полезно посмотреть на начало последовательностей. Это позволяет заметить, как выглядят числа на каждом чётном шаге рекурсии. Осталось только доказать предположение по индукции.

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

Разобьём числа на пять видов по последней цифре, обозначим их соответствующими символами:

1.: $Nn 1$ — количество чисел из $n$ знаков, которые кончаются на $1.$
2.: $n N 2$ — количество чисел из $n$ знаков, которые кончаются на $2.$
3.: $n N 3$ — количество чисел из $n$ знаков, которые кончаются на $3.$
4.: $n N 4$ — количество чисел из $n$ знаков, которые кончаются на $4.$
5.: $Nn5$ — количество чисел из $n$ знаков, которые кончаются на $5.$

Тогда напишем рекуррентные соотношения:

(|| Nn+1= Nn ||||| 1n+1 2n n ||{ N2 = N1 +N 3 || Nn3+1= Nn2 +Nn4 ||||| Nn4+1= Nn3 +Nn5 ||( Nn+1= Nn 5 4

Ясно, что $Nn = Nn 1 5$ и $Nn = Nn 2 4$ (например, можно построить биекцию, заменив $1$ на $5$ и $2$ на $4).$ Тогда давайте по индукции доказывать, что при $n= 2k$ — $Nn = Nn =3k−1 1 5$ и $Nn =Nn = Nn = 2⋅3k−1. 2 3 4$ База очевидна, двузначные числа $21,$ $12,$ $32,$ $23,$ $43,$ $34,$ $54,$ $45.$ Теперь переход с помощью рекурренты:

(||Nn+1 = 2⋅3k−1 ||||| 1n+1 k−1 |||||N 2 = 3⋅3 {Nn+31 = 4⋅3k−1 ||||Nn+12 = 3⋅3k−1 =3k |||||Nn+2 = 6⋅3k−1 =2 ⋅3k |||( 2n+1 k−1 k N 3 = 6⋅3 =2 ⋅3

Теперь у нас спрашивают про $n =2016= 1008⋅2.$ Получаем

(| 2016 1007 |||||N1 = 3 |||{N22016= 2⋅31007 |N23016= 2⋅31007 |||||N2016= 2⋅31007 |||( 42016 1007 N5 = 3

Значит, ответ $1007 8⋅3 .$

Ответ:

$8⋅31007$

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

Задача 54#102027Максимум баллов за задание: 7

Дима и Саша занимаются двумя на первый взгляд совершенно разными делами. У Димы есть фигура “хромой король” — она умеет ходить на 1 клетку вверх или вправо, а также на $1$ клетку по диагонали вправо-вверх. Пусть $A$ — количество путей хромого короля по доске $n ×n$ из левого нижнего угла в правый верхний, которые никогда не поднимаются выше главной диагонали.

А у Саши есть бумажный квадрат $n× n$ и резак, которым он может проводить горизонтальные или вертикальные разрезы “от края до края”. Саша отметил $n − 1$ узлов клеток, лежащих внутри квадрата на его главной диагонали, и каждый очередной разрез делает по одному из отмеченных узлов, по которому еще разрез не проводился (разрез проводится от края до края того куска бумаги, на котором расположен выбранный на данном ходу узел). Пусть $B$ — количество способов так разрезать квадрат (способы отличающиеся только порядком разрезов считаются одинаковыми). Докажите, что $A = B.$

На рисунках изображены примеры всевозможных способов при $n= 3.$

$PIC$

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

Подсказка 1

Тут не нужно в явном виде считать формулу n-го члена для каждой конструкции. Достаточно доказать, что количество способов описывается одинаковым рекуррентные соотношением, в котором первые члены равны.

Подсказка 2

В первом соотношении стоит ввести последовательность a_n - количество способов попасть в n-ю клетку на главной диагонали.

Подсказка 3

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

Показать доказательство

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

n∑−1 a1 =1, a2 =2, an =an−1+ akan− k k=1

Для хромого короля рассмотрим первый момент на пути (не считая стартовой клетки), когда он попал на главную диагональ. Если это произошло первым же ходом, то мы получаем $a n−1$ способов. Если нет, то первый ход был направо, и далее есть $n$ вариантов, в зависимости от того, в каком столбце впервые король попал на главную диагональ. Если он туда попал в $k+1$ по счету слева столбце, то сделал он это ходом вверх, и до этой клетки добраться было $ak$ способов. С этой клетки до правой-верхней есть $an−k$ способов добраться. Так и получается искомое рекуррентное соотношение.

Для разрезов пронумеруем отмеченные узлы слева направо от $1$ до $n − 1.$ Пусть $k$ -й узел это наименьший узел, по которому разрез проходит от края до края исходного квадрата. Не умаляя общности, он проходит по вертикали. Если этот разрез прошел по $1$ узлу, то остается $an−1$ способов проделать разрезы дальше. Если по $(n− 1)$ -му, то $an−1∕2$ способов (потому что направление следующего разреза предопределено, а значит, вдвое меньше количества всех возможных способов провести дальнейшие разрезы). Если же по какому-то промежуточному узлу $2 ≤k ≤n − 2,$ то есть $ak∕2$ способов провести разрезы слева и $an−k$ способов провести разрезы справа. Не забудем умножить итоговую сумму на $2,$ поскольку первый разрез можно было провести в любом из двух направлений, и получим следующее соотношение:

n−2 an = 2(an−1+ an−1∕2+ ∑ akan−k) k=2

что с учетом $a1 =1$ упрощается до искомого соотношения.

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

Задача 55#103200Максимум баллов за задание: 7

Сколько $n$ -буквенных слов ( $n$ — натуральное) можно составить из букв $a$ и $b$ так, чтобы после каждой буквы $a$ стояла хотя бы одна буква $b?$ (Букве $a$ разрешается быть последней).

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

Пусть подходящих слов длины $n− S . n$ Тогда рассмотрим последнюю букву в нашем слове. Если она $a,$ то перед ней обязательно $b,$ значит, слов, кончающихся на $a− Sn−2.$ Слов, кончающихся на $b− Sn−1.$ То есть $Sn = Sn−2+ Sn−1.$ Значит, наш ответ совпадает с числами Фибоначчи. Для $n= 1$ слова $2,$ для $n =2$ слова $3.$ Значит, ответ $Fn+2.$

Ответ:

$F n+2$

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

Задача 56#105468Максимум баллов за задание: 7

Назовем билет с номером от $000000$ до $999999$ отличным, если разность некоторых двух соседних цифр его номера равна $5.$ Найдите число отличных билетов.

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

Найдем число неотличных билетов. Заметим, что для любого числа от $0$ до $9$ существует ровно одно число из того же промежутка, модуль разности которого с исходным равен $5,$ назовем это число неподходящим для исходного.

На первом месте в десятичном представлении неотличного билета может стоять любая из $10$ цифр, на втором — любая, кроме неподходящей для первой, на третьем — любая, кроме неподходящей для второй. Таким образом, число неотличных билетов равно $5 10⋅9 .$

Наконец, поскольку общее число билетов равно $6 10 ,$ число отличных билетов равно

106− 10⋅95

Ответ:

$106− 10 ⋅95$

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

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

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

Задача 57#136036Максимум баллов за задание: 7

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

Источники: Всесиб - 2024, 10.4 (см. sesc.nsu.ru)

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

Подсказка 1

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

Подсказка 2

Тут мы выбираем не человека, а пару братьев, из которой кто-то войдёт в эту команду. Мы не просто берём четырёх человек сразу, а сначала определяемся с четырьмя парами братьев, из которых затем выберем представителей для команды. Сколько существует способов выбрать такие четыре пары из имеющихся шести?

Подсказка 3

Верно, это просто число сочетаний из 6 по 4! Теперь важно учесть, что для каждой пары есть два способа выбрать, какой именно брат войдет в состав команды. Сколько в таком случае способов собрать состав для первой команды?

Подсказка 4

Получается 15 ⋅ 2⁴ вариантов для первой команды. Осталось только аналогичным способом подобрать вторую команду из оставшихся ребят и не забыть учесть разбиения, которые мы посчитали несколько раз.

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

Для начала посчитаем количество способов собрать первую команду. Нам нужно выбрать 4 пары братьев из шести, а потом из каждой из выбранных пар выбрать брата, который войдёт в состав первой команды. Есть $4 C 6$ способа выбрать 4 пары братьев, и для каждой пары есть по 2 способа выбрать одного из двух братьев. Таким образом, способов собрать первую команду $4 4 C6 ⋅2 =240.$

Теперь посчитаем количество способов собрать вторую команду. В этой команде обязательно должно быть по одному из братьев из пар, которые не вошли в первую команду. Остальных двух человек мы выбираем из пар, где второй брат уже состоит в первой команде. В итоге получается $2 2⋅2⋅C4 =24$ сбособа.

В третью же команду попадают все оставшиеся ребята. При этом заметим, что мы несколько раз посчитали одни и те же разбиения на команды, только присвоили им разную нумерацию от 1 до 3. Это значит, что общее число способов нужно поделить на 3! Итак, искомое число способов равно:

240⋅24 --3!--= 960

Ответ: 960

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

Задача 58#137266Максимум баллов за задание: 7

На конкурсе сладкоежек 7 участников были награждены 20 одинаковыми пирожными и 2 одинаковыми тортами. Каждому досталась хотя бы одна сладость. Сколькими способами могли распределиться награды?

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

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

Подсказка 1

Нам нужно раздать пирожные и торты участникам. С чего выгоднее начать?

Подсказка 2

Верно, с тортов! Ведь их совсем мало, а значит, есть не так уж много вариантов выбрать тех, кому достанется торт! А сколько конкретно?

Подсказка 3

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

Подсказка 4

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

Подсказка 5

Вспомните задачку о шарах и перегородках!

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

Распределение делаем в два шага: сначала раздадим торты, а тем, кому их не досталось, выделим по пирожному; затем распределим среди всех оставшихся пирожные.

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

Случай 1. Оба торта достались одному участнику — $7$ вариантов. Остальным $6$ участникам надо выделить $6$ пирожных. Остаётся распределить $14$ пирожных среди всех $7$ участников — это равносильно расстановке $14$ шаров и $7− 1 =6$ перегородок, что даёт $6 6 C14+6 = C20$ способов. Итого получается $6 7C20$ способов.

Случай 2. Торты достались двум разным участникам — $2 C7$ вариантов. Остальным $5$ участникам надо выделить $5$ пирожных. Остаётся распределить $15$ пирожных среди всех $7$ участников — это можно сделать $6 6 C6+15 = C21$ способами. Всего в этом случае имеется $C27C621$ способов.

Ответ:

$C7 ⋅C6 + 7⋅C6 2 21 20$

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

Задача 59#137271Максимум баллов за задание: 7

Найдите количество строк из 6 натуральных чисел, произведение которых равно 6!.

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

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

Подсказка 1

Разложите 6! на простые множители. Поймите, какой вид имеет каждое число в строке.

Подсказка 2

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

Подсказка 3

Воспользуйтесь методом шаров и перегородок.

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

Разложим $6!$ на простые множители:

4 2 1 6!= 2 ⋅3 ⋅5

Значит, каждое число в строке имеет вид

2a⋅3b⋅5c

Cтроку можно закодировать тройками показателей, первая состоит из 6 показателей степени у двойки с суммой 4, вторая — у тройки с суммой 2, третья — у пятёрки с суммой 1. Методом шаров и перегородок находим, что троек первого вида $C44+5,$ второго — $C22+5,$ третьего — $C11+5.$ Тогда количество строк равно

C44+5 ⋅C22+5 ⋅C11+5 =15876

Ответ:

$C4 ⋅C2 ⋅C1= 15876 9 7 6$

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

Задача 60#60907Максимум баллов за задание: 7

По кругу отмечены 10 точек. Сколько существует замкнутых 10-звенных (возможно, самопересекающихся) ломаных с вершинами в этих точках?

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

Пронумеруем точки по кругу. Будем последовательно выбирать номера точек для вершин ломаной, на выбор которых нет ограничений. Получим всевозможные наборы из $10$ различных чисел, например, ${3,1,2,6,5,8,7,4,10,9}$ . Всего таких наборов $10!$ как количество способов поставить $10$ элементов на $10$ позиций.

По условию ломаная замкнутая, так что все наборы разбиваются на десятки, получаемые при её обходе, начиная с каждой из десяти вершин (например, $1→ 2 → ...→ 9→ 10 → 1$ ). В итоге получаем $10!∕10 =9!$ различных ломаных.

Но нужно заметить, что ломаная симметричная и все наборы разбиваются на пары, получаемые при её обратном обходе (то есть в рассмотренном примере если мы выберем вершины $1→ 10→ 9 → ...→ 2→ 1$ , то получим ту же самую ломаную!). Поэтому нужно наш результат ещё поделить на $2,$ чтобы исключить повторы.

Замечание.

Эта задача про известный факт, что различных простых циклов на $k$ вершинах имеется $(k− 1)!∕2.$

Ответ:

$9!∕2$ (это равно $181440$ )

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