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

Количество способов, исходов, слагаемых → .01 Правила сложения и умножения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В лагере «Школково» в одной комнате живут пятеро: Крош, Ёжик, Бараш, Лосяш и Пин. Каждый день они выбирают одного смешарика для патрулирования территории. Им нужно составить график патрулирования на $5$ дней. Сколько можно составить графиков, в которых никто не будет патрулировать территорию дважды, и при этом Крош дежурит не после Ёжика?

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

Заметим, что все графики, то есть $120$ штук (их количество мы посчитали в первой задаче), можно разбить на две группы: те, в которых Крош дежурит после Ёжика, и те, в которых Крош не дежурит после Ёжика. В предыдущей задаче мы посчитали, что графиков, в которых Крош дежурит после Ёжика, $4!= 24$ штуки. Значит, графиков, в которых Крош не дежурит после Ёжика, $120− 24= 96$ штук.

Ответ: 96

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

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

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

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

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

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

Будем последовательно выбирать состояние для лампочек. Для каждой лампочки по условию есть два состояния: горит либо не горит. Выбор очередного состояния не зависит от того, что было выбрано ранее. Поэтому работает правило умножения, так как выбор последовательный и независимый. Получается $2⋅2⋅2⋅2⋅2⋅2=64$ сигнала.

Ответ: 2^6 = 64

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

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

У Кроша и Ёжика есть $8$ различных конфет. Они собираются поделить их между собой. Сколькими способами можно это сделать?

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

Посмотрим на задачу с точки зрения конфеты. У нее возможны две судьбы: либо достаться Крошу, либо достаться Ёжику. И так для каждой конфеты. Выложим конфеты в ряд и для каждой будем двумя способами определять, кому из смешариков достанется очередная конфета. Заметим, что выбор судьбы для очередной конфеты не зависит от того, как мы распределили предыдущие конфеты. Значит, работает правило умножения, так как выбор последовательный и независимый. Поэтому эти восемь двоек надо перемножить. Получается

2⋅2⋅2⋅2⋅2⋅2⋅2⋅2= 28 = 256 способов.

Ответ: 2^8 = 256

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

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

У Тора и Локи есть $8$ различных конфет. Они собираются поделить их между собой. Сколькими способами можно это сделать?

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

Подсказка 1

В задаче нам мало чего дано. Двое богов просто хотят поделить между собой конфеты. Не сказано даже о том, сколько и кому должно достаться конфет. А давайте, пусть, для нашего удобства они сами будут брать себе конфеты. Будем просто "наблюдать", сколькими способами они могут расхватать себе конфеты. Что тогда будет происходить с одной конфетой?

Подсказка 2

Верно, она окажется либо у Тора, либо у Локи. Выходит, что у конфеты только 2 варианта. А связаны ли выборы конфет между собой?

Подсказка 3

Конечно, нет. Например, если Тор взял какую-то конфету, то это никак не помешает Локи взять другую. Тогда по правилу умножения осталось перемножить все варианты для конфет.

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

Посмотрим на задачу с точки зрения конфеты. У нее возможны две судьбы: либо достаться Тору, либо достаться Локи. И так для каждой конфеты. Выложим конфеты в ряд и для каждой будем двумя способами определять, кому из асгардцев достанется очередная конфета. Заметим, что выбор судьбы для очередной конфеты не зависит от того, как мы распределили предыдущие конфеты. Значит, работает правило умножения, так как выбор последовательный и независимый. Поэтому эти восемь двоек надо перемножить. Получается

2⋅2⋅2⋅2⋅2⋅2⋅2⋅2= 28 = 256 способов.

Замечание. Другим способом про это мыслить является выбор подмножества конфет для Тора — он однозначно задаёт конфеты Локи. Тогда количество способов будет равно числу различных подмножеств набора из $8$ элементов, то есть $28$ .

Ответ:

$256$

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

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

У Тора и Локи есть $8$ различных конфет. Они собираются поделить их между собой. На этот раз они хотят поделить их так, чтобы каждому досталась хотя бы одна конфета. Сколькими способами можно это сделать?

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

Подсказка 1

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

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

2⋅2⋅2⋅2⋅2⋅2⋅2⋅2= 28 = 256 способов.

Теперь нам надо исключить способы, в которых все конфеты достались только кому-то одному. Этих способов всего два: один, когда все конфеты достаются Тору, и второй, когда все конфеты достаются Локи (что соответствует пустому и “полному” множествам из замечания). Значит, нам надо из $256$ вычесть $2$ способа. Получается $256− 2= 254$ способа.

Ответ:

$254$

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

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

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

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

Среди цифр от $1$ до $9$ лишь одно делится на $5$ , следовательно, чтобы произведение трёх чисел на одной строке/столбце делилось на $50,$ необходимо, чтобы два из них были $5$ -ками, а третье число должно быть чётным.

Нам достаточно теперь разместить чётные числа, на остальные места поставим пятёрки.

Способов выбрать место для чётных цифры $3⋅2⋅1$ , так как мы сначала ставим чётную цифру на любую из трёх клеток первой строки, потом в остальных строках мы не можем ставить чётную цифру в этот же столбец, поэтому во второй строке уже есть только два способа, а в третьей остаётся один.

На каждое из этих трёх мест мы можем поставить одну из четырёх чётных цифр, то есть в на каждое место $3 4$ варианта.

Итого $3 6 ⋅4 =384$ способа.

Ответ:

384

Курсы

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

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

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

В магазине “Канцтовары” продаются 5 видов фломастеров, 3 вида ручек и 4 вида карандашей. Известно, что один из фломастеров, одна из ручек и один из карандашей изготовлены фирмой “Паркер”. Сколькими способами можно купить набор “Фломастер + ручка + карандаш”, в котором:

(a) нет предметов фирмы “Паркер”?

(b) 1 предмет фирмы “Паркер”?

(d) 3 предмета фирмы “Паркер”?

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

(a) Нам нужно выбрать набор из 3 предметов, в котором нет ничего от фирмы “Паркер”. Тогда фломастер можно выбрать любой из 4, так как мы исключаем один фломастер от фирмы “Паркер”. Аналогично выбрать ручку есть 2 варианта, а карандаш — 3. Тут соблюдаются все условия для правила умножения: мы выбираем несколько объектов последовательно, количество способов выбрать следующий объект не зависит от того, что было выбрано ранее. Тогда получим $4⋅2⋅3= 24$ способа выбрать все три предмета.

(b) Нам нужно, чтобы 1 предмет был фирмы “Паркер”. Тогда возможны три варианта, это может быть: 1) фломастер; 2) ручка; 3) карандаш. Посчитаем каждый случай отдельно. Если фломастер фирмы “Паркер”: выбираем несколько объектов последовательно. Соблюдаются все условия для правила умножения: мы выбираем несколько объектов последовательно, количество способов выбрать следующий объект не зависит от того, что было выбрано ранее. Тогда получаем: 1) если фломастер: $1⋅2⋅3= 6$ способов выбрать все три предмета;

2) если ручка: $4⋅1⋅3= 12$ способов выбрать все три предмета

3) если карандаш: $4⋅2⋅1= 8$ способов.

Мы разобрали три разных случая того, что можно выбрать. Чтобы найти общее количество способов, всё складываем. Получим $6+ 12+ 8= 26$ способов.

(c) Нам нужно, чтобы 2 предмета были фирмы “Паркер”. Тогда возможны случаи: 1) фломастер и ручка фирмы “Паркер”; 2) ручка и карандаш фирмы “Паркер”; 3) фломастер и карандаш фирмы “Паркер”. Воспользуемся правилом умножения, чтобы подсчитать количество способов для каждого случая, поскольку выбираем несколько объектов последовательно, при этом количество способов выбрать следующий объект не зависит от того, что было выбрано ранее.

1) фломастер и ручка фирмы “Паркер”: $1⋅1⋅3= 3$ способа;

2) ручка и карандаш фирмы “Паркер”: $4⋅1⋅1= 4$ способа;

3) фломастер и карандаш фирмы “Паркер”: $1⋅2⋅1= 2$ способа.

Мы разобрали три разных случая того, что можно выбрать. Найдём общее количество способов, всё складываем. Получим $3+ 4+2 =9$ способов.

(d) Нам нужно, чтобы все три предмета были фирмы “Паркер”, поэтому возможен только один случай. Тогда выбрать фломастер мы можем только 1 способом. Аналогично выбрать ручку у нас есть 1 способ и карандаш — 1 способ. Так как выбор последовательный, воспользуемся правилом умножения и получим $1⋅1⋅1= 1$ способ.

Ответ:

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

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

Имеется куб размером $10 ×10× 10,$ состоящий из маленьких единичных кубиков. В центре $O$ одного из угловых кубиков сидит кузнечик. Он может прыгать в центр кубика, имеющего общую грань с тем, в котором кузнечик находится в данный момент, причём так, чтобы расстояние до точки $O$ увеличивалось. Сколькими способами кузнечик может допрыгать до кубика, противоположного исходному?

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

Кузнечик должен совершить всего 27 прыжков – по 9 в каждом направлении. Обозначим направления буквами A, B и C. Каждый путь однозначно определяется последовательностью длины 27, в которой буквы A, B и C встречаются по 9 раз.

Ответ:

$-27! (9!)3$

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

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

У Васи имеются:

$1)2$ различных тома из собрания сочинений А. С. Пушкина; высота каждого тома — $30$ см;

$2)$ собрание сочинений Е. В. Тарле в $4$ -х томах; высота каждого тома — $25$ см;

$3)$ книга лирических стихов высотой $40$ см, опубликованных самим Васей.

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

Источники: СПБГУ-22, 9 (см. olympiada.spbu.ru)

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

Подсказка 1

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

Подсказка 2

Нет, не может! Поскольку высота томов Пушкина и Тарле различна, для двух томов Пушкина, стоящих по одну сторону от тома Васи, не найдется книги, которая смогла бы дополнить их по условию симметричности. Пронумеруем позиции, на которые будут расставлены книги от 1 до 7. На 4 позиции всегда стоит том Васи. А на каких позициях могут стоять тома Пушкина?

Подсказка 3

Все верно! На 1 и 7, 2 и 6 или 3 и 5 позициях, и для каждого выбора этих двух позиций есть два способа расставить на них тома Пушкина. На остальных позициях располагаются тома Тарле. Сколько способов имеется для расстановки томов Тарле?

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

Из условия симметричности расстановки вытекают два вывода:

1) слева и справа от стихов Васи должны стоять один том Пушкина и два тома Тарле;

2) для томов Пушкина допустимы 3 пары позиций: $(1,7),(2,6),(3,5).$ Остальные свободные места должны занимать книги Тарле.

Расставить тома Пушкина на выбранных для них позициях можно $2!$ способами. После этого книги Тарле на оставшихся местах независимо расставляются $4!$ способами.

Таким образом, окончательное количество расстановок равно $3⋅2!⋅4!= 6⋅24= 144.$

Ответ: 144

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

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

На клетчатой доске размера $25× 22$ (длина стороны клетки равна 1) требуется отметить тройку клеток так, чтобы центры этих клеток образовывали прямоугольный треугольник с катетами длины 7 и 4 (катеты параллельны краям доски). Сколькими способами это можно сделать?

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

Посчитаем количество треугольников, в которых угол направлен влево-вниз.

Тогда если вертикальная сторона 7, а горизонтальная 4, то для прямого угла $18 ⋅18$ вариантов, а остальные вершины восстанавливаются соответственно.

Тогда если вертикальная сторона 4, а горизонтальная 7, то для прямого угла $21 ⋅15$ вариантов, а остальные вершины восстанавливаются соответственно.

В итоге ответ $4(18 ⋅18+ 21⋅15)$ (для всех вариантов ориентации прямого угла).

Ответ:

$4(18 ⋅18+ 21⋅15)$

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

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

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

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

Для верхней полоски есть 1 вариант, а для каждой следующей 2 варианта. Значит всего $25$ .

Ответ: 32

Интенсивы

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

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

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

Сколькими способами клетки таблицы $4×6$ можно заполнить нулями и единицами так, чтобы сумма чисел в каждой строке и каждом столбце была четной?

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

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

Сейчас в каждом столбце и в каждой строке, кроме верхней сумма четная. Значит, во всей таблице сумма четная и поэтому в верхней строке сумма четная.

Это значит, что по всей таблице кроме верхней строки и правого столбца однозначно определяется вся таблица.

Ответ: 15

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

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

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

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

Заметим, что ровно одна цифра из десяти не входит в каждое число. Поскольку все подходящие числа делятся на 90, то они делятся на 10, а значит, они оканчиваются на 0. Также заметим, что сумма всех десяти цифр равна 45, и сумма цифр каждого из наших чисел должна делиться на 9, поэтому отсутствовать должна цифра 9. Любое число, состоящее из оставшихся цифр, с цифрой 0 в конце нам подходит. Таких чисел $1⋅2⋅...⋅8.$

Ответ: 8!

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

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

Сколькими способами можно раскрасить клетки прямоугольника $2× 2n$ в $5$ цветов так, чтобы любые две соседние по стороне клетки были разного цвета?

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

Подсказка 1

Начнём последовательно по столбам красить прямоугольник. Раскрасить левый столбец из двух клеток в различные цвета 5×4=20. Тогда далее разберём два случая: в следующем столбце верхняя клетка по цвету совпадает с нижней и верхняя клетка в следующем столбце по цвету не совпадает с нижней. Сколько способов покрасить второй столбец в таких случае?

Подсказка 2

В первом случае 4, во втором 3×3, итого, покрасить второй столбец 4+9=13 способов. А что дальше со следующим столбцом?

Подсказка 3

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

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

Пусть у нас имеются $5$ цветов ${a,b,c,d,e}.$ Первый столбик из $2$ клеточек мы можем покрасить $20$ способами (первую клетку красим в любой из $5$ цветов, вторую — в любой из оставшихся $4).$ Пусть, не умаляя общности, предыдущий столбик раскрашен в цвета $(a,b).$ Тогда следующий столбик мы можем покрасить в любую из $13$ следующих комбинаций: $(b,a),$ $(b,c),$ $(b,d),$ $(b,e),$ $(c,a),$ $(d,a),$ $(e,a),$ $(c,d),$ $(c,e),$ $(d,e),$ $(d,c),$ $(e,c),$ $(e,d).$ Это означает, что всего способов раскрасить прямоугольник $2 ×2n$ — $2n−1 20⋅13 .$

Ответ:

$20⋅132n−1$

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

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

По окружности выписано $100$ целых чисел, сумма которых равна $1$ . Цепочкой назовем несколько чисел (возможно, одно), стоящих подряд. Найдите количество цепочек, сумма чисел в которых положительна.

Источники: Муницип - 2021, Ямало-Ненецкий автономный округ, 8.6

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

Подсказка 1

Понятно, что как-то явно посчитать количество нужных цепочек мы не сможем. Поэтому идея такая: давайте попробуем каждой цепочке с положительной суммой сопоставлять цепочку, сумма чисел которой не положительна!

Подсказка 2

Такс, подумаем какие цепочки мы можем сопоставлять друг другу. Пусть есть какая-то цепочка, сумма которой положительна! Что можно сказать про цепочку, которая дополняет первую до всей окружности? То есть, в этих двух цепочках есть все 100 чисел и они не пересекаются.

Подсказка 3

Верно, такая цепочка не может иметь положительную сумму! Иначе сумма всех чисел была бы хотя бы 2. Таким образом, мы научились любой цепочке с положительной суммой находить пару в виде дополняющей её цепочки, причем сумма второй цепочки не больше нуля! Остаётся правильно посчитать число нужных нам цепочек и не забыть про цепочку, которая является нашей окружностью из 100 чисел.

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

Разобьем все цепочки (кроме цепочки, состоящей из всех чисел) на пары дополняющих друг друга. Если сумма чисел в одной из цепочек пары равна $s$ , а во второй равна $t$ , то $s+t= 1$ . Поскольку числа $s$ и $t$ целые, то положительным из них является ровно одно. Значит, ровно половина всех цепочек имеет положительную сумму. Всего цепочек $100⋅99$ (две дополняющие друг друга цепочки определяются выбором двух мест между ними). Это дает нам $4950$ цепочек с положительной суммой. Добавим к ним еще цепочку из всех чисел.

Ответ: 4951

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

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

У Васи имеются 9 разных книг Аркадия и Бориса Стругацких, содержащих по одному произведению писателей каждая. Вася хочет расставить эти книги на полке так, чтобы рядом стояли:

a) романы “Жук в муравейнике” и “Волны гасят ветер” (неважно, в каком порядке);

б) повести “Беспокойство” и “Повесть о дружбе и недружбе” (неважно, в каком порядке).

Сколькими способами Вася может это сделать?

Источники: СПБГУ-21, 9 (см. olympiada.spbu.ru)

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

Васе нужно расположить в ряд $7$ объектов: $5$ книг, не указанных в пунктах а) и б), и двух пар из а) и б). Это можно сделать $7!$ способами. Кроме того, внутри каждой пары можно менять книги местами, что увеличивает общее число вариантов в 4 раза. В итоге получаем $4⋅7!$ способов.

Ответ:

$4⋅7!$

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

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

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

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

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

Один из возможных вариантов ключа:


1	1	2	2

2	1	1	2

0	0	1	2

0	1	2	0

А сколько всего существует различных ключей?

Источники: Верченко - 2021, 11.3 (см. v-olymp.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Конечно, противоречия могут быть. Поэтому надо добавить еще два линейных равенства на диагонали. А значит, у нас есть 9 переменных и два равенства. Отсюда 7 свободных переменных, а потому вариантов 3⁷.

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

Указанную в условии таблицу $4 ×4$ , можно построить следующим образом: положим элементы верхнего левого угла размеров $3× 3$ произвольным образом, после чего заметим, что все оставшиеся элементы определяются однозначно из линейных (по модулю $3$ ) соотношений для строк и столбцов (при этом элемент в правом нижнем углу будет равен сумме по модулю $3$ всех остальных элементов квадрата). Плюс к этому имеем два линейных соотношения для элементов диагоналей. Таким образом, общее число независимого выбора переменных $ai,j,i,j = 1,2,3$ равно $7.$ Следовательно, общее число ключей равно $7 3 = 2187.$

Ответ:

$2187$

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

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

Палиндром — это слово, которое не меняется, если в нём переставить буквы в обратном порядке, например $abcba$ . Сколько различных $11$ -буквенных слов можно составить из букв $a,b,c,d,e$ так, чтобы они не содержали палиндромов длины больше $1?$

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

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

Подсказка 1

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

Подсказка 2

Это значит, что не должно быть палиндрома длины 2 и длины 3. Ну отсутствие палиндрома длины 3, равносильно тому, что у нас буквы через 1 не совпадают. А отсутствие длины два, значит, что не совпадают соседние. Какое тогда условие равносильно отсутствию палиндромов длины 2 и 3?

Подсказка 3

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

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

Заметим, что две центральные буквы любого палиндрома чётной длины одинаковы, то есть образуют палиндром длины два. Точно так же три центральные буквы палиндрома нечётной длины образуют палиндромы длины три. Таким образом, отсутствие в слове палиндромов равносильно отсутствию палиндромов длины $2$ и $3.$ Это, в свою очередь, равносильно тому, что любые три подряд идущие буквы в слове различны.

Первая буква в слове выбирается пятью способами, для следующей остаётся $4$ способа. Каждая из последующих букв не может совпадать с двумя предыдущими, поэтому для неё остаётся $3$ способа. Все эти числа надо перемножить, поэтому мы получаем

5(5 − 1)(5 − 2)11−2 = 393600

Ответ:

$393660$

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

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

Найдите количество способов раскрасить все натуральные числа от 1 до 20 в синий и красный цвета так, чтобы оба цвета встречались и произведение всех красных чисел было взаимно просто с произведением всех синих чисел.

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

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

Подсказка 1

Что можно сказать про числа из нашего набора, имеющие общий простой множитель?

Подсказка 2

Верно, они должны быть покрашены в один цвет! Тогда подумаем про раскраску чётных чисел.

Подсказка 3

Да, они будут одного цвета! Но тогда в эту же группу попадут числа, имеющие общий простой множитель с кем-то из чётных. Что это за числа?

Подсказка 4

Это числа, кратные трём, пяти, семи. Осталось совсем немного чисел, и теперь нужно понять, как будут раскрашены они:)

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

Заметим, что все чётные числа должны быть одного цвета. Так как среди них содержатся числа 6, 10 и 14, то числа, кратные 3, 5 и 7 должны быть того же цвета. Остались числа $1,11,13,17$ и 19. Заметим, что их можно распределить как угодно по двум цветам. Таким образом, у нас есть 6 групп, каждая из которых может быть любого цвета, т. е. всего $6 2$ способов раскраски. Заметим, что из них не подходят 2 варианта, в которых все числа одного цвета, Итого получается $6 2 − 2 =62$ способа.

Ответ: 62

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

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

Сколькими разными способами можно в таблице $2 ×7$ расставить натуральные числа от 1 до 14 (все по одному разу) так, чтобы сумма чисел в каждом из семи столбцов была нечётна?

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

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

Подсказка 1

Какие должны быть два числа, чтобы их сумма была нечетной? Очевидно, одно - четным, другое - нечетным. Кстати, у нас всего 7 четных и 7 нечетных чисел. Сколько способов выбрать, какое по четности число будет в верхней клетке столбцов?

Подсказка 2

Конечно, выбираем из четного или нечетного числа - 2 способа заполнить столбец, но для каждой расстановки в первом столбце подходят все расстановки остальных столбцов, значит, применяем правило умножения и получаем коэффициент 2⁷. Теперь подумаем, сколько способов есть расставить все четные числа в одном из 2⁷ возможных вариантов по четности/нечетности.

Подсказка 3

7 чисел на 7 мест, причём важен порядок -> получили 7! способов. Но не кажется ли вам, что столько же способов и для нечетных чисел, ибо логика действий сохраняется и для них. А еще для каждой расстановки четных чисел подходят все расстановки нечетных чисел, следовательно, 7! возведётся в квадрат. Вспоминаем про коэффициент из 2 подсказки и получаем ответ.

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

В каждом столбце стоит одно чётное и одно нечётное число. Где стоит чётное число, а где нечётное, выбирается двумя способами, итого $27$ способов для всей таблицы. Далее, существует $7!$ способов расставить чётные числа по выбранных для них местам и столько же способов расставить нечётные. Итого $7 2 2 ⋅(7!)$ способов.

Ответ:

$27⋅(7!)2$

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