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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

121⋅10⋅10⋅1:4= 3025

Ответ: 3025

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

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

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

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

Болельщики должны выбрать 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

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

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

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

Источники: Росатом - 2024, московский вариант, 11.5, по мотивам 10.2 ММО - 2005 (см. olymp.mephi.ru)

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

Подсказка 1

Обратим внимание на степени переменных. Понятно, что при раскрытии скобок для каждого одночлена степень будет вида 17n+15m. Тогда найдём натуральные решения для 17n+15m=49

Подсказка 2

Правильно, единственное решение - (2;1). То есть при перемножении скобок мы 2 раза взяли х¹⁷ и 1 раз х¹⁵. Обратим внимание также, что в заданной скобке перед каждым одночленом коэффициент 1. Как тогда мы можем выразить коэффициент перед х⁴⁹?

Подсказка 3

Конечно, коэффициент перед х⁴⁹ равен количеству способов выбрать комбинацию из двух х¹⁷ и одного х¹⁵ в 6 скобках. Остаётся только это досчитать

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

Понимаем, что при раскрытии скобок степень каждого одночлена будет иметь вид $17n +15m,$ где $n$ — количество взятых $x17,m$ — количество взятых $15 x .$ Поэтому решим сначала уравнение в натуральных числах

17n +15m = 49

Нетрудно заметить решение $n= 2,m =1,$ а также что это решение единственное, т.к. иначе, чтобы сохранить нужные остатки, $x$ будет изменяться на кратное 15 число, а $y$ на кратное 17, поэтому одно из них станет отрицательным.

Осталось лишь посчитать количество способов выбрать комбинацию из двух $x17$ и одного $x15$ в 6 скобках:

2 1 6⋅5 C6 ⋅C 4 = 2 ⋅4= 60

Ответ: 60

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

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

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

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

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

Подсказка 1

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

Подсказка 2

Можно решить задачу, в которой каждая белка либо осталась на своем месте, либо перешла на соседнее. Задача стала проще, можно перебрать все случаи

Подсказка 3

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

Подсказка 4

Каждая пара может поменяться, а может остаться на месте. Но один случай мы уже учли. Тогда вариантов 7 + 7 (пары могут образоваться двумя способами). Какой еще случай мы не учли?

Подсказка 5

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

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

Любой рассадке вечером можно сопоставить рассадку, в которой белка, сидевшая на дереве с номером $x$ (нумерация по часовой стрелке), сидит на дереве $(x+ 3)$ по модулю 6 (то есть просто белку переместили на противоположное место). Нетрудно видеть, что это противоположное место является либо тем местом, на котором белка сидела утром, либо соседним с ним. Значит, можно решить задачу, в которой каждая белка либо осталась на своём месте, либо перешла на соседнее.

Пусть изначально белки сидели в порядке $ABCDEF$ . Рассмотрим случаи:

$1)$ Все остаются на своих местах. Тогда есть только один случай ( $ABCDEF$ ).

Если $A$ перемещается вправо на место $B$ , у $B$ есть два варианта действий. $B$ может переместиться влево(на место $A$ ) или переместиться вправо на место $C$ .

$2)$ Рассмотрим движение по кругу. Если $B$ перемещается на место $C$ , то единственный способ для $C$ — переход к $D$ , переход $D$ к $E$ , переход $E$ к $F$ и переход $F$ к $A$ , в результате чего достигается $F ABCDE$ . Каждый бельчонок может также двигаться влево( $BCDEF A$ ). Таким образом, тут два случая.

$3)$ Некоторые бельчата из соседних пар $AB$ , $CD$ , $EF$ меняются местами, оставаясь в той же паре. Если $A$ перемещается на место $B$ , $B$ перемещается на место $A$ . $C$ может остаться на месте, или переместиться на $D$ , $E$ может остаться на месте, или переместиться на $F$ . Это даёт $2⋅2⋅2= 8$ случаев, но бельчата не могут все оставаться на месте, поскольку мы уже посчитали такую возможность в случае $1$ , и, следовательно, здесь $7$ случаев. Кроме этого, могут быть пары $BC,DE,F A$ что даёт еще $7$ случаев.

$4)$ Меняются местами не в соседних парах, а в парах, разделённых одним бельчонком. Если бы $A$ и $B$ поменялись местами, $D$ и $E$ могли бы поменяться местами, и это не было бы учтено предыдущими группировками. При этом два бельчонка, разделяющие пары, сидят на прежних местах. Это может происходить в трёх случаях ( $A$ и $D$ не движутся, $B$ и $E$ не движутся, $C$ и $F$ не движутся).

Всего случаев $1 +2+ 7+ 7+ 3= 20$ .

Ответ: 20

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

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

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

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

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

Подсказка 1

А что если не было бы условия на два дня голодовки? Сколько способов было бы?

Подсказка 2

Нам нужно выбрать всего 4 дня из 10, а остальные будут обжорными. А как посчитать количество способов, которые не подходят под условие?

Подсказка 3

Нам нужно вычесть способы, в которых есть хотя бы 3 дня подряд голодовки. Много ли таких случаев?

Подсказка 4

Разберите случаи: когда у нас есть 3 дня подряд голодовки и 1, не стоящий рядом с ними. И второй случай: все 4 дня голодовки стоят рядом

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

Посчитаем сначала общее количество способов распределить дни без учёта условия. Заметим, что нам нужно выбрать 4 голодных дня, остальные сразу станут обжорными. Значит, их количество

4 10⋅9⋅8⋅7 C10 =---4!---= 210

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

1) У нас 3 голодных дня подряд и 1 голодный, не стоящий с ними рядом. Будем воспринимать эти 3 дня как 1, назовём его большой голодный день, т.е. теперь у нас будет 8 дней и мы распределяем большой голодный день и голодный день так, чтобы они не стояли рядом. Если большой голодный стоит первым или последним, то у обычного есть 6 вариантов, в иных случаях у него их 5. В итоге

2⋅6+ 6⋅5= 42

2) У нас 4 голодных дня подряд. Количество таких способов равно количеству способов выбрать место для первого голодного дня, оно равно 7.

В итоге количество способов распределения, подходящих под условия равно

210 − 42− 7= 161

Ответ: 161

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

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

Сколькими способами из множества ${1,2,3,...,2024}$ можно выбрать $n$ чисел так, чтобы сумма любых $m$ (произвольное натуральное число, меньшее $n$ ) из выбранных чисел не делилась на 3? Рассмотрите все возможные $n ≥ 2.$

Источники: Иннополис - 2024 (см. dovuz.innopolis.university)

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

Подсказка 1

Нужно рассмотреть все натуральные n>=2... как будто это очень много чисел.. Значит, нужно как-нибудь сузить круг поиска. Подумайте, может ли n быть больше трех?

Подсказка 2

Правда ли, что из любых трёх целых чисел найдётся несколько из них, сумма которых кратна трём?

Подсказка 3

Это действительно так! Получается n<=3, то есть нам нужно рассмотреть всего два варианта! Для подсчёта используйте число сочетаний и рассматривайте остатки при делении на 3.

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

Заметим, что из любых трёх целых чисел найдётся несколько из них, сумма которых кратна трём. (Ведь не может быть числа, кратного трём, и не могут быть одновременно числа с остатками $1$ и $2$ , а чисел одного остатка не более двух).

А значит, $n ≤3,$ при этом из условия нас интересуют $n≥ 2.$ В рассматриваемом множестве чисел по $675$ чисел, дающих остатки $1$ и $2$ при делении на $3.$

Тогда для $n= 3$ подходят любые три числа с одинаковыми остатками, их $3 2⋅C675.$ Для $n = 2$ любая пара чисел с ненулевыми остатками, то есть $2 2⋅C675$ пар чисел с одинаковыми остатками и $2 675$ с разными.

Итого $2 3 2 3 2 2 ⋅C 675+ 2⋅C675+ 675 =2 ⋅C 676+ 675 = 102971025$ чисел.

Ответ:

$2⋅C3 + 6752 = 102971025 676$

Курсы

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

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

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

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

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

Первой цифрой числа может быть любая из $1,2,...,9,$ потому что число не может начинаться с $0.$ Вторую цифру можно выбрать $9$ способами, так как всего цифр $10$ , при этом вторая цифра должна отличаться от соседней первой. Аналогично третью цифру можно выбрать $9$ способами, потом четвертую $9$ способами и так далее. Получаем ответ:

6 9⋅9⋅9⋅9⋅9⋅9= 9

Ответ:

$96$

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

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

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

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

Посчитаем количество всех шестизначных чисел: первую цифру можно выбрать любым из $9$ способов (любая кроме $0$ ), а последующие любым из $10.$ Всего шестизначных чисел:

5 9⋅10

Посчитаем количество шестизначных чисел, не содержащих “5”: первую цифру можно выбрать любым из $8$ способов (любая кроме $0,5$ ), а последующие любым из $9.$ Всего шестизначных чисел, не содержащих “5”:

8⋅95

Тогда чисел, содержащих в своей записи “5” будет:

9⋅105− 8 ⋅95 = 427608

Ответ:

$427608$

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

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

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

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

Число партий будет равно количеству способов выбрать неупорядоченную пару человек. Всего человек 20, поэтому количество способов выбрать пару с учётом порядка будет равна $20⋅19 =380.$ Чтобы убрать повторяющиеся пары, поделим это число на 2, в итоге получим $380∕2 =190$ способов.

Ответ:

190

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

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

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

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

Подсказка 1

Нам нужно посмотреть, сколько вариантов взять яблоко и апельсин у Нади в каждом случае. Тогда разберём их по отдельности. Пусть Ваня взял яблоко. Теперь у нас их 11 штук. Сколько тогда у Нади вариантов взять фрукты?

Подсказка 2

Верно! 11*10 = 110. Ведь для каждого из 11 способов выбрать яблоко у нас 10 способов выбрать апельсин. Теперь по аналогии выясните кол-во способов выбора у Нади в случае, когда Ваня взял апельсин.

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

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

1) Если Ваня взял яблоко, то в корзине осталось 11 яблок и 10 апельсинов. Получается, у Нади есть 11 способов выбрать яблоко и 10 способов выбрать апельсин, при этом на каждый из 11 способов выбрать яблоко есть 10 способов выбрать апельсин, то есть всего $11⋅10= 110$ спобов выбрать фрукты.

2) Если Ваня взял апельсин, то в корзине осталось 12 яблок и 9 апельсинов. Аналогично предыдущему случаю, воспользуемся правилом умножения и получим, что у Нади есть $12⋅9= 108$ способов выбрать апельсин и яблоко.

Поскольку $110> 108$ , Надя имеет большую свободу выбора, если Ваня взял яблоко.

Ответ: яблоко

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

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

Сколько существует 5-значных натуральных чисел, делящихся на $2$ и не содержащих в десятичной записи ни одной из цифр $3$ , $4$ , $5$ , $7$ и $9$ ?

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

Подсказка 1

Мы знаем, что наше число делится на 2. Тогда что можно сказать про последнюю цифру числа?

Подсказка 2

Точно! Это либо 0, либо 2, либо 6, либо 8. То есть для последней цифры у нас 4 варианта. Теперь подумайте, сколько же вариантов для цифр на остальных разрядах числа? Учтите: число не может начинаться с нуля!

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

Так как число чётное, то его последняя цифра чётная, то есть она может быть равна 0, 2, 6, 8 (в списке нет 4, так как по условию десятичная запись числа не содержит 4). Получается, существует 4 способа выбрать последнюю цифру.

Первой цифрой числа могут быть все цифры, кроме 0 и тех, что не содержатся в записи числа по условию, то есть это 1, 2, 6, 8. Получается, есть 4 способа выбрать первую цифру. А способов выбрать каждую из оставшихся цифр на один больше, так как они могут равняться и нулю.

Воспользуемся правилом умножения, чтобы посчитать общее количество чисел, так как цифры мы выбираем независимо друг от друга. Итак, искомых чисел $4⋅5⋅5⋅5⋅4= 2000.$

Ответ: 2000

Интенсивы

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

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

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

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

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

Подсказка 1

Сразу разберёмся с первой цифрой. Всего 9 способов выбрать её (не берём 0). Сколько тогда вариантов для второй цифры с учётом того, что цифры различны?

Подсказка 2

Верно! Тоже 9. Так как 0 мы уже поставить можем, а цифру, которая была на 1ой позиции не можем. А как же тогда будет меняться кол-во способов выбрать цифру на 3, 4, 5 позиции?

Подсказка 3

Точно! С каждым разом оно будет уменьшаться на 1. Теперь осталось воспользоваться правилом умножения.

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

Первой цифрой такого числа могут быть все цифры, кроме 0, то есть существует 9 способов её выбрать.

Способов выбрать вторую цифру так же 9, так как ей могут быть все цифры, кроме той, что была первой.

Третья цифра должна быть не равна первой и второй, поэтому способов выбрать ее уже 8. Аналогично, способов выбрать четвёртую цифру 7, пятую — 6, шестую — 5.

Так как цифры мы выбираем последовательно друг за другом, и количество способов выбрать следующую цифру не зависит от того, что именно мы выбрали ранее, то воспользуемся правилом умножения для подсчёта всех нужных чисел. Итак, искомых чисел $9⋅9⋅8⋅7⋅6⋅5= 136080.$

Ответ: 136080

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

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

Сколько существует 6-значных чисел, в которых есть цифра 7, но нет цифры 9?

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

Подсказка 1

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

Подсказка 2

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

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

Для начала подсчитаем количество шестизначных чисел, в которых нет цифры 9. Способов выбрать первую цифру такого числа восемь(все цифры, кроме 0 и 9), а способов выбрать каждую из остальных цифр — девять(без 9). Получается, всего этих чисел $5 8⋅9 .$

Теперь аналогично посчитаем количество шестизначных чисел, в которых нет 7 и нет 9. Способов выбрать первую цифру такого числа семь, а способов выбрать каждую из остальных цифр — восемь. Получается, всего этих чисел $5 7⋅8.$

Чтобы найти количество чисел, в которых есть хотя бы одна 7 и нет 9, нужно из чисел, в которых нет 9, вычесть числа, в которых нет ни одной 7 и нет 9. Получается, искомых чисел $5 5 8⋅9 − 7⋅8 =243016.$

Ответ: 243016

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

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

У одного школьника есть 6 книг по математике, а у другого — 8, все книги различны. Сколькими способами они могут обменять две книги одного на две книги другого?

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

Подсказка 1

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

Подсказка 2

Мы знаем, как посчитать количество способов выбрать 2 книги из 6 для первого школьника и количество способов выбрать 2 книги из 8 для второго школьника. Теперь нужно понять, как скомбинировать эти два числа. Зависит ли как-то выбор второго школьника от выбора первого и наоборот?

Подсказка 3

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

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

Давайте сначала выберем $2$ книги на обмен от первого школьника. Первую книгу мы можем выбрать $6$ способами, затем, для каждого такого выбора мы можем выбрать вторую $5$ способами. По правилу умножения получаем $6⋅5= 30$ способов, но при таком подсчёте мы посчитали каждую пару дважды, итого $15$ . Аналогично, есть $8⋅7 2 = 28$ способов выбрать $2$ книги на обмен второму школьнику. Для каждой из $15$ пар книг первого школьника есть $28$ пар второго школьника, по правилу произведения получим $15⋅28= 420.$

Ответ: 420

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

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

Петя хочет выписать в порядке возрастания $5$ различных двузначных чисел, делящихся на $3,$ в десятичной записи которых встречается каждая цифра от $0$ до $9$ (включительно). Сколькими способами он может осуществить свой план?

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

Подсказка 1

Ясно, что каждая цифра встречается ровно 1 раз. Попробуем объединять цифры в числа. Какие цифры можно объединять с какими?

Подсказка 2

Верно! Вместе с цифрами 1, 4, 7 можно поставить любую из цифр 2, 5, 8, а цифры 0, 3, 6, 9 должны стоять вместе в одном числе. Сколько способов составить числа из цифр 1, 2, 4, 5, 7, 8?

Подсказка 3

Конечно, 48! А сколько существует способов составить числа из цифр 0, 3, 6, 9?

Подсказка 4

Верно! Всего 6 способов. Заметим, что порядок при любом составлении двузначных чисел однозначен. Каково тогда требуемое число способов?

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

Заметим, что каждая цифра должна встречаться ровно $1$ раз. Заметим, что каждая из цифр $1,4,7$ должна стоять в одном числе с одной из цифр $2,5,8$ (следует из признака делимости на $3),$ а оставшиеся цифры $0,3,6,9$ должны стоять в одном числе друг с другом. Способов разбить на пары цифры $1,4,7$ и $2,5,8$ ровно $3!= 6,$ и в каждой паре цифры можно поставить в любом порядке. Итого $3 3!⋅2 =48$ способов. Оставшиеся $4$ цифры разбиваются на пары $3$ способами. В одной из пар будет число $0,$ оно обязано стоять в разряде единиц, так как все числа двузначные. То есть нам надо выбрать порядок только у одной пары. Итого $3⋅2= 6$ способов. То есть всего способов составить $5$ двузначных чисел $6⋅48 =288.$ Причем эти числа выстраиваются по возрастанию однозначно, то есть на ответ это не повлияет.

Ответ:

$288$

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

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

Сколькими способами можно в некоторые клетки доски $n× n$ положить по одной фишке, так, чтобы количества фишек в столбцах были равны $1,2,3,...,n$ (в некотором порядке) и количества фишек в строках были равны $1,2,3,...,n?$

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Так, например, можно любую доску свести к такой, в которой в первом столбце и первой строке по одной фишке, во втором столбце и второй строке по две и т.д. Такая существует единственная. Значит, количество возможных досок соответствует количеству перестановок строк и столбцов. Чему оно равно?

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

Заметим, что в любой искомой доске мы можем переставлять столбцы и строки, и нужное свойство доски от этого не поменяется. Значит, мы можем любую доску свести перестановками строк и столбцов к “красивой” доске, где в первой строке будет только одна фишка на первой клетке, на второй строке ровно $2$ фишки на первых $2$ клетках и т.д. (такая доска тоже удовлетворяет условию). Тогда любая искомая доска получается из “красивой” перестановкой строк и столбцов, причем единственной. Столбцы мы можем переставлять $n!$ способами, строки — $n!.$ Значит, всего возможных досок $n!⋅n!.$

Ответ:

$(n!)2$

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

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

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

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

Жук находится в левой нижней клетке квадрата $10× 10.$ За один ход он может перемещаться на одну клетку вверх, на одну клетку вниз или на одну клетку вправо. Запрещено посещать одну и ту же клетку дважды. Сколькими способами жук сможет добраться до правой верхней клетки квадрата?

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

Подсказка 1

Жук может перемещаться по строкам в любую сторону, а в столбцах только вправо. Можно ли тогда для некоторых столбцов или для некоторых строк зафиксировать какую-нибудь информацию, по которой путь можно восстановить однозначно?

Подсказка 2

Верно! Для каждого из первых 9 столбцов зафиксируем строку, в которую жук переходит. Тогда пусть восстанавливается однозначно. Чему равно количество путей?

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

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

Ответ:

$109$

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

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

Числа $1,2,3,...,N$ записываются в строчку в таком порядке, что если где-то (не на первом месте) записано число $i,$ то где-то слева от него встретится хотя бы одно из чисел $i+1$ и $i− 1.$ Сколькими способами это можно сделать?

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

Подсказка 1

Пусть на первом месте стоит число k. Что тогда можно сказать о порядке чисел меньших k относительно друг друга, а о порядке больших k?

Подсказка 2

Верно, числа меньшие k стоят в порядке убывания, а большие - в порядке возрастания. Давайте теперь придумаем, чему сопоставить расстановки, зная как они устроены.

Подсказка 3

Итак, перестановку в самом деле можно задать набором мест, которые будут занимать числа меньшие k. Так пройдясь по всем k, получаем, что искомое количество соответствует числу подмножеств из n-1 элементов(выбор произвольных мест помимо первого).

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

Пусть на первом месте стоит число $k.$ Заметим, что если $k >1,$ то числа $k− 1,k − 2,...,1$ стоят в нашей перестановке в порядке убывания (если двигаться слева направо). Действительно, по условию левее числа $1$ должно стоять $2,$ левее $2 − 1$ или $3,$ то есть $3,$ левее $3− 2$ или $4,$ то есть $4$ и т. д. Аналогично при $k< N$ числа $k +1,k+ 2,...,N$ стоят в порядке возрастания, так как левее $N$ должно быть $N − 1,$ левее $N − 1$ — число $N − 2$ и т. д. Следовательно, любая из рассматриваемых перестановок однозначно задаётся набором мест, занимаемых числами $1,2,...,k − 1$ (таких мест может вообще не быть, если $k= 1,$ то есть для перестановки $1,2,...,N).$ Количество этих наборов равно количеству подмножеств множества из $N − 1$ элемента — всех мест, кроме первого, то есть $N−1 2 .$ По числу элементов подмножества однозначно определяется число $k,$ стоящее на первом месте.

Ответ:

$2N−1$ способами

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

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

Назовем упорядоченную четвёрку целых чисел $(a,b,c,d)$ интересной, если верно, что $1≤ a< b<c <d ≤10$ и $a+ d> b+c.$ Сколько существует интересных упорядоченных четвёрок?

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

Подсказка 1

Заметим, что если в четверке (a, b, c, d) выполняется a + d > b + c, то в четверке (11-a, 11-b, 11-c, 11-d) это неравенство выполняется в другую сторону и наоборот. Как тогда найти количество нужных пар?

Подсказка 2

Верно! Нужно из количества всех четверок, вычесть количество тех четверок, у которых a + d = b + c и разделить получившееся число на 2. Как найти число четверок с равенством?

Подсказка 3

Точно! Сумма a + d является числом от 3 до 19. Можно посчитать для каждого числа количество разбиений в сумму двух натуральных чисел, меньших 11. Тогда легко посчитать общее количество.

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

Предположим, что для упорядоченной четвёрки $a< b< c< d$ верно, что $a +d> b+ c,$ тогда

(11− a)+ (11− d)< (11− b)+(11− c)

И наоборот, если $a+d <b +c,$ то

(11− a)+ (11− d)> (11− b)+(11− c)

То есть, упорядоченные четвёрки $a <b< c< d$ с условием $a+ d> b+ c$ находятся во взаимно-однозначном соответствии с упорядоченными четвёрками $a <b <c< d$ с условием $a+ d< b+ c.$ Посчитаем количество четвёрок со свойством $a+ d= b+ c.$ Заметим, что $(a +d)$ является целым числом из промежутка $[3,19].$ Для каждого числа из этого диапазона посчитаем количество разбиений числа в сумму двух различных натуральных слагаемых, меньших $11.$ Тогда всего таких четвёрок будет

2 2 2 2 2 2 2 2 2 2C1 + 2C2 + 2C3 + 2C 4 +C 5 + 2C4 +2C3 +2C2 + 2C1 = 2+ 6+ 12 +10+ 12+6 +2 =50

С другой стороны, количество всех четвёрок равно $C410 = 210.$ Тогда оставшиеся $210− 50 =160$ четвёрок бьются на пары, в каждой из которых нам подходит ровно одна четвёрка. Получаем ответ $160∕2= 80.$

Ответ:

$80$

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

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

Найдите коэффициенты, которые будут стоять при $x17$ и $x18$ после раскрытия скобок и приведения подобных членов в выражении $( 5 7)20 1+ x + x .$

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

После раскрытия скобок $x17$ можно получить только перемножением $x7⋅x5⋅x5 ⋅1 ⋅...⋅1.$ Значит, нужно посчитать количество способов выбрать $7 5 5 x ,x ,x$ из скобок, так как 1 из остальных скобок выбирается однозначно. Выбрать $7 x$ из 20 скобок можно 20 способами. Выбрать $5 x$ и $5 x$ из 19 скобок — $19⋅18 2$ способов. Тогда всего $19⋅18- 20⋅ 2 = 3420.$

Попробуем представить 18 в виде суммы из 5 и 7. Эта сумма не может содержать более трёх пятёрок $($ так как $5⋅4> 18)$ и более двух семёрок $($ так как $7 ⋅3 >18).$ После небольшого перебора выясняем, что 18 никак не представима в виде суммы из 5 и 7. Значит, после раскрытия скобок слагаемого $18 x$ не будет. Тогда коэффициент при $18 x$ будет равен 0.

Ответ:

3420 и 0

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