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

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

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

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

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

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

Подтемы раздела количество способов, исходов, слагаемых

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

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

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

На сторонах треугольника $ABC$ отметили точки: $10$ — на стороне $AB,11$ — на стороне $BC,12$ — на стороне $AC.$ При этом ни одна из вершин треугольника не отмечена. Сколько существует треугольников с вершинами в отмеченных точках?

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

Первое решение.

Три точки из $33$ данных можно выбрать $3 C33 =5456$ способами.

При этом треугольник образуется во всех случаях за исключением того, когда все три точки лежат на одной прямой. Итак, не подходят $3 3 3 C12+ C11+C 10 =220+ 165 +120= 505$ случаев.

Значит, всего есть $5456− 505 =4951$ треугольник.

Второе решение.

Выбрать по одной точке на каждой стороне можно $1 1 1 C 12⋅C11⋅C10 = 12⋅11 ⋅10 =1320$ способами.

Выбрать две точки на одной стороне и одну точку на другой можно $2 1 2 1 2 1 2 1 2 1 2 1 C12⋅C11+ C12⋅C10 +C11⋅C12+ C11 ⋅C 10+ C10⋅C12+C 10⋅C11 = 66⋅21+55⋅22+ 45⋅23 =1386+ 1210+ 1035 =3631$ способами.

Значит, всего есть $1320+ 3631 =4951$ треугольник.

Ответ:

$4951$

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

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

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

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

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

( ) 1 2 3 4 5 6 3 6 4 5 1 2

То есть первый символ ставится на третье место, второй - на шестое и так далее. В своем пароле для почты qwerty Петя переставил буквы по правилу из книжечки, а затем, для большей надежности переставил буквы по этому же правилу еще раз. (Если использовать правило как в примере, то из qwerty после первой перестановки получится tyqerw, а после второй — rwtqey).

a) Какие из нижеследующих комбинаций


yetrqw	eyrtqw	yrwteq	rewqyt	qwtyre	tywreq

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

б) Петя потерял книжечку! Он помнит, что первоначально пароль был qwerty, но правило, по которому были в нём дважды переставлены буквы, не помнит. За какое наименьшее число попыток можно с гарантией подобрать утерянный пароль?

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

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

Подсказка 1

В этой задачи нам описали какой-то алгоритм и просят понять, что могло быть результатом этого алгоритма. В таких задачах полезно поискать инварианты (то, что не меняется в результате работы алгоритма) или свойства: как данный алгоритм работает для некоторых схожих входных данных. Обратите внимание на то, что в алгоритме как бы описаны взаимодействия между объектами: символ с места A переходит в символ с местов B, а какой математический объект позволяет нам показывать связи между объектами?

Подсказка 2

Правильно, можно использовать граф, попробуйте нарисовать его для правила из "примера", а затем для двойной перестановки и посмотрите, как он изменился. Если не сразу понятно, на что обращать внимание, то придумайте своё правило для перестановки чисел и проделайте те же действия.

Подсказка 3

Можно заметить, что циклы длины 2n распадаются на 2 цикла длины n, а каждый цикл длины 2n+1 остаётся длины 2n+1 (взаимосвязи между объектами другие, но длина та же). Ага! Из каждого объекта при какой-то операции получается по 2 объекта, на что это похоже?

Подсказка 4

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

Подсказка 5

Верно, если мы посмотрим, что происходит с циклами длины 2 * (2n+1) (длина которых делится на 2, но не делится на 4), то они просто превращаются в нечётные циклы, а так как мы не знаем, сколько изначально было циклов нечётной длины, то про их итоговую чётность мы ничего сказать не можем. Почему бы тогда не посмотреть на циклы чётной длины, ведь они могут получиться только из циклов кратных 4. А сколько тогда циклов чётной длины будет?

Подсказка 6

Да, циклов чётной длины чётное количество, иначе бы не выполнялось утверждение о том, что из циклов длины 2n получаются 2 цикла длины n. Осталось посмотреть, какие из перестановок из пункта "а" противоречат данному утверждению, а для остальных найти пример!

Подсказка 7

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

Подсказка 8

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

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

Приведенное в условии правило перестановки букв, или перестановку, будем обозначать греческой буквой $σ.$ Перестановку $σ$ можно интерпретировать как отображение множества цифр ${1,2,3,4,5,6}$ в себя. Например, тот факт, что первая буква перешла на третье место, можно записать как $σ(1)= 3,$ а также изобразить стрелочкой из 1 в 3:

$PIC$

Видно, что если бы мы перестановку $σ$ применяли многократно, то буквы на 2-й и 6-й позициях постоянно менялись бы местами, а буквы на позициях 1, 3, 4, 5 переставлялись бы по циклу. Поэтому перестановка $σ$ может символически быть записана в виде произведения циклов:

( ) σ = 1 2 3 4 5 6 = (1345)(26)= 4∗2 3 6 4 5 1 2

Запись $4∗ 2$ отражает цикловую структуру перестановки $σ,$ показывая, что в ней один цикл длины 4 и один цикл длины 2.

Посмотрим теперь более детально на то, что произойдет, если по правилу $σ$ переставить буквы еще раз. Так 1 при первом применении правила $σ$ перешла в 3: $σ(1)=3,$ а при повторном применении 3 перешла в 4: $σ(3)= 4.$ Значит, в результате двойной перестановки 1 переходит в 4. Будем это записывать как $σ(σ(1))= 4$ или же $2 σ (1) =4.$ Поэтому правило двойной перестановки букв, представляющее собой квадрат перестановки $σ,$ выглядит так:

$PIC$

Заметим, что после повторной перестановки 2 и 6 вернутся на свои места, то есть цикл $(2,6)$ распадется на два тривиальных цикла $(2)$ и $(6),$ а цикл $(1345)$ превратится в два цикла $(1,4)$ и $(3,5).$ Таким образом, при повторном применении перестановки циклы четной длины $2n$ распадаются на два цикла, длины $n$ каждый. Несложно проверить, что при этом циклы нечетной длины сохраняются. Справедливо утверждение.

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

Рассмотрим первую комбинацию уеqwrt из пункта а). Она получена из qwerty перестановкой $( ) 1 2 3 4 5 6 = (1324561), 3 4 2 5 6 1$ которая представляет собой цикл длины 6. Поскольку циклов четной длины здесь нечетное количество (всего один), то, согласно утверждению, такая комбинация двойной перестановкой букв получиться не могла. Аналогично исследуются и остальные комбинации в пункте а).

Проведем подсчет общего числа перестановок, являющихся полными квадратами. Их цикловые структуры могут быть следующие:

$1∗ 1∗1∗1∗ 1∗1.$ Это перестановка, оставляющая все на своих местах (тождественная перестановка). Она единственна.
$1∗ 5.$ Мы должны выбрать 5 элементов из шести, чтобы составить цикл дины 5. Это можно сделать 6-ю способами. Из пяти элементов цикл длины 5 можно организовать $(5− 1)!$ способами (действительно, организуем цикл из пяти элементов $a1,a2,a3,a4,a5;$ элемент $a1$ может перейти в любой из четырех (т.к. в себя нельзя), элемент $a2$ переходит в один из оставшихся трех и т.д. В итоге получаем $4 ⋅3 ⋅2 ⋅1$ способов). Таким образом, здесь $6⋅4!= 144$ перестановок.
$2∗ 2∗1∗1.$ Выбрать два элемента из шести для первого цикла длины 2 можно $2 C6$ способами. Для второго цикла длины 2 есть $2 C4$ способа. Итого $2 2 C 6 ⋅C4 = 90.$ От порядка следования циклов результат не зависит, поэтому 90 еще следует разделить на два. Всего 45 перестановок с такой структурой.
$3∗ 3.$ Здесь мы 6 элементов десятью способами $( ) 12C36 = 10$ разбиваем на две тройки и из каждой тройки получаем по 2 цикла. Всего 40 перестановок.
$3∗ 1∗1∗1.$ Здесь мы двадцатью способами $( ) C36 = 20$ выбираем тройку и из каждой тройки получаем по 2 цикла. Всего 40 перестановок.

В итоге, имеется $1+144+ 45+40+ 40= 270$ перестановок длины 6, представляющих собой полный квадрат.

Ответ:

a) yetrqw, tywreq;

б) 270

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

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

Айрат выписывает все четырехзначные числа, в записи которых есть только цифры $2$ и $6.$ Сколько выписанных им чисел делятся и на $2,$ и на $6?$

Источники: Муницип - 2022, Республика Татарстан, 7.4

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

Подсказка 1

Мы понимаем, что если число делится на 6, то оно делится и на 2, и на 3. А что может гарантировать делимость на 3?

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

Понятно, что если число делится на $6,$ то делится и на $2.$ Тогда нам нужна делимость чисел на $6,$ а это значит, что число должно делиться на $2,$ и на $3.$ Тогда и сумма цифр нашего числа должна делиться на $3.$ Какой может быть сумма цифр числа, используя $2$ и $6?$ Возможны варианты

6⋅4= 24; 2+6 ⋅3 =20; 2⋅2+ 6⋅2= 16; 2⋅3+6 =12; 2⋅4= 8

Получаем, что подходящие нам четырёхзначные числа могут быть только из всех $6$ или со всеми $2,$ кроме одной. И того, несложно перебрав, получаем $5$ чисел( $6666,2226,2262,2622,6222$ ).

Ответ: 5

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

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

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

Источники: Изумруд-2022, 11.2 (см. izumrud.urfu.ru)

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

Подсказка 1

Попробуем представить себе расстановку чисел в таблице (от а₁ до а₉). Что можно точно сказать об этих числах?

Подсказка 2

Правильно, в каждом ряду и столбце последующее число больше предыдущего. Подумайте, чему равны первое (а₁) и последнее (а₉) числа, а также попробуйте вывести оценку на а₅.

Подсказка 3

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

Подсказка4

Если а₅ = 4 или 6, по очереди находим количество способов расстановки чисел, меньших и больших а₅, а затем перемножаем. Если а₅ = 5, то следует начать с рассмотрения клеток а₃ и а₇ и количества способов для каждого значения цифр, стоящих в этих клетках. Остаётся только проверить, нет ли у нас пересекающихся случаев, и сложить общее количество способов

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

Пронумеруем клетки таблицы так, как показано на рисунке. Ясно, что в левой верхней клетке стоит число 1, а в правой нижней — число 9.


1	$a2$	$a3$

$a4$	$a5$	$a6$

$a7$	$a8$	9

По условию $a5 > a2,a5 > a4,a5 < a6,a5 <a8,$ поэтому $4 ≤a5 ≤ 6.$ Рассмотрим случаи.

1) Если $a5 =4,$ то числа $a2$ и $a4$ — это 2 и 3. Способов их расстановки всего 2. Теперь вычислим количество вариантов выбора чисел $a3$ и $a6.$ На их место можно поставить любую из оставшихся пар чисел, причём $a3 < a6,$ поэтому расстановка каждой пары определяется однозначно. Всего таких пар $C2 = 6. 4$ Оставшиеся два числа расставляются однозначно. Всего получилось $2 ⋅6 =12$ вариантов расстановки.

2) Если $a5 =6,$ то числа $a6$ и $a8$ — это 7 и 8, и случай аналогичен предыдущему. Получаем ещё 12 вариантов расстановки.

3) Если $a5 =5,$ то посмотрим, какие числа могут стоять в клетках с номерами $a3$ и $a7.$ На их место нельзя ставить числа 2 и 8, так как эти числа обязаны быть соседями 1 и 9 соответственно. Если $a =3, 3$ то $a = 2 2$ и $a = 4. 4$ Любое из оставшихся чисел можно поставить в клетку $a 6$ тремя способами, оставшиеся числа ставятся однозначно. Рассмотренный вариант аналогичен случаям $a = 7,a =3 3 7$ и $a = 7 7$ — в каждом получаем по 3 варианта расстановки, но были дважды посчитаны случаи, когда числа $a 3$ и $a 7$ — это 3 и 7. Всего таких случаев два:


1	2	3

4	5	6

7	8	9


1	4	7

2	5	8

3	6	9

В итоге получаем $3⋅4− 2= 10$ вариантов.

Если ни одно из чисел в клетках $a3$ и $a7$ не равно 3 или 7, то в клетках $a3$ и $a7$ могут стоять лишь числа 4 и 6 в любом порядке. Тогда в клетках $a2$ и $a4$ стоят числа 2 и 3 в любом порядке, а в клетках $a6$ и $a8$ — числа 7 и 8 в любом порядке. Всего 8 вариантов расстановок.

Все случаи разобраны, искомое число вариантов равно $24+ 10+8 =42.$

Ответ: 42

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

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

Паша, Оля и Саша играли в тетрис. Тот, кто побеждал в очередном раунде, получал одно очко, остальные — по 0. Побеждает тот, кто первым наберёт 101 очко. Оле очень не везло: у неё всё ещё было 0 очков, когда один из остальных двух участников уже набрал 100. Но потом она собралась с силами и победила, при этом у Паши и Саши было по 100 очков. Сколько существует последовательностей побед, при которых такое могло произойти?

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

Подсказка 1

Заметим, что до последней победы Оли у всех ребят было по 100 побед. Тогда нам надо разобрать два симметричных случая, когда Саша или Паша набрали 100 очков, а у Оли было на тот момент 0 очков, как это можно сделать?

Подсказка 2

Да, скажем, что на первых 100 местах были победы Саши, на последних 100 местах были победы Оли, а для побед Паши есть 300 мест(между местами Саши и Оли, а также в начале и в конце), причем их было тоже ровно 100. Сколькими способами можно так распределить победы?

Подсказка 3

Верно, это будет число сочетаний из 300 по 100, аналогично разбирается случай, когда на первых 100 местах были победы Паши! Осталось понять, а не учли ли мы какие-то случаи дважды? Мы смогли гарантировать, что на момент, когда у кого-то из ребят было 100 побед, у Оли было ровно 0 побед, но вот про то, что какие-то способы мы посчитали дважды, пока не думали.

Подсказка 4

Да, мы дважды учли ровно те ряды из побед, когда у Паши и Саши было уже 100 побед, а у Оли еще не было побед. То есть, нам надо вычесть все одинаковые последовательности длины 200 из побед только Саши и Паши. То есть надо вычесть число сочетаний из 200 по 100.

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

Будем писать букву П, О или С, если в очередном раунде побеждает Паша, Оля или Саша соответственно. Из условия следует, что последнюю победу одержала Оля; отбросим эту победу, количество подходящих последовательностей не изменится.

Посчитаем сначала последовательности, в которых Саша набрал 100 очков, когда у Оли всё ещё было 0 очков. Подходят те последовательности букв, которые можно получить так: сначала написать 100 букв С, потом 100 букв О, а где-то между ними (а также в конец или начало ряда) нужно вставить 100 букв П. Это означает, что нам нужно из 300 объектов выбрать 100, которые будут П-шками, из оставшихся 200 объектов первые 100 будут С-ками, последние 100 — О-шками. Количество способов равно $100 C300$ .

Последовательностей, в которых Паша набрал 100 очков, когда у Оли всё ещё было 0 очков, столько же, но некоторые подходящие последовательности посчитаны дважды: те, в которых и Саша, и Паша набрали по 100 очков, а у Оли было в этот момент 0. Во всех таких последовательностях на конце будет 100 букв О, и нам нужно выбрать порядок для первых 200 букв, причём 100 из них — П-шки, оставшиеся 100 — С-ки. Количество способов равно $C120000$ , и эти способы нужно отнять, что даёт ответ.

Ответ:

$2⋅C100− C100 300 200$

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

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

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

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Не забывайте, что если сумма цифр при сложении в столбик равна 5, то она именно 5, потому как мы всегда берём остаток по модулю 10, когда считаем в столбик, поэтому надо рассматривать ещё случаи, когда она равна 15, 25.

Подсказка 4

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

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

Пусть искомое число есть $abcdefg, (a ⁄=0)$ . Определим, какой может быть максимальная степень десятки, на которую происходит деление. Возможны несколько случаев:

1) если максимальная степень десятки равна $4$ или меньше, то сумма остатков меньше $4 3 2 10 + 10 + 10 = 11100$ , что меньше $12345;$

2) если максимальная степень десятки равна $7$ или больше, то сумма остатков не меньше $6 a⋅10$ , что больше $12345;$

3) максимальная степень десятки равна $5$ или $6$ . Эти случаи возможны.

3.1) Пусть максимальная степень десятки равна $5$ . Тогда остатки от деления на $5 4 3 10, 10 , 10$ равны соответственно $----- ------- cdefg, defg,efg$ , и сумма остатков есть

c⋅104+ 2d⋅103 +3S

где $S = efg, 0≤ S <1000.$

Рассмотрим уравнение $4 3 c⋅10 +2d⋅10 + 3S = 12345$ . Так как $4 12345 <2 ⋅10$ , то либо $c= 0$ , либо $c= 1.$

Если $c= 0$ , то получаем

3 3 2d ⋅10 + 3S = 12345⇒ 2d⋅10 = 12345− 3S = 3(4115− S)

Поэтому $2d$ делится на $3.$ При этом $9< 2d ≤12$ , так как $0≤ S <1000.$ Поэтому $d =6$ , откуда $S = 115$ . То есть число имеет вид $------ ab06115$ . Таких чисел $90.$

Если $c= 1$ , то

2d⋅103+3S =2345.2d⋅103 =2345− 3⋅S

Поэтому либо $d =0$ , либо $d= 1$ . Если $d= 0$ , то $3S = 2345$ , что невозможно. Если $d =1$ , то $3 ⋅S = 345$ , откуда $S = 115$ . То есть число имеет вид $------ ab11115$ . Таких чисел 90.

3.2) Пусть максимальная степень десятки равна $6$ . Тогда остатки от деления на $6 5 4 10 , 10, 10$ равны соответственно $----- ----- bcdefg,cdefg$ , $---- defg$ . И сумма остатков есть

b⋅105 +2c⋅104 +3S

где $---- S = defg, 0≤ S < 10000.$

Рассмотрим уравнение

b⋅105+ 2c⋅104+ 3S = 12345.

Это равенство возможно только при $b= c= 0$ . Значит, $3S = 12345$ , откуда $S = 4115$ , то есть число имеет вид $------ a004115$ . Таких чисел $9.$

Значит, искомое количество семизначных чисел есть $90+ 90+ 9= 189.$

Ответ: 189

Курсы

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

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

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

На поле $4× 5$ в левом нижнем углу сидит кролик, а в правом верхнем углу лежит морковка. Сколькими способами кролик может добраться до морковки, если ему разрешено прыгать только на одну клетку вверх, вправо или по диагонали вправо-вверх?

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

Если мы не прыгаем по диагонали, то нам нужно сделать 3 прыжка вверх и 4 вправо. Вариантов расставить эти 9 шагов в каком-то порядке это тоже самое, что из 9 прыжков выбрать те, которые будут вверх. Всего таких вариантов $4 C7$ .

Если мы прыгаем по диагонали один раз, то нам нужно сделать 2 прыжка вверх и 3 вправо и один по диагонали. Тогда сначала $1 C6 =6$ способами выберем когда мы сделаем прыжок по диагонали, а затем $2 C5$ выберем когда будем прыгать вверх. Итого получится $1 2 C6 ⋅C5$ способов в этом случае.

Если мы прыгаем по диагонали два раз, то нам нужно сделать 1 прыжка вверх и 2 вправо и 2 по диагонали. Аналогично, получится $2 1 C5 ⋅C 4$ способов в этом случае.

Если мы прыгаем по диагонали 3 раз, то нам нужно сделать прыжок вправо и 3 по диагонали. Аналогично, получится $1 C4$ способов в этом случае.

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

Ответ:

$C4 +C1 ⋅C2+ C2⋅C1+ C1 7 6 5 5 4 4$

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

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

В некотором языке $N$ буквы обозначают всего $10$ согласных и $5$ гласных звуков. Слоги в этом языке допустимы двух видов: либо «согласный $+$ гласный», либо «согласный $+$ гласный $+$ согласный». Словом в языке $N$ является любая последовательность букв, которую можно допустимым образом разбить на слоги. Например, русское слово «кошка» могло бы быть словом языка $N$ , поскольку оно может быть разбито на слоги как «кош-ка», а вот слова «гроза» в языке $N$ существовать не могло бы, поскольку оно начинается с двух согласных, которые на слоги не разделяются. Сколько всего в языке $N$ восьмибуквенных слов?

Источники: ВСОШ - 2022, школьный этап, 8 класс

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

Заметим, что количество гласных не должно быть больше половины от общего количества букв в слове, то есть больше 4, поскольку в каждом слоге с гласным есть хотя бы один согласный. Также количество гласных не может быть меньше $1∕3$ от количества букв в слове, поскольку согласных максимум в два раза больше, чем гласных. Таким образом, 2 или меньше гласных в восьмибуквенном слове быть не может. Это означает, что возможные количества гласных - 4 или 3. В первом случае возможно только одно разбиение на слоги: сг-сг-сг-сг, а во втором случае возможны три разбиения: сгс-сгс-сг, сгс-сг-сгс, сг-сгс-сгс (с - согласный, г - гласный).

Посчитаем количества слов при каждом из четырех разбиений на слоги: сг-сг-сг-сг: $4 4 10 ∗5∗10∗5∗ 10 ∗5∗10∗5= 10 ∗5$ сгс-сгс-сг: $5 3 10∗5 ∗10∗10∗5∗10∗ 10∗ 5= 10 ∗ 5$ сгс-сг-сгс: $5 3 10 ∗5∗10∗10∗5 ∗10 ∗5∗10= 10 ∗5$ сг-сгс-сгс: $5 3 10∗5∗10∗5 ∗10∗10∗5∗10 =10 ∗5$ Общее количество восьмибуквенных слов в языке N равно сумме этих четырёх чисел, то есть $4 4 5 3 10 ∗5 +3 ∗10∗ 5 =43750000$ .

Ответ: 43750000

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

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

На доске написано 10 простых чисел: $2,3,5,7,11,13,17,19,23,29$ . Максим нашёл все попарные произведения этих чисел и выписал их на доску, после чего, стёр все изначальные числа и все повторяющиеся. Затем он нашёл все попарные произведения оставшихся чисел и выписал их на доску, после чего снова стёр все изначальные числа и все повторяющиеся. Сколько теперь чисел написано на доске?

Источники: Изумруд - 2021, 11.2 (см. izumrud.urfu.ru)

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

Подсказка 1

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

Подсказка 2

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

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

Для удобства обозначим изначально записанные на доске числа как $p ,p ,...,p 1 2 10$ .

Поскольку любые два начальных числа взаимно просты, все попарные произведения будут различными, а всего их будет $2 C10 = 45$ . Именно столько чисел останется после того, как Максим сотрёт все изначальные числа. Все оставшиеся числа имеют вид $pipj$ , где $1 ≤i,j ≤10,i<j$ . Произведение двух оставшихся чисел может быть одного из двух видов: $pkplpmpn$ или $2 pkplpn$ , где $k ⁄=l⁄= m ⁄= n$ .

Всего различных чисел вида $pkplpmpn$ столько же, сколько и различных четвёрок чисел $k,l,m,n$ , а их всего $4 C10 = 210$ . Каждое из чисел вида $pkplpmpn$ может быть получено тремя способами: при перемножении чисел $pkpl$ и $pmpn,pkpm$ и $plpn$ или $pkpn$ и $plpm$ . То есть каждое из таких чисел будет написано трижды, поэтому с учётом повторяющихся чисел всего их будет написано 630 .

Чтобы узнать количество чисел вида $pkp2lpn$ , необходимо вычесть из количества всех чисел количество чисел вида $pkplpmpn$ (с учётом повторяющихся). После второго действия до того, как будут стёрты повторяющиеся числа, их будет всего $C245 = 990$ . Значит, чисел вида $pkp2lpn$ всего $990− 630 =360$ . Но каждое из чисел вида $pkp2lpn$ может быть получено лишь одним способом — при перемножении чисел $pkpl$ и $plpn$ , поэтому повторяющихся чисел такого вида не будет. Значит, после того, как Максим сотрёт все повторяющиеся числа, на доске останется $210+ 360= 570$ чисел.

Замечание. На олимпиаде 2021 года баллы за задачу не снимались, если условие понималось так, что после второго действия Максим стирал все числа вида $pkplpmpn$ .

Ответ: 570

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

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

У Олега есть $1000$ рублей, и он хочет подарить маме на $8$ Марта тюльпаны, причем непременно их должно быть нечётное число, и ни один оттенок цвета не должен повторяться. В магазине, куда пришел Олег, один тюльпан стоит $49$ рублей, и есть в наличии цветы двадцати оттенков. Сколько существует способов у Олега подарить маме цветы?

Источники: Межвед - 2021, 11.1 (см. v-olymp.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Верно, 2^20. Но что делать с букетиками, в которых чётное количество оттенков? Было бы хорошо, если бы мы смогли добавлять цветки туда, где нужно подправить чётность количества. Но ведь у нас тогда будут повторы, нам бы еще один оттенок... или можно изначально собирать букеты иначе? ;)

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

Из условия очевидно, что максимальное количество цветов в букете — $20.$ Рассмотрим $19$ цветов $19$ различных оттенков. Собрать букет из этих цветов без учёта чётности можно $19 2$ способами. Если в букете нечётное количество цветов, то мы его оставляем, если же чётное — добавляем неиспользованный двадцатый цветок. Таким образом, общее количество способов собрать букет равно $19 2$ .

Ответ:

$219$

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

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

В магазине продаётся $9$ наушников, $13$ компьютерных мышек и $5$ клавиатур. Кроме этого ещё есть $4$ набора «клавиатура и мышка» и $5$ наборов «наушники и мышка». Сколькими способами можно купить три предмета: наушники, клавиатуру и мышку?

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

Подсказка 1

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

Подсказка 2

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

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

Разберём случаи того, покупался ли какой-то набор.

- Пусть покупался набор «клавиатура и мышка», тогда к нему докупались наушники. Получается ровно $4⋅9= 36$ способов совершить покупку.

- Пусть покупался набор «наушники и мышка», тогда к нему докупалась клавиатура. Получается ровно $5⋅5= 25$ способов совершить покупку.

- Пусть не покупался ни один набор, тогда покупались наушники, мышка и клавиатура по отдельности. Получается ровно $9⋅13 ⋅5 =585$ способов совершить покупку.

Итого существует ровно $36+ 25+585= 646$ искомых способов.

Ответ: 646

Интенсивы

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

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

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

Дан квадрат, стороны которого равны $500.$ Его стороны разбиты отмеченными точками на отрезки длины $2$ (вершины исходного квадрата тоже отмечены). Найдите количество четвёрок из отмеченных точек, являющихся вершинами прямоугольника.

Источники: Физтех - 2021, аннулированный из-за технических проблем вариант

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

Подсказка 1:

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

Подсказка 2:

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

Подсказка 3:

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

Подсказка 4:

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

Подсказка 5

Чтобы это использовать, попробуйте учесть и подобие, и тот факт, что все стороны квадрата равны 500. Теперь должно получиться посчитать количество способов!

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

Посчитаем число отрезков, на которые разбили квадрат: $500-=250, 2$ тогда число точек равно $251.$

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

Рассмотрим случай, когда фиксируются две точки на соседних сторонах. Определим, когда в этом случае образуется прямоугольник:

Пусть сторона прямоугольника образует с квадратом угол $α.$ Тогда получаем четыре подобных прямоугольных треугольника с гипотенузами, являющимися сторонами прямоугольника, причём противоположные треугольники равны. Их острые углы равны $α$ и $∘ 90 − α.$

Обозначим катеты одного из треугольников за $x$ и $y.$ Тогда треугольники подобны с коэффициентом $x y .$

Рассмотрим два соседних треугольника. Если у одного из них катет равен $x,$ то у другого катет равен $500 − x.$

Из подобия найдём вторую сторону:

(500− x)⋅ x y

Из равенства противоположных треугольников получаем уравнение:

500= (500− x)⋅ x+ y y

Откуда:

(x − y)(500− x− y)=0

Следовательно, либо $x= y,$ либо $x +y =500.$

Теперь посчитаем все случаи:

1. Если фиксируем две точки на одной стороне, то точки можно выбрать на вертикальной и горизонтальной сторонах квадрата. При этом сам квадрат мы посчитали дважды. Общее количество таких прямоугольников:

251⋅250-⋅2− 1 2

2. Если фиксируем точки на соседних сторонах квадрата, первую точку (без учёта вершин квадрата) можно выбрать $249$ способами. Тогда вторую точку можно выбрать двумя способами: либо $x= y,$ либо $x +y =500.$ Учтём также, что случай $x = y 2$ был посчитан дважды:

249 ⋅2 − 1

Сложив оба случая, получаем:

251⋅250⋅2− 1+249⋅2− 1= 63246 2

Ответ:

63246

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

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

Найдите количество восьмизначных чисел, произведение цифр каждого из которых равно $3375.$ Ответ необходимо представить в виде целого числа.

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

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

Подсказка 1

Если произведение 8 цифр это 3375, то надо выяснить, какие это могут быть цифры вообще и сколько раз они встречаются в записи числа.

Подсказка 2

Ага, получилось два набора цифр: в одном пятерки, тройки и единички, в другом есть помимо них девятка. Находим, сколько в первом наборе способов поставить тройки, потом на оставшиеся места пятерки и тд, то же делаем для второго набора и понимаем, что эти наборы не пересекаются -> работает правило сложения

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

Разложим $3375$ на множители. $3375 =5⋅675= 52⋅135= 53⋅27= 53⋅33.$ Значит, либо в нашем числе есть $3$ пятерки, $3$ тройки и остальные единицы, либо в нашем числе есть $3$ пятерки, $1$ девятка, $1$ тройка и остальные единицы.

В первом случае способов выбрать места для пятерок можно $3 8⋅7⋅6 C8 = 3!$ способами, так как нам нужно выбрать три места из восьми для пятерок. Затем выбрать места для троек $3 5⋅4⋅3 C5 = 3!$ вариантов, а остальные места займут единицы, поэтому всего в этом случае $8⋅7⋅6 5⋅4⋅3 3! ⋅ 3! =56⋅10= 560$ вариантов.

В втором случае способов выбрать места для пятерок так же $3 8⋅7⋅6 C8 = 3! ,$ выбрать место для тройки можно из оставшихся пяти, для девятки — из оставшихся четырёх, а остальные места займут единицы, поэтому всего в этом случае $8⋅7⋅6 3! ⋅5⋅4= 56⋅20= 1120$ вариантов.

Итого $1120+ 560 =1680$ вариантов.

Ответ:

$1680$

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

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

Рассмотрим всевозможные 100-значные натуральные числа, в десятичной записи которых встречаются только цифры 1,2. Сколько среди них делятся на 3 нацело?

Источники: Межвед - 2020 (см. v-olymp.ru)

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

Подсказка 1

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

Подсказка 2

Давайте попробуем дописать 2 цифры так, чтобы число стало делиться на 3. Какие для этого есть варианты?

Подсказка 3

Количество вариантов для дописывания зависит от того, делилось ли 98-значное число на 3. Попробуем явно рассмотреть случаи, это, кажется, не так сложно!

Подсказка 4

Отлично! Теперь мы умеем выражать ответ для n=100 через ответ для n=98. А что нам мешает "спуститься" ещё ниже, к числам меньшей длины?)

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

Каждое 100-значное натуральное число может быть получено дописыванием двух цифр справа к 98-значному числу. Пусть $x$ — некоторое 98-значное число. Посмотрим какие справа две цифры (каждая из которых равна 1 или 2) нужно к числу $x$ приписать, чтобы получившееся 100значное число делилось на 3. Воспользуемся тем, что остаток от деления натурального числа на 3 равен остатку от деления на 3 суммы его цифр. Пусть наше число $x$ при делении на 3 дает остаток $m$ . Тогда

- если $m = 0$ , то припишем 12 или 21 ;

- если $m = 1$ , то припишем 11 ;

- если $m = 2$ , то припишем 22 ;

Таким образом, из каждого 98-значного числа, кратного 3, можно получить два кратных трем 100 -значных числа. Каждое не кратное трем 98-значное число порождает только одно кратное трем 100-значное число.

Всего 98-значных чисел $298$ . Пусть среди них $A98$ чисел кратно трем. (Далее символом $An$ будем обозначать количество n-значных чисел, кратных 3.) Тогда количество кратных трем 100 -значных чисел может быть найдено по формуле

( ) A100 = 2A98 + 298 − A98 = 298+ A98

Верны, таким образом, следующие соотношения:

98 A100 = 2 + A98 A98 = 296+ A96 ... 4 A6 = 2 +A4 A4 = 22+A2.

Сложив эти равенства (величины $A4,...,A98$ при этом сокращаются), получим

A100 = A2+ 22 +24+ ⋅⋅⋅+ 298

Остается просуммировать геометрическую прогрессию и заметить, что $A =2 2$ . Тогда

50 50 A100 =2+ 4--−-4= 4--+2- 3 3

Ответ:

$450+-2 3$

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

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

Звук записывается на магнитный слой барабана, который вращается с постоянной скоростью, совершая один оборот за $4$ секунды. Рядом с барабаном по окружности через равные расстояния размещены записывающая $(1)$ и три читающие головки $(2),$ $(3),$ $(4).$ В каждый момент времени в телефонную линию передается сигнал с одной из читающих головок. Устройство спроектировано так, что каждый участок сигнала будет передан в линию один раз, а сама передача стартует, как только начало записи окажется у $3$ -й читающей головки. Сколько различных вариантов звука, переданного в линию, может получиться, если сообщение длилось $20$ секунд?

$PIC$

Источники: Верченко - 2020, 11.5

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

Подсказка 1

Пусть передача длилась n секунд. Как можно представить звук, переданный на линию?

Подсказка 2

Переключение между читающими головками происходит раз в секунду, поэтому можно разбить весь звук на n фрагментов и рассматривать их перестановки.

Подсказка 3

Обозначим количество перестановок за T(n). Передача закончится на (n+1)-ой секунде. Какие фрагменты могут быть переданы в этот момент на линию?

Подсказка 4

Мог быть передан n-ый или (n+1)-ый фрагмент. Рассмотрите оба случая.

Подсказка 5

Пусть был передан (n+1)-ый фрагмент. Значит, он не мог быть передан на предыдущей секунде. Чему тогда равно количество перестановок фрагментов?

Подсказка 6

T(n-1). Проведите аналогичные рассуждения для n-ого фрагмента и выведите формулу для T(n).

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

Пусть передача длилась $n$ секунд. Так как переключение между читающими головками происходит раз в секунду, весь звук можно разбить на $n$ фрагментов по 1 секунде, тогда звук, переданный на линию, будет будет перестановкой этих фрагментов. Обозначим количество возможных перестановок за $T(n).$

Представим весь процесс в виде таблицы, элементами которой являются номера фрагментов. Например, на второй секунде, с которой начинается передача, на пишущей головке будет третий фрагмент звука, второй фрагмент звука будет на второй читающей головке, а первый фрагмент — на третьей. Передача закончится на $(n +1)−$ ой секунде. В этот момент на линию может быть передан $(n− 1)−$ ый или $n−$ ый фрагмент звука. Рассмотрим оба случая:

$PIC$

1.: Пусть в момент времени $n +1$ бы передан $n−$ ый фрагмент. Тогда он не мог быть передан на предыдущей секунде. Если посмотреть на таблицу, становится ясно, что количество перестановок фрагментов в этом случае совпадает с $T (n − 1),$ иначе говоря, количеством способов переставить звук длины $n− 1.$

$PIC$
2.: Пусть в момент времени $n+ 1$ бы передан $(n− 1)−$ ый фрагмент. Тогда он не мог быть передан на предыдущих секундах. Так как $n−$ ый фрагмент должен уйти на линию, он должен быть передан в момент $n.$ Тогда до $(n− 1)−$ ой секунды должно быть передано $n − 2$ последовательных фрагмента, что соотвествует $T(n− 2)$ способам.

$PIC$

Таким образом, $T(n)=T (n − 1)+ T(n − 2).$ Для любого $n,$ чтобы найти $T(n),$ достаточно найти $T(1)$ и $T(2).$ Останется только с использованием формулы $T(n)= T(n − 1)+ T(n− 2)$ вычислить нужное значение.

$PIC$

Ответ:

$10946$

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

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

На столе лежат $130$ различных карточек с числами $502,504,506,...,758,760$ (на каждой карточке написано ровно одно число, каждое число встречается ровно один раз). Сколькими способами можно выбрать $3$ карточки так, чтобы сумма чисел на выбранных карточках делилась на $3?$

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

Подсказка 1

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

Подсказка 2

Да, числа должны давать либо одинаковые остатки, либо наоборот различные(0, 1, 2). Можно ли посчитать, какие остатки при делении на 3 дают числа в условии задачи?

Подсказка 3

Да, можно, так 502 ≡ 1 (mod=3), 504 ≡ 0 (mod=3), 506 ≡ 2(mod=3), …, 760 ≡ 1(mod=3). То есть, по модулю 3: 44 числа сравнимы с единицей, 43 числа сравнимы с двойкой, 43 числа сравнимы с нулем. Как посчитать общее число способов?

Подсказка 4

Выбрать три числа с разными остатками, это просто 43*43*44. А если мы хотим выбрать три числа с одинаковым остатком, то нужно воспользоваться формулой числа сочетаний. И посчитать сумму всех этих способов!

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

Первое решение.

Если мы возьмём три карточки с числами подряд по возрастанию, то среди них будут по одной карточке с остатками $0,1$ и $2$ при делении на $3.$ Значит, среди карточек $502,504,506,...,758$ по $43$ карточки с каждым остатком (разобьём на $43$ тройки подряд идущих) и ещё есть карточка с числом $760,$ которое дает остаток $1.$

Давайте подумаем, какие есть варианты для остатков трёх карточек, чтобы их сумма делилась на $3:$ либо все три числа должны давать разные остатки (способов выбрать так карточки $43 ⋅44⋅43,$ так как выбрать карточку с остатком $0$ — $43$ способа, способов выбрать карточку с остатком $1$ — $44$ и способов выбрать карточку с остатком $2$ — $43$ ), либо все три остатка $0$ (тогда способов $3 C 43),$ либо все три остатка 1 (тогда способов $3 C44),$ либо все три остатка $2$ (тогда способов $3 C43).$ Итого всего

43⋅44⋅43+C343+ C344+ C343 = 81356+ 12341+ 13244+ 12341= 119282

Второе решение.

Данные числа, расположенные в порядке возрастания, образуют арифметическую прогрессию с разностью $2≡3 −1.$ Следовательно, остатки от деления на $3$ у этих чисел чередуются (идут по убыванию с шагом $1,$ то есть $0→ 2→ 1→ 0→ ...$ ).

Среди данных нам чисел есть $44,$ дающие остаток $1$ от деления на $3$ (они образуют множество $A ={502;508;514;...;760}$ ), $43$ числа, делящихся на $3$ (образуют $B = {504;510;516;...;756}$ ) и $43$ числа, дающих остаток $2$ от деления на $3$ ( $C ={506;512;518;...;758}$ ).

Сумма трёх чисел может делиться на $3$ в следующих случаях.

1.: Все три числа дают одинаковые остатки от деления на $3.$ Есть $C344$ способов выбрать $3$ числа из множества $A$ и по $C343$ способов выбрать $3$ числа из множеств $B$ и $C.$ В сумме получаем $44⋅436⋅42+ 2⋅ 43⋅462⋅41-=13244+2 ⋅12341= 37926$ способов.
2.: Если не все остатки одинаковы, то подходит только случай, когда все три остатка разные, т.е. мы должны выбрать по одному числу из каждого из множеств $A,B,C.$ Получаем $44 ⋅43⋅43= 81356$ способов. Если есть два равных остатка, то для кратности их суммы трём третий должен быть таким же.

В сумме выходит $119282$ способов.

Ответ:

$119282$

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

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

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

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

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

Источники: ИТМО 2019

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

Подсказка 1

Обязательно ли нам расставлять именно числа от 1 до 9?

Подсказка 2

Мы можем сначала расставлять 0 и 1, так как нам важна только четность.

Подсказка 3

Какое количество единиц может быть в таблице?

Подсказка 4

Например, четыре нам подойдет. А может ли их быть две или восемь?

Подсказка 5

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

Подсказка 6

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

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

Будем расставлять в таблицу нули и единицы. Каждый $0$ можно поставить четырьмя способами, а $1$ — пятью. Заметим, что в каждой строчке чётное количество единиц, потому единиц суммарно в таблице может быть $0,2,4,6$ ( $8$ быть не может, поскольку в каждой строчке не более двух). Также заметим, что двух единиц быть не может, поскольку тогда бы они стояли в одной строчке и их было бы по одной в столбце. Разберём остальные случаи

Пусть единиц нет. Тогда имеем $9$ чётных чисел и $9 4$ способов в этом случае.
Пусть единиц четыре. Тогда они стоят на пересечении двух строчек и двух столбцов. Выбираем строчки и столбцы $2 2 C 3 ⋅C3 = 9$ способами, в итоге имеем $5 4 9⋅4 ⋅5$ способов.
Пусть единиц шесть. Тогда оставшиеся нули стоят в разных строчках (в каждой строчке и в каждом столбце должно быть ровно по две единицы). Число способов так расставить нули равно $3!=6$ , откуда имеем $6⋅56⋅43$ .

Ответ:

$49+ 9⋅45⋅54 +6⋅56⋅43$

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

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

На столе лежат $100$ различных карточек с числами $3,$ $6,$ $9,$ …, $297,$ $300$ (на каждой карточке написано ровно одно число, каждое число встречается ровно один раз). Сколькими способами можно выбрать $2$ карточки так, чтобы сумма чисел на выбранных карточках делилась на $5?$

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

Подсказка 1

Нам нужно, чтобы сумма делилась на 5, а сколько у нас чисел с различными остатками при делении на 5?

Подсказка 2

О, а их одинаковое количество! А какие случаи нам подходят? Если оба числа делятся на 5 или если одно число дает остаток a, то у второго должен быть остаток (5-a). Разбираемся со случаями по отдельности!

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

Данные числа, расположенные в порядке возрастания, образуют арифметическую прогрессию с разностью 3. Следовательно, остатки от деления на 5 у этих чисел чередуются. Действительно, если какое-то из этих чисел делится на 5, то есть имеет вид $5k$ , где $k∈ℕ$ , то следующее за ним число есть $5k +3$ — и оно даёт остаток 3 от деления на 5 — далее $− 5k +6= 5(k+ 1)+ 1$ , дающее остаток 1 от деления на 5, затем — $5k+9 =5(k+ 1)+ 4$ , дающее остаток 4 от деления на 5 , затем $5k+ 12= 5(k +2)+ 2$ , дающее остаток 4 от деления на 5; наконец, следующим является $5k+ 15= 5(k+ 3)$ , которое снова делится на 5, после чего порядок остатков по чисел на 5 идут в порядке $...;0;3;1;4;2;0...$

Среди данных нам 100 чисел есть по 20 чисел, дающих остатки $0,1,2,3,4$ от деления на 5.

Сумма двух чисел может делиться на 5 в следующих случаях.

1) Оба числа делятся на 5. Всего карточек с такими числами 20 , и нужно выбрать 2 из них — есть $2 1 C20 = 2 ⋅20⋅19= 190$ способов.

сделать это.

2) Одно из чисел даёт остаток 1 от деления на 5 — тогда второе должно давать остаток 4 от деления на 5. Эту пару чисел можно выбрать $20⋅20= 400$ способами.

3) Одно из чисел даёт остаток 2 от деления на 5 — тогда второе даёт остаток 3 , и, аналогично второму случаю, получаем 400 способов выорать 2 числа. В итоге выходит 990 способов.

Ответ: 990

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

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

На каждой из прямых $y =1$ и $y =6$ отмечено по $200$ точек с абсциссами $1,2,3,...,200.$ Сколькими способами можно выбрать три точки из отмеченных $400$ так, чтобы они являлись вершинами прямоугольного треугольника?

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Конечно, можно сначала посмотреть на другой катет, который перпендикулярен обеим прямым. То есть, нам надо выбрать абсциссу(200 способов), а потом точку на одной из прямых. Этих точек осталось 200*2-2=199*2. Значит всего способов в этом случае 400*199. Но это первый случай. А как свести к перебору второй случай, когда гипотенуза лежит на одной из прямых? Какой отрезок в таком треугольнике точно известен? Что он дает?

Подсказка 4

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

Подсказка 5

Действительно, либо 1 и 25 либо 5 и 5. Теперь подумаем, как нам посчитать каждый из способов. В первом случае мы должны учесть порядок проекций. То есть сначала идет отрезок длиной 1, а потом 25 или наоборот. Плюсом, учесть прямую на которой располагается гипотенуза. Плюсом, учесть, что гипотенуза не должна выходить за крайние точки на прямых. Во втором же случае порядок нам не важен, так как отрезки проекций катетов равны, а все остальное важно. Остается посчитать это, сложить с первым случаем(когда катет лежит на одной из прямых) и получить ответ.

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

Первое решение.

Треугольники делятся на два типа

Катеты параллельны осям. Тогда один из них соединяет точки с одинаковой абсциссой, а второй лежит на какой-то прямой. Выберем эту абсциссу $200$ способами, а затем прямую и саму точку $2⋅199$ способами (сначала прямую, а затем точку из оставшихся $199$ на ней). В итоге $400⋅199$ способов.
Ни один из катетов не лежит на прямых, поэтому там лежит гипотенуза (ведь на какой-то прямой лежат две вершины треугольника), откуда высота к ней имеет длину $5$ . Она же является корнем из произведения проекций катетов, то есть их произведение равно $25 =5⋅5 =1⋅25$ — длины проекций являются натуральными числами, потому их значения могут быть только такими. Если это $1$ и $25$ , то, выбирая прямую, затем порядок двух различных отрезков проекций на прямой, а затем абсциссу высоты, получаем $2⋅2⋅174$ способа (поскольку мы не можем брать $25$ ближайших точек с одной стороны прямой, а с другой одну, чтобы наши проекции “влезли”). Если же это $5$ и $5$ , то сначала выбираем прямую, порядок выбирать не нужно, поскольку отрезки равны, а точку выберем $190$ способами, поскольку с каждой стороны прямой нельзя брать по $5$ точек. В итоге $190⋅2+ 174⋅4$ способа.

В качестве ответа имеем $400⋅199+190⋅2+ 174 ⋅4 =80676$ .

Второе решение.

Рассмотрим два возможных случая:

Гипотенуза треугольника лежит на одной из прямых, а вершина прямого угла - на второй прямой. Пусть $ABC$ - данный треугольник с прямым углом при вершине $C,CH$ - его высота, опущенная на гипотенузу. Из пропорциональности отрезков прямоугольного треугольника получаем, что $2 CH = AH ⋅BH$ , т.e. $AH ⋅BH =25$ . Поскольку $AH$ и $BH$ - целые числа, то возможны следующие случаи: $AH =BH = 5,AH = 25$ и $BH = 1,AH =1$ и $BH =25$ .
В первом из этих случаев гипотенузу $AB$ , равную 10, можно расположить $190⋅2= 380$ способами (по $200 − 10$ способов расположения на каждой из двух данных прямых), при этом положение вершины $C$ определяется однозначно.
Во втором и третьем случаях длина гипотенузы равна 26, и её можно расположить $2(200−$ $26)= 348$ способами. Для каждого положения гипотенузы существует два способа размещения вершины - получаем $2⋅348= 696$ способов.
Один из катетов треугольника (назовём его $BC$ ) перпендикулярен данным прямым, а второй катет $(AC )$ лежит на одной из данных прямых. Тогда положение катета $BC$ можно выбрать 200 способами. Для каждого варианта расположения катета $BC$ вершину $A$ можно расположить 398 способами (подходят все точки кроме уже выбранных $B$ и $C$ ) - всего выходит $200⋅398=79600$ способов.

Итого получаем $380+696+ 79600= 80676$ способов.

Ответ:

$80676$

Критерии оценки

Доказано, какие три вида прямоугольных треугольников возможны — 2 балла.

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

Произведён подсчёт количества треугольников одного вида — 1 балл.

Произведён подсчёт количества треугольников двух видов — 2 балла.

Произведён подсчёт количества треугольников трёх видов — 4 балла.

Ошибка в $\pm 1$ при подсчёте количества треугольников — снять 1 балл от общей суммы.

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

Верный ответ в развёрнутой форме — баллы не снимаются.

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

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

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

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

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

Подсказка 1

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

Подсказка 2

Верно, карточек каждого вида по 21 и в пару мы выберем такую же, для сохранения делимости. Получаем, что в каждом виде таких пар будет 21*20/2. Дальше видим, что у нас не очень удачно выбрано ограничение по числам. Давайте сразу разберёмся с карточками с 2101 до 2117. Подумайте над тем, какие числа снова можно подобрать к ним в пару и сколько их?

Подсказка 3

Точно, их тоже по 21 штуке для каждой. То есть количество таких пар будет равно 17*21. Остались карточки с 1 до 2099 и уже можно увидеть какие пары нам нужны. То есть в пару к 01 мы берём 99, к паре 02 - 98 и так далее до 49 и 51. Осталось только понять, сколько для выбранного первого числа есть второе в пару. И умножить это количество выборов первого числа!

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

Будем называть парной карточкой к данной такую карточку, что их сумма кратна $100$ , а видом карточки — её последние две цифры. Рассмотрим несколько случаев

Номер на карточке кратен $50$ , то есть заканчивается на $50$ или $00$ . Карточек каждого вида ровно по $21$ , а парная карточка к каждой из них заканчивается на те же самые две цифры. То есть для обоих видов мы получим по $C2 21$ способов взять две парные карточки с такими последними цифрами. Всего $21 ⋅20= 420$ .
Номер карточки заканчивается на $01,02...49$ , при этом он не больше $2100$ . В силу второго ограничения таких карточек тоже по $21$ каждого вида. Легко видеть, что в пару им идут виды $51,52...99$ , по одному на каждый, то есть для каждой выбранной карточки подойдёт $21$ карточка парного вида. Итак, выбираем вид $49$ способами, затем его представителя $21$ и пару ему также $21$ , итого $2 21 ⋅49$ .
Остались карточки с номерами $2101,...2117$ . Для каждой из них есть по $21$ парной, то есть получаем $17⋅21$ способов.

Складывая по всем случаям, получаем $420+ 212⋅49+ 17⋅21 =22386$ способов.

Ответ:

$22386$