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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Числа $1,2,3,...,101$ записывают в строку в некотором порядке. Назовем порядок хорошим, если можно вычеркнуть одно число так, что остальные числа будут идти строго по возрастанию. Сколько существует разных хороших порядков?

Источники: Лига открытий - 2018

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

Первое решение. Нетрудно видеть, что хороший порядок получается перестановкой одного числа из набора $1,2,3,...,101$ на какое-то место (возможно, то же самое), ведь при удалении этой переставленной цифры получим порядок по возрастанию. Если же переставлено хотя бы два числа, то после удаления одна из них нарушает порядок.

Итак, каждое из чисел можно сдвинуть с его позиции на любую из $100$ оставшихся, в итоге получаем $101⋅100$ способов.

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

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

Окончательно получаем $100⋅101− 100+ 1=100001.$

______________________________________________________________________________________________________________________________________________________

Второе решение. Подходят исходная расстановка и любая строка, полученная переносом любого числа с исходного места на любое другое. При этом перенос на соседнее место равносилен обмену местами двух соседей, то есть, может быть получен двумя способами; каждый из остальных переносов дает уникальную строку. На не соседнее место можно переставить 99 способами крайние числа 1 и 101 и 98 способами каждое из 99 остальных чисел. Учитывая, что есть 100 пар соседей, всего получаем хороших порядков $1+ 100+2 ⋅99+ 99⋅98= 10001$ .

Ответ:

$10001$

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

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

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

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

Найдите количество различных приведённых квадратных трёхчленов (т.е. со старшим коэффициентом, равным $1$ ) с целыми коэффициентами таких, что они имеют два различных корня, являющиеся степенями числа $7$ с целыми неотрицательными показателями, и при этом их коэффициенты по модулю не превосходят $36 343 .$

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

Подсказка 1

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

Подсказка 2

То есть наш многочлен в общем виде представляется как (x-7^a)(x-7^b), где a, b ≥ — целые. Какие тогда коэффициенты у нашего многочлена?

Подсказка 3

По теореме Виета: коэффициент при x = -7^a-7^b, свободный коэффициент = 7^(a+b). Теперь вспомните условие на коэффициенты. Что мы получаем?

Подсказка 4

Верно! Получаем, что 7^a + 7^b ≤ 7¹⁰⁸ , а также a + b ≤ 108. Не умоляя общности, будем считать, что a > b (a, b — различные по условию). Как связаны эти два неравенства?

Подсказка 5

Осознайте, что если выполняется второе, то первое тоже за исключением случая (a, b) = (108, 0). Что же осталось сделать?

Подсказка 6

Аккуратно посчитать случаи. Для каждого a отдельно разберитесь с b-шками, не забывайте, что a > b и a + b ≤ 108. Уверены, у вас всё получится! Успехов!

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

Такие квадратные трёхчлены можно представить в виде $(x− 7a)(x− 7b),$ где $a ≥0,$ $b≥ 0$ — целые числа. Чтобы исключить повторения, считаем, что $a >b.$ Раскрывая скобки, получаем $2 (a b) a+b x − 7 +7 x+ 7 .$ По условию

{ 7a+ 7b ≤34336, { 7a+ 7b ≤ 7108 a+b 36 ⇔ 7 ≤ 343 a +b≤ 108

Заметим, что если выполняется второе неравенство, то первое неравенство верно за исключением одного случая $a= 108,b= 0.$ Для каждого значения $a$ выпишем количество подходящих значений $b$ :

a= 108 ⇒ 0 значений b a= 107 ⇒ 2 значения b(0;1); a= 106⇒ 3 значения b(0;1;2);

$...............$

a =55⇒ 54 значения b(0;1;...;53); a =54⇒ 54 значения b(0;1;...;53); a =53⇒ 53 значения b(0;1;...;52); a =52⇒ 52 значения b(0;1;...;51); ............................ a = 1⇒ 1 значение b(0); a =0 ⇒ 0 значений b.

Суммируя, получаем $(2 +3+ 4+ ...54)+(54+53+ 52+ ...+1)= 2969$ вариантов

Ответ:

$2969$

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

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

Даны $6000$ карточек, на которых написаны натуральные числа от $1$ до $6000$ (на каждой карточке написано ровно одно число, притом числа не повторяются). Требуется выбрать две карточки, для которых сумма написанных на них чисел делится на $100.$ Сколькими способами это можно сделать?

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

Подсказка 1

Посмотрим на все эти числа по модулю 100 - тогда останется по 60 карточек каждого остатка по модулю 100. Как можно получить 0? Например, 0+0. Или 50+50. Посчитаем сначала количество таких вариантов по отдельности: сначала 0+0, а затем 50+50.

Подсказка 2

Количество вариантов для 0 и для 50 будет одинаково: это С₆₀² (берем две любые карточки из 60). Как еще получить 0? 1+99 = 2 + 98 и тд - все это будет равно нулю по модулю 100, что нам и надо. Посчитаем ситуацию 1+99: для каждой карточки 1 подходит каждая карточка 99, их по 60 штук, следовательно вариантов здесь 60². Причём здесь посчитаны и варианты 99+1.

Подсказка 3

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

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

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

$1)$ Номер на карточке оканчивается на $00$ (таких карточек $60$ штук). Для делимости суммы на $100$ вторую карточку надо выбрать так, чтобы номер на ней также оканчивался на $00.$ Всего получаем $2 60⋅59 C60 = 2 = 1770$ вариантов.

$2)$ Аналогично, если номер на карточке оканчивается на $50$ (таких карточек также $60$ штук), то для делимости суммы на $100$ вторую карточку надо выбрать так, чтобы номер на ней оканчивался на $50,$ т.е. и здесь $1770$ вариантов.

$3)$ Номер на карточке оканчивается на число от $1$ до $49$ (таких карточек $49⋅60= 2940$ ). Для каждой из них пару можно выбрать $60$ способами (если число оканчивается на $1,$ то подойдёт любая карточка с числом, оканчивающимся на $99;$ если число оканчивается на $2$ — любая карточка с числом, оканчивающимся на $98$ и т.д.). Таким образом, получаем $2940⋅60= 176400$ вариантов.

$4)$ Номер на карточке оканчивается на число от $51$ до $99.$ Все такие варианты были учтены при рассмотрении третьего случая (эти карточки составляли пару карточкам, выбранным первоначально).

Итого выходит $1770+1770+ 176400= 179940$ способов.

Ответ:

$179940$

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

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

Найдите количество различных приведённых квадратных трёхчленов (т.е. со старшим коэффициентом, равным 1) с целыми коэффициентами таких, что они имеют хотя бы один корень, все их корни являются степенями числа 3 с целыми неотрицательными показателями, и при этом их коэффициенты по модулю не превосходят $47 27 .$

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

Подсказка 1

Давайте запишем наши корни в виде 3^а и 3^b (чтобы исключить повторения, считаем, что а ≥ b), как в этом случае мы можем записать коэффициенты уравнения?

Подсказка 2

По теореме Виета мы можем выразить коэффициенты уравнения через корни и записать ограничения на них, что мы теперь можем сказать о наших степенях?

Подсказка 3

Так как коэффициенты по условию не превосходят 27⁴⁷, получаем a + b ≤ 141. Теперь мы можем просто перебрать все возможные варианты и получить ответ!

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

Такие квадратные трёхчлены можно представить в виде $(x− 3a)(x− 3b)$ , где $a ≥0$ , $b≥ 0$ — целые числа. Чтобы исключить повторения, считаем, что $a ≥b$ . Раскрывая скобки, получаем $2 (a b) a+b x − 3 +3 x+ 3$ . По условию

{ 3a+3b ≤ 2747 a+b 47 3 ≤27

{ 3a+ 3b ≤3141 a+ b≤141

Заметим, что если выполняется второе неравенство, то первое неравенство верно за исключением одного случая $a= 141,b= 0$ . Для каждого значения $a$ выпишем количество подходящих значений $b$ :

$a= 141⇒ 0$ значений $b$ ;

$a= 140⇒ 2$ значения $b(b∈{0;1})$ ;

$a= 139⇒ 3$ значения $b(b∈{0;1;2})$ ;

$a= 71 ⇒ 71$ значение $b(b∈ {0;1;...;70})$ ;

$a= 70 ⇒ 71$ значение $b(b∈ {0;1;...;70})$ ;

$a= 69 ⇒ 70$ значений $b(b∈{0;1;...;69})$ ;

$a= 68 ⇒ 69$ значений $b(b∈{0;1;...;68})$ ;

$a= 1⇒ 2$ значения $b(b∈ {0;1})$ ;

$a= 0⇒ 1$ значение $b(b= 0).$

Суммируя, получаем $(2 +3+ 4+ ...71)+(71+70+ 69+ ...+1)= 5111$ вариантов.

Ответ: 5111

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

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

Заведующая библиотекой, увидев, что $10$ томов “Малой энциклопедии козлов” стоят в беспорядке, указала на это библиотекарю. Тот в ответ заявил: “Беспорядок — небольшой; хотя ни один из томов не стоит на своем месте, но для каждого тома или его номер делится на номер места, или его место делится на номер тома.”. Сколькими способами можно расставить тома энциклопедии в соответствии с этим условием?

Источники: Лига открытий - 2018

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

Том “ $7$ ” может стоять только на позиции “ $1$ ”. А на позиции “ $7$ ” только том “ $1$ ”. Аналогично на пары разбиваются тома $5$ и $10,9$ и $3,$ потом $6$ и $2,$ и остаются тома $4$ и $8.$ Таким образом, расстановка восстанавливается однозначно.

Ответ:

Одним

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

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

Дано число $5300...0035$ ( $100$ нулей). Требуется заменить некоторые два нуля на ненулевые цифры так, чтобы после замены получилось число, делящееся на $495$ . Сколькими способами это можно сделать?

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

Подсказка 1

Так как мы рассматриваем делимость на 495, посмотрим сначала его разложение на простые множители, 495=5*11*9. Наше же число уже оканчивается на 5, поэтому осталось проконтролировать делимость на 9 и 11. Если с делимостью на 9 всё относительно просто, то вот с 11 посложнее, потому что делимость зависит от чётности. Тогда какие два случая резонно рассмотреть, чтобы проконтролировать это?

Подсказка 2

Верно, можно рассмотреть случаи, когда мы меняем 0 на позиции одной чётности и на разных. Так будет намного удобнее, и, конечно, они не пересекаются между собой. Посмотрим сначала первый случай. Что тогда можно сказать про позиции 5 и 3 и сумму цифр числа? Как они влияют на делимость на 9 и 11?

Подсказка 3

Верно, 5 и 3 находятся на позициях с разной чётностью, а значит никак не влияют на делимость на 11. То есть мы должны менять нули на цифры с суммой 11. А что с делимостью на 9? С ней всё ок, так как 5+5+3+3+11=27. Осталось только найти количество способов выбрать позиции одной чётности и умножить на количество представлений числа 11. Теперь что можно сразу сказать про второй случай, зная информацию из этой подсказки?

Подсказка 4

Ага, раз теперь позиции разной чётности, то и разность должна делится на 11. Другими словами цифры должны быть равны(цифры не превышают 9). А что с делимостью на 9? Наша сумма равна 16+2х, где х – это цифра, на которую поменяли нули. Посмотрите, чему может равняться х, и аналогично найдите количество способов выбрать две позиции разной чётности без учёта порядка.

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

Поскольку $495 =5 ⋅9⋅11$ , а данное в условии число уже оканчивается на $5$ , то достаточно добиться делимости на $11$ и на $9$ . Рассмотрим два случая:

Пусть мы меняем нули на позициях одной чётности. Тогда сумма поставленных нами ненулевых цифр точно не меньше $2$ и не больше $18$ , а при этом должна быть кратна $11$ , поскольку остальные цифры в знакопеременную сумму дают $0$ . Отсюда сумма поставленных нами цифр в точности должна быть равна $11$ , причём тогда сумма всех цифр будет равна $11+ 5+ 3+3 +5 =27$ и кратна $9$ . Тогда и число будет делиться на $9$ . Способов выбрать две позиции одной чётности с учётом порядка (потому что мы будем ставить разные цифры, ведь $11$ не делится пополам, а при постановке разных цифр нам уже важно, в каком они стоят порядке: получаются разные числа) будет $100 ⋅49$ (первая позиция любая, а вторая из оставшихся позиций той же чётности номера), умножая это на количество разбиений числа $11$ в сумму двух цифр уже без учёта порядка ( $11= 2+ 9= 3+ 8=4 +7 =5+ 6$ ), имеем $4⋅100⋅49$ способов.
Теперь рассмотрим позиции разной чётности. Теперь из признака делимости на $11$ поставленные нами две цифры должны быть равны (чтобы знакочередующаяся сумма цифр давала ноль и делилась на $11$ ), а сумма цифр полученного числа будет равна $16+ 2k$ , где $k ∈[1,9]∩ℕ$ , и должна делиться на $9$ , отсюда подойдёт только $k= 1$ . Осталось выбрать две позиции разной чётности без учёта порядка (ведь мы ставим одинаковые цифры и числа получаются одинаковые, хоть мы поставим $k...k$ , хоть $k...k$ ) $100 ⋅50∕2= 502$ способами (первая позиция любая, а вторая любая из позиций с номерами другой чётности).

В качестве ответа имеем $502+ 400 ⋅49 =22100$ .

Ответ:

$22100$

Курсы

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

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

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

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

Источники: ПВГ-2017, 6.5 (см. pvg.mk.ru)

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

Подсказка 1

Посмотрим внимательно на картинку. Понятно, что раз обводили только по линиям сетки, то и треугольники будут с гипотенузой на нашей исходной и с углом 45 градусов. Теперь подумаем, а как тогда задаются такие треугольники?

Подсказка 2

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

Подсказка 3

Верно, единичных отрезков будет 7, длины 2 – 6 и так далее, осталось только сложить их.

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

Заметим, что треугольники здесь будут только прямоугольные с углом $45∘$ . Кроме того, их гипотенуза лежит на гипотенузе изначального треугольника, поскольку все остальные отрезки проходят только по линиям сетки. Заметим также, что положением гипотенузы задаётся весь треугольник, потому достаточно посчитать количество различных отрезков с концами в целых точках на отрезке длины $7$ (так получится, если уменьшить всю гипотенузу в $√- 2$ раз). Длины $1$ отрезков будет $7$ , длины $2$ — $6$ ,.. длины $7$ — $1$ . Итого имеем $7+ 6+ ...+ 1= 28$ различных треугольников.

Ответ:

$28$

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

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

Код сейфа состоит из пяти идущих подряд цифр. Василий Петрович положил деньги в сейф, а когда захотел их забрать, выяснилось, что он забыл код. Он только помнил, что в коде были числа 21 и 16. Какое наименьшее количество пятизначных номеров необходимо перебрать, чтобы наверняка открыть сейф?

Источники: Миссия выполнима 2016

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

Подсказка 1

Так, нам надо посчитать, сколько всего вариантов кода. Что делать с тем условием, что у нас есть числа 21 и 16? Хочется понять, как они вообще могут быть расположены в коде друг относительно друга.

Подсказка 2

Ага, есть 3 варианта взаимного расположения чисел 21 и 16… Осталось только посчитать, сколько способов заполнить остальные места в коде!

Подсказка 3

И не забыть, что что-то мы случайно могли посчитать дважды!

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

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

1) Код содержит комбинацию цифр $216$ . Ее можно расположить в коде тремя способами: $∗∗216$ , $∗216∗$ или $216∗∗$ . В каждом из этих возможных кодов каждую из остальных цифр можно выбрать $10$ способами. Таким образом, получается $3⋅100 =300$ вариантов.

2) Код содержит комбинации $21$ и $16$ , причем комбинация $21$ расположена левее. Тогда оставшуюся цифру можно выбрать $10$ способами и поставить ее на одно из трех мест: перед $21$ , между $21$ и $16$ , после $16$ . То есть $30$ вариантов.

3) Код содержит комбинации $21$ и $16$ , причем комбинация $21$ расположена правее. Аналогично - $30$ вариантов. Заметим, что числа $21616$ , $21621$ , $21216$ , $16216$ мы посчитали дважды. Таким образом, чтобы открыть сейф достаточно перебрать $300 +30+ 30− 4 =356$ номеров.

Ответ: 356

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

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

Рассматриваются всевозможные пятизначные числа, в которых цифры $9,7,3,1,0$ используются ровно по одному разу. Найдите среднее арифметическое этих чисел.

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

Подсказка 1

Что мы имеем? На первое место можем поставить 4 из 5 цифр, на остальные все 5. Как-то несимметрично, да ещё и сумму нам считать надо. Как же нам побороть эту несимметричность?...

Подсказка 2

Например, давайте сначала забудем, что 0 в начале стоять не может и будем считать, что для первой цифры всё также 5 вариантов. Как в этом случае посчитать сумму всех чисел?

Подсказка 3

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

Подсказка 4

Сходу неочевидно, однако попробуйте считать по-умному. Посчитайте, сколько раз встречается в этой сумму цифра 1 или другая (неважно).

Подсказка 5

Напомним про красивое число 1*2*3*4 (оно вам пригодится). Самостоятельно осознайте, что каждое цифра в разряде единиц встречается 24 раза. Тогда сумма цифр в разряде единиц = (0 + 1 + 3 + 7 + 9)*24 = 20*24. Что же дальше?

Подсказка 6

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

Подсказка 7

Бинго! 1111*20*24. Осталось отдельно посчитать числа, где в начале 0 и вычесть из уже посчитанного. Уверены, вы справитесь! Успехов!

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

Сначала проигнорируем то, что 0 не может быть первым. Тогда для каждого разряда сумма различных цифр в нём $1+ 3+7 +9+ 0= 20$ , при фиксированной цифре на любой позиции число способов поставить остальные — $4!= 24$ , откуда сумма таких чисел равна $24⋅20⋅11111$ . Затем поставим 0 на первое место, а остальные 4 цифры образуют 4-хзначное число, для всех вариантов которого аналогично сумма будет $6⋅20⋅1111$ . С учётом того, что всего чисел $4⋅4!$ , имеем:

20⋅(11111⋅24 − 1111⋅6) S = --------96---------=54166.25

Ответ:

$54166 1 4$

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

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

Дан правильный $22$ -угольник $M$ . Найдите количество четвёрок вершин этого $22$ -угольника, являющихся вершинами выпуклых четырёхугольников, у которых есть хотя бы одна пара параллельных сторон.

Источники: Физтех-2015, 10.2 (см.olymp.mipt.ru)

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

Подсказка 1

Разбейте все диагонали (или стороны) на группы параллельных. Какими могут быть эти группы?

Подсказка 2

Такие группы бывают 2 видов: те, которые содержат диаметр, и те, которые не содержат. Посчитайте количества групп.

Подсказка 3

Как выбрать выпуклый четырёхугольник с 2 параллельными сторонами?

Подсказка 4

Надо выбрать 2 параллельных диагонали (или стороны) и построить трапецию. Главное, чтобы четырёхугольники получились различными.

Подсказка 5

Может ли нам помешать параллелограмм?

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

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

$PIC$

Для того, чтобы выбрать выпуклый четырёхугольник, у которого есть хотя бы одна пара параллельных сторон, нужно выбрать две параллельные диагонали (или стороны) и составить из них трапецию. Так мы получим $11⋅10 10⋅9 11⋅ 2 +11⋅ 2$ четырехугольников. Осталось проверить, что они различны. На самом деле если наш четырехугольник имеет две пары параллельных прямых (вписанный параллелограмм — это прямоугольник), то он был посчитан два раза. Значит, из этого числа нужно вычесть количество прямоугольников. Выбрать прямоугольник можно таким способом. Сначала выберем 2 его соседние вершины. Это можно сделать $22⋅20$ способами, так как соседние вершины не могут быть противоположными, а затем однозначно определим оставшиеся 2 вершины, так как диагональ прямоугольника должна проходить через центр окружности. Так, каждый прямоугольник мы посчитаем $4⋅2$ раз и поэтому всего прямоугольников $22⋅20 --8-$ .

Получаем ответ $11⋅10 10⋅9 22⋅20 11⋅-2--+11⋅-2-− --8-= 1045$ .

Ответ:

$1045$

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

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

Нынешний $2024$ год записывается четырьмя цифрами: $0,2,2$ и $4.$ Сколько раз в будущем год будет записываться этими же четырьмя цифрами?

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

Сразу заметим, что год не начинается с $0.$ Тогда первая цифра года или $2,$ или $4.$ Разберем каждый случай по отдельности.

(a) Если первая цифра года $2,$ то второй цифрой года может быть любая из трех оставшихся, так как одна цифра была использована. Третьей цифрой года может быть любая из двух оставшихся, а четвертой цифрой будет единственная оставшаяся цифра. Тогда может быть всего $6$ разных годов $(3⋅2⋅1).$ Но в этих годах есть $2024,$ который не должен учитываься. Тогда получаем, что вариантов всего $5.$

(b) Если первая цифра года $4,$ то второй цифрой года может быть любая из трех оставшихся, так как одна цифра была использована. Третьей цифрой года может быть любая из двух оставшихся, а четвертой цифрой будет единственная оставшаяся цифра. Тогда может быть всего $6$ разных годов $(3 ⋅2⋅1).$ Но в данном случае количество вариантов посчитано два раза, потому что были посчитаны упорядоченные пары вместо неупорядоченных. Тогда получаем, что вариантов всего $3.$

Итого получаем, что всего $8$ разных вариантов. Это $2042,$ $2204,$ $2240,$ $2402,$ $2420,$ $4022,$ $4202,$ $4220.$

Замечание. Для решения достаточно будет и перебора всех возможных годов.

Ответ: 8

Интенсивы

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

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

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

Есть семь карточек с цифрами $0;1;2;3;3;4;5$ . Сколько существует различных шестизначных чисел, делящихся на $15$ , которые можно сложить из этих карточек?

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

Подсказка 1

Чему равносильна делимость на 15?

Подсказка 2

Делимости на 3 и на 5. Вспомните признаки для этих 2 чисел.

Подсказка 3

У нас всего 7 карточек, а нужны шестизначные числа. Какой будет незадействованная карточка?

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

Чтобы число делилось на 5, оно должно заканчиваться на 5 или 0. А по признаку делимости на 3 его сумма цифр должна делиться на 3. Так как карточек 7 и их сумма равна $0+1+ 2+ 3+ 3+4 +5= 18$ , то единственная незадействованная карточка делится на 3 (так как 18 кратно 3 и сумма цифр кратна 3).

Если это карточка с цифрой 0, то на последнем месте стоит обязательно 5, на двух других местах стоят две тройки, а остальные 3 цифры различны и стоят как угодно. Тогда таких чисел ровно $2 C5 ⋅3!= 60$ .

Если это карточка с цифрой 3, то на последнем месте может стоять 5 или 0. Если это 0, то оставшиеся 5 цифр различны и стоят как угодно. Всего вариантов $5!=120$ . Если же это 5, то 0 может стоять на любом из 4 мест, а остальные цифры как угодно. Всего вариантов $4⋅4!= 96$ .

Всего: $60 +120+ 96 =276$ чисел.

Ответ: 276

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

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

Число $84605$ написали семь раз подряд, при этом получилось $35$ -значное число

84605846058460584605846058460584605.

Из этого $35$ -значного числа требуется вычеркнуть две цифры так, чтобы полученное после вычёркивания $33$ -значное число делилось на $15$ . Сколькими способами это можно сделать?

Источники: Физтех-2013, 11.4 (см. olymp.mipt.ru)

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

Подсказка 1

Нужно, чтобы наше число делилось на 15. Значит чего необходимо и достаточно? Как этого добиться? Верно, нужно, чтобы число делилось на 3 и на 5.

Подсказка 2

Чтобы число делилось на 5 нужно, чтобы последняя цифра была либо 5 либо 0. Значит нельзя вычеркнуть две последние цифры одновременно. Делимость на 3 обеспечивается суммой цифр. Сумма цифр вполне понятна. Тогда на что лучше заменить каждую из цифр в числе?

Подсказка 3

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

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

Для того, чтобы число делилось на $15,$ необходимо и достаточно, чтобы оно делилось на $3$ и на $5$ . Для делимости на $5$ нужно, чтобы последняя цифра числа была $0$ или $5.$ Значит, полученное число будет делиться на $5,$ если мы вычеркнем любые две цифры, кроме двух последних. Перейдём к делимости на $3$ .

Если в числе заменить все цифры $8$ и $5$ на $2$ , цифры $4$ на $1,$ а цифры $6$ на $0,$ то остаток от деления числа на $3$ не изменится (остаток от деления числа на $3$ равен остатку от деления суммы цифр этого числа на $3$ ). Нужно узнать, сколькими способами можно вычеркнуть две цифры из числа $X = 21002210022100221002210022100221002$ так, чтобы полученное число делилось на $3$ . Сумма цифр числа $X$ равна $35$ . Чтобы после вычёркивания сумма цифр делилась на $3$ , мы можем вычеркнуть либо а) две единицы, либо б) двойку и ноль.

а) Количество способов вычеркнуть две единицы равно $2 C7 = 21$

б) Количество способов вычеркнуть один ноль и одну двойку равно $C114⋅C114 =14⋅14= 196.$

Но в пункте (б) мы подсчитали способ, при котором вычеркнуты последние две цифры. Такого допускать нельзя, чтобы не нарушить делимость на $5$ . Этот способ нужно вычесть. Так что в итоге получаем $21+ 196− 1= 216$ способов.

Ответ:

$216$

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

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

Число 84605 написали семь раз подряд, при этом получилось 35-значное число

84605846058460584605846058460584605.

Из этого 35-значного числа требуется вычеркнуть две цифры так, чтобы полученное после вычёркивания 33-значное число делилось на 15. Сколькими способами это можно сделать?

Источники: Физтех-2013, 11.5

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

Подсказка 1

Рассмотрите отдельно делимость этого числа на 5 и на 3. В каком случае число не будет делиться на 5?

Подсказка 2

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

Подсказка 3

Если вычеркнем 2 единички или нолик с двоечкой, то нам число подойдет. Посчитаем кол-во способов выбрать 2 единички, отдельно - выбрать нолик с двоечкой, а дальше остался лишь счёт.

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

Для того, чтобы число делилось на 15, необходимо и достаточно, чтобы оно делилось на 3 и на 5. Для делимости на 5 нужно, чтобы последней цифрой числа была 0 или 5. Значит, полученное число будет делиться на 5, если мы вычеркнем любые две цифры, кроме двух последних. Перейдём к делимости на 3.

Если в числе заменить все цифры 8 и 5 на 2, цифры 4 на 1, а цифры 6 на 0, то остаток от деления числа на 3 не изменится (остаток от деления числа на 3 равен остатку от деления суммы цифр этого числа на 3). Таким образом, нужно узнать, сколькими способами можно вычеркнуть две цифры из числа $X = 21002210022100221002210022100221002$ так, чтобы полученное число делилось на 3. Сумма цифр числа $X$ равна 35. Чтобы после вычёркивания сумма цифр делилась на 3, мы можем вычеркнуть либо 1) две единицы, либо 2) двойку и ноль. Количество способов вычеркнуть две единицы равно $2 C 7 = 21$ ; количество способов вычеркнуть один ноль и одну двойку равно $1 1 C14⋅C14 = 14⋅14 =196$

Две последние цифры вычёркивать нельзя, поэтому получаем $196+ 21− 1= 216$ способов.

Ответ: 216

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

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

Сколькими различными способами можно выбрать целые числа $a,b,c∈[1;100]$ так, чтобы точки с координатами $A (− 1,a)$ , $B(0,b)$ и $C (1,c)$ образовывали прямоугольный треугольник?

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

В случае, когда гипотенуза равна AC, получим (b-a)(b-c) = 1, откуда получим, что каждая из скобок равна либо 1, либо -1, подумайте, как посчитать кол-во треугольников, которое получится в данном случае. Какие треугольники задаются при (b-a) = 1 и (b-a) = -1, а что нужно зафиксировать, чтобы получить треугольник, в одном из этих случаев?

Подсказка 4

Во-первых, нам повезло, что полученные 2 случая: с произведением равным 1 и равным -1, дают нам разные треугольники, а значит мы их просто сложим в конце, а во-вторых, когда мы фиксируем одно из чисел, то остальные однозначно получаются из заданных нами уравнений, а значит нам достаточно найти границы на одно из чисел так, чтобы остальные тоже попадали в заданные границы [1;100]. Остальные случаи убиваются так же быстро.

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

$AB2 = 1+(b− a)2, BC2 = 1+(c− b)2, AC2 =4+ (c− a)2.$

Если треуогльник $ABC$ прямоугольный с гипотенузой $AC$ , то по т.Пифагора

2 2 2 AC = AB +BC

1+ (b− a)2+1+ (b− c)2 = 4+(a− c)2

что приводится к виду $(b− a)(b − c)= 1$ . Так как оба множителя — целые числа, имеем только такие случаи: $b= a+1 =c+ 1$ и $b= a− 1= c− 1$ , для каждого из которых есть $99$ троек $(a,b,c)$ , т.е. всего $198$ способов.

Если гипотенузой является сторона $AB$ , то аналогично получаем соотношение $(c− a)(c− b) =−2$ , что возможно только в следующих случаях:

c =a+ 1= b− 2

c =a− 1= b+ 2

c =a+ 2= b− 1

c =a− 2= b+ 1

для каждого из которых есть $97$ троек $(a,b,c)$ , т.е. всего $97⋅4= 388$ способов.

Если гипотенузой является сторона $BC$ , то получаем соотношение $(a − b)(a− c)= −2$ . Аналогично предыдущему, находим $388$ способов.

Всего получаем $198+ 388+ 388= 974$ способов.

Ответ: 974

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

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

Круг разбили на 4 равных сектора по $90∘$ . Сколькими способами можно его раскрасить, если есть 7 цветов и каждый сектор можно красить в любой цвет? Раскраски, которые совпадают при повороте круга, считать одинаковыми.

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

Подсказка 1

Что будет, если раскраски, отличающиеся поворотом, считать за различные? А какие раскраски считаются несколько раз? Сколько?

Подсказка 2

Рассмотрим одноцветные раскраски, те, что переходят друг в другая поворотом на 180 градусов, и те, что невозможно поворотом перевести в самого себя. Хочется просто вычесть из общего количества повторы. Что может помешать?

Подсказка 3

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

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

Если не отождествлять раскраски, отличающиеся поворотом, то их всего будет $74$ . Отнесём каждый из таких способов раскраски к одному из трех видов.

1) Одноцветные раскраски – их всего $7$ . (Каждый поворот на $∘ 90$ переводит их в себя)

2) Разноцветные раскраски с противоположными секторами одинакового цвета – их $7⋅6 2 =21$ , по числу способов выбора пары цветов из семи. (Каждый поворот на $∘ 180$ переводит такие раскраски в себя)

3) Прочие раскраски, не переходящие в себя ни при каком повороте.

Из общего числа $4 7$ , каждая раскраска первого типа считается $1$ раз, раскраска второго типа - по $2$ раза, и раскраска третьего типа - по $4$ раза. Отсюда можно найти число способов раскраски третьего типа. Это

74− 7− 2⋅21 -----4---- = 588

Тогда общее число способов раскраски, с учётом отождествлений, получается как сумма $7+21+ 588= 616$ .

Ответ: 616

Предыдущая подтема

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