Сколько существует четных пятизначных чисел с произведением цифр 20

Сколько существует четных пятизначных чисел с произведением цифр 20

Пошаговое объяснение:

Общее количество пятизначных чисел по правилу произведения равно 9 · 10 · 10 · 10 · 10 = 90000 (в старшем разряде не может стоять нуль). Из пяти нечетных цифр 1, 3, 5, 7, 9 можно составить 5 · 5 · 5 · 5 · 5 = 3125 пятизначных чисел, состоящих только из нечетных цифр. Это и есть «ненужные» варианты.

Задачи по комбинаторике. Часть 1

В этой статье использован материал из лекций Шарича Владимира Златковича и Максимова Дмитрия Васильевича на КПК foxford.

Очень рекомендую абитуриентам курсы foxford для подготовки к ЕГЭ и олимпиадам.

1. Сколько четырехзначных чисел содержит ровно одну семерку?

Четырехзначное число имеет вид . Если четырехзначное число содержит ровно одну семерку, то она может стоять

1) на первом месте, и тогда на остальных трех местах могут стоять любые цифры от 0 до 9, кроме цифры 7, и по правилу произведения мы получаем четырехзначных чисел, у которых семерка стоит на первом месте.

2) на любом месте, кроме первого, и тогда по правилу произведения мы получаем . У нас три возможности расположения цифры 7, на первом месте может стоять 8 цифр (все цифры, кроме нуля и 7), на тех местах, где не стоит цифра 7 — 9 цифр.

Сложим полученные варианты, и получим четырехзначных чисел, содержащих ровно одну семерку.

2. Сколько пятизначных чисел содержит ровно две семерки?

Так же как в предыдущей задаче у нас две возможности:

1) Одна из семерок стоит на первом месте, а вторая на любом из оставшихся четырех мест. На трех местах, не занятых цифрой 7 может стоять любая из 9 цифр (все, кроме цифры 7). В этом случае мы получаем чисел.

2) Ни одна из семерок не стоит на первом месте. В этом случае мы имеем возможностей расставить 2 семерки на оставшихся 4-х местах. У нас осталось 3 места, не занятых цифрой 7, одно из которых первое, и таким образом мы получаем чисел.

Сложим полученные варианты, и получим пятизначных чисел, содержащих ровно две семерки.

3. Сколько существует пятизначных чисел, цифры которых различны и расположены в порядке возрастания?

Так как первой цифрой не может быть 0, рассмотрим последовательность цифр 1-9, расположенных в порядке возрастания.

1, 2, 3, 4, 5, 6, 7, 8, 9

Если мы выберем из этой последовательности 5 произвольных цифр, например так:

1, 2 , 3, 4 , 5, 6, 7 , 8 , 9

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

Осталось посчитать, сколькими способами мы можем выбрать из 9 цифр 5:

Итак существует 126 пятизначных чисел, цифры которых различны и расположены в порядке возрастания.

Треугольник Паскаля и число сочетаний.

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

Посчитаем, для каждой клетки, сколькими способами король может до нее добраться.

Так как король может двигаться только вправо и вниз, до любой клетки первого столбца и первой строки он может добраться единственным способом:

Рассмотрим произвольную клетку доски. Если в клетку, стоящую над ней можно добраться способами, а в клетку, стоящую слева от нее способами, то в саму клетку можно добраться способами (это следует из того, что король может двигаться только вправо и вниз, то есть не может дважды зайти на одну клетку):

Заполним начальные клетки, пользуясь этим правилом:

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

Число в каждой клетке показывает, сколькими способами король может попасть в эту клетку из левой верхней.

Например, чтобы попасть в клетку (4;3) — четвертая строка, третий столбец, король должен сделать 4-1=3 шага вправо, и 3-1=2 шага вниз. То есть всего 3+2=5 шагов. Нам нужно найти число возможных последовательностей этих шагов:

То есть найти, скольким способами мы можем расположить 2 вертикальные (или 3 горизонтальные) стрелки на 5-ти местах. Число способов равно:

— то есть ровно то число, которое стоит в этой клетке.

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

Можно получить рекуррентное соотношение для числа сочетаний:

Смысл этого соотношения следующий. Путь у нас есть множество, состоящее из n элементов. И нам нужно выбрать из этого множества l элементов. Все способы, которыми мы можем это сделать делятся на две группы, которые не пересекаются. Мы можем:

а) зафиксировать один элемент, и из оставшихся n-1-го элемента выбрать l-1 элемент. Это можно сделать способами.

б) выбрать из оставшихся n-1-го элемента все l элементов. Это можно сделать способами.

Также можно получить соотношение:

Действительно, левая часть этого равенства показывает число способов выбрать какое-то подмножество из множества, содержащего n элементов. (Подмножество, содержащее 0 элементов, 1 элемент и так далее.) Если мы пронумеруем n элементов, то получим цепочку из n нулей и единиц, в которой 0 означает, что данные элемент не выбран, а 1 — что выбран. Всего таких комбинаций, состоящих из нулей и единиц .

Кроме того, число подмножеств с четным числом элементов равно числу подмножеств с нечетным числом элементов:

Докажем это соотношение. Для этого докажем, что между подмножествами с четным числом элементов и подмножествами с нечетным числом элементов существует взаимно однозначное соответствие.

Зафиксируем один элемент множества:

Теперь возьмем произвольное подмножество, и если оно не содержит этот элемент, то поставим ему в соответствие подмножество, состоящее из тех же элементов, что и выбранное, плюс этот элемент. А если выбранное подмножество уже содержит это элемент, то поставим ему в соответствие подмножество, состоящее из тех же элементов, что и выбранное, минус этот элемент. Очевидно, что из этих пар подмножеств одно содержит четное число элементов, а другое — нечетное.

5. Рассмотрим выражение

1. Сколько слагаемых имеет этот многочлен?

а) до приведения подобных членов

б) после приведения подобных членов.

2. Найти коэффициент при произведении

При возведении суммы слагаемых в степень , мы должны эту сумму умножить на себя раз. Мы получаем сумму одночленов, степень каждого из которых равна m. Число всевозможных произведений, состоящих из переменных из множества с учетом порядка и возможностью повторения равно числу размещений с повторениями из k по m:

Когда мы приводим подобные члены, мы считаем одинаковыми произведения, содержащие равное число множителей каждого вида. В этом случае, чтобы найти число слагаемых многочлена после приведения подобных членов, мы должны найти число сочетаний с повторениями из k по m:

Найдем коэффициент при произведении .

Выражение представляет собой произведение m элементов из множества , причем элемент взят раз, элемент взят раз, и так далее, и, наконец, элемент взят раз. Коэффициент при произведении равен числу возможных произведений:

Рассмотрим частный случай: — Бином Ньютона. И получим формулу для биномиальных коэффициентов.

Произвольный член многочлена, полученного возведением двучлена в степень имеет вид , где А — биномиальный коэффициент, . Как мы уже получили,

Тогда если мы положим х=1 и y=1, то получим, что

6. Задача про кузнечика.

Есть n клеточек, расположенных последовательно. Кузнечик должен попасть из крайней левой клеточки в крайнюю правую, прыгая вправо на произвольное число клеток.

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

Изобразим условие задачи:

Кузнечик может попасть в крайнюю правую клетку, побывав, или не побывав в любой внутренней клетке. Присвоим клетке значение 1, если кузнечик в ней побывал, и 0, если нет, например, так:

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

б) сколькими способами кузнечик может добраться в n-ю клетку, сделав k шагов?

Чтобы попасть в n-ю клетку, сделав k шагов, кузнечик должен попасть ровно в k—1 клетку между первой и последней. Так как последний шаг он делает всегда в последнюю клетку. То есть стоит вопрос, сколькими способами можно выбрать k—1 клетку из n-2 клеток?

Ответ: .

в) сколькими способами кузнечик может добраться в n-ю клетку, двигаясь на одну или на две клетки вправо?

Распишем, сколькими способами можно попасть в каждую клетку.

В первую и вторую клетки можно попасть единственным способом: в первую — никуда из нее не уходя, и во вторую из первой:

В третью можно попасть из первой или второй, то есть двумя способами:

В четвертую — из второй или третьей, то есть 1+2=3 способами:

В пятую — из третьей или четвертой, то есть 2+3=5 способами: Можно заметить закономерность: чтобы найти число способов, которыми кузнечик может попасть в клетку с номером k нужно сложить число способов, которыми кузнечик может попасть в две предыдущие клетки:

Мы получили интересную последовательность чисел — числа Фибоначчи — это линейная рекуррентная последовательность натуральных чисел, где первое и второе равно единице, а каждое последующее — сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377.

ДМ / Diskret_mat2

Запишем выражение в развернутом виде и в числителе вынесем за скобки 1 2 3 . ( n − 2) 1 2 3 . ( n − 2) .

Сократим его со знаменателем , тогда получим :

K = n 4 – 2 n 3 + n 2 + n –1.

1. Запишите следующие произведения с использова —

нием знака факториала :

(2 П 2) 1·3·4·6·7·8·9·10;

(8 РЕ ) 1·2·3·…·( n – 4)( n – 3);

(2 Я . РЕ ) 1·2·2·3·…· n ;

(485) 1·2·3·…· n ( n + 1);

( АМИ ) 1·2·3·…·( n –1)( n +1) n ;

2. Упростите и результат запишите с использованием

1 2 3 . n ( n +1)( n + 2)

1 2 2 3 3 4 5 . ( k −1) k 2

[ 1 2 3 . ( k −1) ] k 2

1 2 3 . ( k − 2) ( k −1) 2

1 2 3 . ( k −1)( k +1)

1 2 3 . ( k −1)( k +1)

1 2 3 . k +1 2 3 . ( k +1)

1 2 3 . ( k − 2)( k +1)

4. Вычислите при n = 31:

n ! ( n − 1)! ( n + 1)! n

5. Найдите значение функции при n = 2:

( Т 5 К ) f = ( n –3)!( n –2)( n –1) n .

6. ( ТОТ ). Какими цифрами не может оканчиваться число n !?

7. ( ЯШТ ). Какими цифрами может оканчиваться

число n ! при n > 3?

В общем случае если один элемент множества А 1 мож — но выбрать | A 1 | способами , элемент множества А 2 – | A 2 | способами и так далее до множества А n , один элемент ко — торого можно выбрать | A n | способами , то выбрать n эле — ментов в заданном порядке можно N способами , где

N = | A 1 | · | A 2 | ·…· | A n |.

Пример 1 . Пусть А = <1,2,3,4,5>. Один элемент из этого множества можно выбрать n = 5 способами . Останется четыре элемента . Один элемент из них можно выбрать m = 4 способами . Следовательно , выбор двух элементов возможен 5·4 = 20 способами , список которых имеет вид : 12, 13, 14, 15, 21, 23, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54.

Заметим , что в каждой выборке цифры разные . Пример 2 . В урне пять шаров с номерами 1, 2, 3, 4, 5.

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

На первом месте может стоять одна из пяти цифр , т . е . n = 5. На втором месте – также одна из пяти цифр . Следо — вательно , m = 5. Тогда искомое число nm = 5·5 = 25. Среди всех этих 25 выборок ( в отличие от предыдущего примера ) существуют пары с одинаковыми цифрами .

Пример 3 . Вернемся к примеру 2. Пусть шары извле — кают три раза . Сколько получится трехзначных чисел ?

На первом месте может стоять одна из пяти цифр , на втором – также одна из пяти , и на третьем – одна из пяти . Следовательно , число выборок равно 5·5·5 = 125.

Пример 4 . Сколько существует трехразрядных шесте — ричных чисел ?

В шестеричной системе счисления используются цифры 0,1,2,3,4,5. Первую цифру можно выбрать пятью способами , поскольку нуль не используем , так как число , начинающееся с нуля , не является трехразрядным . Вторая цифра может быть любой , в том числе и нулем , следо — вательно , ее можно выбрать шестью способами . То же самое относится и к цифре младшего разряда . Искомое число равно 5·6·6 = 180.

Пример 5 . Сколько существует пятизначных сим — метричных восьмеричных чисел , то есть таких чисел , которые одинаково читаются как слева направо , так и справа налево , например : 23032, 55655, 10001 и т . д .?

Первую цифру ( старшего разряда ) можно выбрать 7 способами , так как с нуля пятизначные числа начинать — ся не могут . Вторую цифру можно выбрать 8 способа — ми , поскольку теперь можно использовать и нуль . Для выбора третьей цифры также существует 8 вариантов . Цифры двух младших разрядов не имеют вариантов для выбора . Они должны повторять первые две цифры . Например , если выбраны цифры 372, то следующей может быть только цифра 7, а после нее – только цифра 3. Таким образом , всего существует 7·8·8 = 448 искомых чисел .

1.2. Правило произведения

Если один элемент множества А может быть вы — бран n способами , а после него второй элемент – m способами , то выбор того и другого элемента в за —

данном порядке может быть осуществлен N способами

1. ( ДЕЗ ). Имеется 10 карточек . На каждой записана гласная буква . Выбирают наугад карточку и к ней справа приставляют вторую , наугад выбранную после первой . Сколько возможно таких двухбуквенных слов ?

2. ( ТР 2). Сколько трехразрядных чисел можно обра — зовать из цифр 3, 4, 5, 6?

3. ( АКИ ). Сколько семизначных чисел можно обра — зовать из цифр 3, 7, 9?

4. ( АРМ ). Из пятизначных десятичных чисел удали — ли все числа , в которые входит хотя бы одна из цифр 0, 3, 7, 8, 9. Сколько чисел осталось ?

5. ( КЭФ )! Город А связан с городом В шестью дорогами . Сколькими способами житель города А может посетить город В , если возврат возможен по той же дороге , что и поездка в город В ? Сколькими способами житель города В может посетить город А , если поездка туда и обратно осуществляется по разным дорогам ?

6. ( УФ 5). Сколько четырехзначных чисел можно со — ставить из цифр 0, 1, 2, 3, 4, 5, если ни одна из цифр не повторяется в числе более одного раза ?

7. (927). Сколько трехзначных чисел можно соста — вить из цифр 1, 2, 3, 4, 5, если цифра младшего разряда каждого числа является четной , а старшего – не — четной ?

8. (296). Сколько существует пятизначных десятич — ных чисел , которые делятся на 5?

9. ( ХТБ ). Сколько существует пятиразрядных сим — метричных десятичных чисел ( которые одинаково читаются как справа налево , так и слева направо ,

например , 39793; 68286)?

10. ( УМС ). Старший разряд двузначного числа неко — торой системы счисления может содержать одну цифру из 7, младший разряд – одну цифру из х . Всего таких чисел существует 84. Найдите х ( десятичное число ).

11. ( ААТ ). Сколько существует трехразрядных семе — ричных чисел , оканчивающихся нечетной цифрой ?

12. ( ОРМ )! Сколько существует трехразрядных деся — тичных чисел , у которых :

– в старшем разряде нет ни одной из цифр 1,2,3,4,5;

– в среднем разряде нет цифр 2,5,7;

– в младшем разряде нет четных цифр и нет цифры 1?

1.3. Правило суммы в комбинаторике

Пусть даны множества Р 1 и Р 2 . Выясним , сколько эле — ментов содержится во множестве Р 1 U Р 2 . Эта задача не

так примитивна , как может показаться на первый взгляд . Она проста только при Р 1 I Р 2 = . В этом случае

| Р 1 U Р 2 | = | Р 1 | + | Р 2 | ,

т . е . если элемент множества Р 1 может быть выбран | Р 1 | способами , а элемент множества Р 2 – | Р 2 | способами , то выбор « либо элемент множества Р 1 , либо элемент мно — жества Р 2 » может быть осуществлен | Р 1 | + | Р 2 | способами .

Это и есть правило суммы [12, с . 250].

Пример 1 . В тарелке лежат 6 яблок и 4 груши . Сколь — кими способами можно выбрать один плод [9, с . 21]?

Если Р 1 – множество яблок , Р 2 – множество груш , то :

| Р 1 U Р 2 | = | Р 1 | + | Р 2 | = 6 + 4 = 10.

Рассмотрим случай , когда Р 1 I Р 2 ≠ Ø. Правило суммы при этом имеет вид :

| Р 1 U Р 2 | = | Р 1 | + | Р 2 | – | Р 1 I Р 2 |.

В [35, с . 140] эту формулу называют формулой вклю — чений и исключений , а в [56, с . 32] используется термин « принцип включения — исключения ». В [42, с . 140] ее на — зывают частным случаем формулы перекрытий .

Пример 2 . Пусть даны множества :

Сколько элементов во множестве Р 1 U Р 2 ? По правилу суммы | Р 1 U Р 2 | = 5 + 5 – 2 = 8.

В случае трех множеств правило суммы имеет вид

| Р 1 U Р 2 U Р 3 | = | Р 1 U Р 2 | + | Р 3 | – |( Р 1 U Р 2 ) I Р 3 | = | Р 1 | + + | Р 2 | – | Р 1 I Р 2 | + | Р 3 | – | Р 1 I Р 3 U Р 2 I Р 3 | = | Р 1 | + | Р 2 | –

– | Р 1 I Р 2 | + | Р 3 | – (| Р 1 I Р 3 | + | Р 2 I Р 3 | – | Р 1 I Р 2 I Р 3 |) = | Р 1 | +

+ | Р 2 | + | Р 3 | – | Р 1 I Р 2 | – | Р 1 I Р 3 | – | Р 2 I Р 3 | + | Р 1 I Р 2 I Р 3 |.

Для четырех множеств получаем аналогично :

| Р 1 U Р 2 U Р 3 U Р 4 | = | Р 1 | + | Р 2 | + | Р 3 | + | Р 4 | – | Р 1 I Р 2 | –

– | Р 1 I Р 3 | – | Р 1 I Р 4 | – | Р 2 I Р 3 | – | Р 2 I Р 4 | – | Р 3 I Р 4 | +

+ | Р 1 I Р 2 I Р 3 | + | Р 1 I Р 2 I Р 4 | + | Р 1 I Р 3 I Р 4 | + | Р 2 I Р 3 I Р 4 | –

– | Р 1 I Р 2 I Р 3 I Р 4 |.

В случае n множеств сумма имеет вид

| Р 1 U Р 2 U … U Р n | = | Р 1 |+| Р 2 |+…+| Р n | – (| Р 1 I Р 2 |+| Р 1 I Р 3 |+

…+| Р n –1 I Р n |)+(| Р 1 I Р 2 I Р 3 |+| Р 1 I Р 2 I Р 4 |+ …+| Р n –2 I Р n –1 I Р n |)–…+(–1) n– 1 | Р 1 I Р 2 I … I Р n |.

Пример 3 . Из 100 студентов английский язык знают 28 человек , немецкий – 30, французский – 42, английский и немецкий – 8, английский и французский – 10, немецкий и французский – 5, все три языка знают 3 че — ловека . Сколько студентов не знают ни одного ино — странного языка [22, с . 15]?

Обозначим : | Р 1 | – число студентов , знающих английс — кий язык ; | Р 2 | – знающих немецкий язык ; | Р 3 | – знающих французский язык . | P 1 | = 28; | P 2 | = 30; | P 3 | = 42.

| Р 1 I Р 2 | = 8 – число студентов , знающих два языка – английский и немецкий ;

| Р 1 I Р 3 | = 10 – число студентов , знающих два языка – английский и французский ;

| Р 2 I Р 3 | = 5 – число студентов , знающих два языка – немецкий и французский ;

| Р 1 I Р 2 I Р 3 | = 3 – число студентов , знающих три языка . По правилу суммы :

| Р 1 U Р 2 U Р 3 | = 28 + 30 + 42 – 8 – 10 – 5 + 3 = 80.

Таким образом , знают хотя бы один иностранный язык 80 студентов , следовательно , ни одного иностран — ного языка не знают 20 человек .

1. ( ОМН ). 30 учащихся сдавали экзамен по физике

и химии . По две отличные оценки получили 9 человек . На « отлично » физику сдали 12 человек , химию – 16. Ско — лько учащихся не получили ни одной отличной оценки ?

2. ( МОК ). 12 туристов взяли с собой по коробке спичек , 19 туристов – по зажигалке . Ни спичек , ни зажигалок не взяли 6 человек . Всего в отряде 27 человек . Сколько человек взяли с собой и спички и зажигалки ?

3. ( ОМТ ). Из 33 учащихся физический кружок посе — щают 11 человек . Из них 4 человека посещают еще и химический кружок . Ни физический , ни химический кружок не посещают 8 человек . Сколько человек посе — щают только химический кружок ?