Кружок 5 класса

Руководители Дмитрий Владимирович Трущин и Михаил Владимирович Шеблаев
2012/2013 учебный год

Комбинаторика (17 ноября 2012 года)

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

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

Указание 2. В пункте б) рассмотрите 3 разных случая в зависимости от количества клеток, на которые можно поставить второго короля.

Решение.

а) Поставим сначала чёрную ладью. Это можно сделать 8 · 8 = 64 способами. Чтобы белая ладья её не била, надо поставить её в другие горизонталь и вертикаль, то есть свободных для неё горизонталей будет 8 - 1 = 7, и вертикалей тоже 8 - 1 = 7. То есть, поставить белую ладью при уже поставленной чёрной можно 7 · 7 = 49 способами. Так как на каждый из 64 способов поставить чёрную ладью будет 49 способов поставить белую, то всего способов поставить обе будет 64 · 49 = 3136.

б) Поставим сначала чёрного короля. Сколько способов тогда останется для постановки белого? Рассмотрим разные случаи:

Если чёрный король стоит в углу доски, то белого нельзя ставить на 4 клетки, то есть можно поставить на одну из 8·8 - 4 = 60 клеток. Углов в доске 4, то есть таких случаев, когда чёрный король стоит в углу, а белый его не бьёт, 4 · 60 = 240.

Дальше, если чёрный король стоит с краю доски (не в углу), то белого нельзя ставить на 6 клеток, то есть можно ставить на 64 - 6 = 58 клеток. На каждой из 4 сторон доски есть 8 - 2 = 6 клеток, где чёрный король будет стоять с краю, но не в углу, то есть всего таких вариантов растановки обоих королей будет 4 · 6 · 58 = 1392.

Задача 4. Сколько существует двузначных четных чисел с разными цифрами?

Решение. Пусть α = α1 α2 − двузначное четное число, у которого все цифры различны. Тогда α2 {0,2,4,6,8} ,а α 1 {1, 2, 3, 4, 5, 6, 7, 8, 9} \ {α 2 }.

Если α1 − нечетная цифра, т.е. α1 {1, 3, 5, 7, 9}, получаем, что первая цифра α1 может быть выбрана 5 способами.

При каждом выборе первой цифры α1 , вторая цифра α2 может быть выбрана 5 способами.

По правилу произведения получим, что существуют 5 5 = 25 двузначных четных чисел, у которых первая цифра нечетная.

Если α1 − четная цифра, тогда α1 {2, 4, 6, 8}, а α 2 {0, 2, 4, 6, 8} \ {α 1 }, т.е. элемент α2 может быть выбран 4 способами.

По правилу произведения, число α может быть выбрано 4 4 = 16 способами.

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

Решение. Пусть А ={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} – множество цифр, α= α1 α2 α3 α4 − четырехзначное число, где α1 A\{0},

α4 {0,5}\{α1 },α2 A\{α1 ,α4 },α3 A\{α1 ,α2 ,α4 }.

Если α4 =0, тогда цифра α1 может быть выбрана 9 способами, цифра α2 может быть выбрана 8 способами, а α3 – 7 способами. По правилу произведения получаем, что число

α может быть получено 9 8 7 = 504 способами. Если α 4 =5, тогда α1 A\{0, 5 }, т.е. цифра α1 может быть

выбрана 8 способами, цифра α2 может быть выбрана также 8 способами, а α3 – 7 способами. По правилу произведения

получаем, что число α может быть выбрано 8 8 7=448 способами.

Таким образом, используя правило суммы, получаем, что существует 504 + 448 = 952 четырехзначных чисел, делящихся на 5, у которых все цифры различные.

Эту же задачу можно решить другим способом.

Рассмотрим четное двузначное число α = α1 α2 , где α1 {1, 2, 3, 4, 5, 6, 7, 8, 9}, а α 2 {0, 2, 4, 6, 8}.

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

1. Сколько анаграмм имеет слово КЛАСС?

Трудность в том, что в этом слове две одинаковые буквы С. Будем временно считать их разными и обозначим С 1 и С 2 . Тогда число анаграмм окажется равным 5! = 120. Но те слова, которые отличаются друг из друга лишь перестановкой букв С 1 и С 2 , на самом-то деле являются одной и той же анаграммой! Поэтому 120 анаграмм разбиваются на пары одинаковых, т.е. искомое число анаграмм равно 120/2 = 60.

2. Сколько анаграмм имеет слово ШАРАДА?

Считая три буквы А различными буквами А 1 , А 2 , А 3 , получим 6! анаграмм. Но слова, которые получаются друг из друга только перестановкой букв А 1 , А 2 , А 3 , на самом деле являются одной и той же анаграммой. Поскольку имеется 3! перестановок букв А 1 , А 2 , А 3 , полученные изначально 6! анаграмм разбиваются на группы по 3! одинаковых, и число различных анаграмм оказывается равным 6!/3! = 120.

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

Найдем количество «ненужных» четырехзначных чисел, в записи которых присутствуют только нечетные цифры. Таких чисел 5 4 = 625. Но всего четырехзначных чисел 9000, поэтому искомое количество «нужных» чисел равно 9000 – 625 = 8375.

1. Найти число анаграмм у слов ВЕРЕСК, БАЛАГАН, ГОРОДОВОЙ.
2. Найти число анаграмм у слов БАОБАБ, БАЛЛАДА, ПЕРЕПОЛОХ, АНАГРАММА, МАТЕМАТИКА, КОМБИНАТОРИКА, ОБОРОНОСПОСОБНОСТЬ.
3. Сколькими способами можно поселить 7 приезжих в три гостиничных номера: одноместный, двухместный и четырехместный?
4. В холодильнике лежат два яблока, три груши и четыре апельсина. Каждый день в течение девяти дней подряд Пете дают один какой-то фрукт. Сколькими способами это может быть сделано?
5. Из семи лучших лыжников школы нужно отобрать команду из трех человек для участия в городских соревнованиях. Сколькими способами это можно сделать?
6. Перед экзаменом профессор пообещал поставить двойки половине экзаменуемых. На экзамен пришло 20 студентов. Сколькими способами он может выполнить обещание?
7. Сколько слов можно составить из пяти букв А и не более чем из трех букв Б?
8. В продаже есть шоколадное, клубничное и молочное мороженое. Сколькими способами можно купить три мороженых?
9. При приготовлении пиццы к сыру добавляются разные компоненты, обеспечивающие тот или иной вкус. В распоряжении Билла имеются лук, грибы, помидоры, перец и анчоусы, причем все это, по его мнению, можно добавлять к сыру. Сколько видов пиццы может приготовить Билл?
10. Свидетель криминальной разборки запомнил, что преступники скрылись на «мерседесе», номер которого содержал буквы Т, З, У и цифры 3 и 7 (номером является строка, в которой сначала идут три буквы, а затем - три цифры). Сколько существует таких номеров?
11. Сколько диагоналей в выпуклом n -угольнике?
12. Сколько всего существует n -значных чисел?
13. Сколько существует десятизначных чисел, в записи которых есть хотя бы две одинаковые цифры?
14. Кубик бросают трижды. Среди всевозможных последовательностей результатов есть такие, в которых хотя бы один раз выпала шестерка. Сколько их?
15. Сколько пятизначных чисел имеют в своей записи цифру 1?
16. Сколькими способами можно расставить на шахматной доске белого и черного короля так, чтобы они не били друг друга?
17. Сколько делителей у числа 10800?

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

Решение:

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

Вариантов

2) предположим, что первая цифра выбрана; независимо от нее на втором месте может стоять любая из четных цифр – 0, 2, 4, 6 или 8, всего 5 вариантов:

Вариантов

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

Вариантов

4) общее количество комбинаций равно произведению

4·5·5·5 = 500

5) таким образом, правильный ответ – 3.

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

Решение:

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

Вариантов

2) предположим, что первая цифра x выбрана; на втором месте может стоять любая цифра y , кроме x , всего 9 вариантов (ноль тоже может быть!):

Вариантов

3) третья цифра z может быть любой, кроме тех двух, которые уже стоят на первых двух местах, всего 8 вариантов:

Вариантов

4) наконец, четвертая цифра может быть любой из 7 оставшихся (не равных x , y и z )

Вариантов

5) общее количество комбинаций равно произведению

9·9·8·7 = 4536

6) таким образом, правильный ответ – 2.

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

Решение:

1) возможны три случая: 99··, ·99· и ··99, где жирная точка обозначает некоторую цифру, не равную 9

2) для каждого из этих случаев нужно подсчитать количество вариантов и эти числа сложить

3) в варианте 99·· две последних цифры могут быть любыми, кроме девятки (по 9 вариантов выбора):

Вариантов

поэтому всего получаем 1·1·9·9 = 81 вариант

4) в варианте ·99· первая цифра не может быть нулем и девяткой (остается 8 вариантов), а последняя может быть любой, кроме девятки (9 вариантов):

Вариантов

поэтому всего получаем 8·1·1·9 = 72 варианта

5) в варианте ··99 первая цифра не может быть нулем и девяткой (остается 8 вариантов), а последняя может быть любой, кроме девятки (9 вариантов):

Вариантов

поэтому всего получаем 8·9·1·1 = 72 варианта

6) общее количество вариантов равно сумме

81 + 72 + 72 = 225

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

Решение:

1) обозначим первую цифру через x , она не может быть нулем, поэтому возможно 9 вариантов выбора

Вариантов

2) другую цифру обозначим через y , ее тоже можно выбирать 9 способами (она может быть нулем, но не может быть равна x )

3) нужно отдельно рассмотреть три случая: xy ··, xxy · и xxx ·; для каждого из этих случаев нужно подсчитать количество вариантов и эти числа сложить

4) в варианте xy ·· две последних цифры могут быть (независимо друг от друга) выбраны равными x или y (по 2 варианта выбора):

			x или y	x или y
Вариантов

поэтому всего получаем 9·9·2·2 = 324 варианта

5) в варианте xxy · последняя цифра может быть равна только x или y (2 варианта):

				x или y
Вариантов

поэтому всего получаем 9·1·9·2 = 162 варианта

6) в варианте xxx · последняя цифра может быть любой (10 вариантов):

				x или y
Вариантов

поэтому всего получаем 9·1·1·10 = 90 вариантов

7) общее количество вариантов равно сумме

324 + 162 + 90 = 576

8) таким образом, правильный ответ – 3.

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

Решение (вариант 1):

1) рассмотрим четыре варианта: 5···, ·5··, ··5· и ···5; для каждого из этих случаев нужно подсчитать количество уникальных вариантов (исключив все общие!) и эти числа сложить

2) в случае 5··· три последних цифры могут быть любыми нечетными (по 5 независимых вариантов выбора):

Вариантов

поэтому всего получаем 1·5·5·5 = 125 вариантов

3) с первого взгляда для случая ·5·· ситуация та же самая, но это не так; дело в том, что часть этих вариантов (с пятеркой на первом месте) уже вошла в первую группу 5···, поэтому второй раз их учитывать не нужно; это значит, что на первом месте может быть одна из 4-х цифр – 1, 3, 7 или 9:

Вариантов

всего получаем 4·1·5·5 = 100 вариантов

4) рассматривая случай ··5·, нужно выкинуть все варианты, в которых пятерки стоят на первых двух местах

Вариантов

всего получаем 4·4·1·5 = 80 вариантов

5) для ··5· аналогично получаем

Вариантов

всего получаем 4·4·4·1 = 64 варианта

6) общее количество вариантов

125 + 100 + 80 + 64 = 369 вариантов

7) таким образом, правильный ответ – 2.

Решение (вариант 2):

1) все числа, состоящие только из нечетных цифр, можно разбить на две группы: те, в которых есть пятерка, и те, где ее нет

2) общее число чисел, состоящих только из нечетных цифр, находим аналогично первой рассмотренной задаче; учитывая, что среди них нет нуля, получаем

5·5·5·5 = 625 вариантов

3) теперь аналогично найдем количество чисел, состоящих только из цифр 1, 3, 7 и 9 (без пятерки); поскольку на каждом из 4-х мест может стоять одна из 4-х цифр, получаем

4·4·4·4 = 256 вариантов

4) нужный нам результат – это разница

625 – 256 = 369 вариантов

5) таким образом, правильный ответ – 2.

Задачи для самостоятельного решения:

1) Сколько существует четырехзначных чисел, в которых есть ровно две восьмерки, не стоящие рядом?

2) Сколько существует четырехзначных чисел, составленных из разных четных цифр?

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

4) Сколько существует четырехзначных чисел, которые делятся на 5?

5) Сколько существует четырехзначных чисел, не превышающих 3000, в которых ровно две цифры «3»?

6) В чемпионате по шахматам участвовало 40 спортсменов. Каждый с каждым сыграл по одной партии. Сколько всего партий было сыграно?

7) В вазе лежат яблоко, груша, персик и абрикос . Кате разрешили выбрать два каких-то фрукта. Сколько у Кати вариантов выбора?

9) Сколько существует четырехзначных чисел, которые читаются одинаково «слева направо» и «справа налево»?

10) Цепочка из трех бусин формируется по следующему правилу: На первом месте в цепочке стоит одна из бусин А, Б, В. На втором – одна из бусин Б, В, Г. На третьем месте – одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте. Сколько всего есть таких цепочек?

В этой задаче нужно определить сколько всего существует четырехзначных чисел.

Количество четырехзначных чисел

• Определим сколько всего существует четырехзначных чисел.
• Четырехзначным называется число, которое состоит из четырех разрядов: единиц, десятков, сотен и тысяч. Простыми словами четырехзначное число - это число, которое состоит из ровно четырех цифр.
• Первым известным четырехзначным числом является число 1000.
• Последним известным четырехзначным числом является число 9999.
• Найди количество четырехзначным чисел. Возможно два варианта: из последнего четырехзначного числа (9999) вычитается первые 999 натуральных чисел. Получаем: 9999 - 999 = 9000.
• Второй способ: 9999 - 1000 + 1 = 9009. Единицу мы прибавляем, так как тысяча тоже является четырехзначным числом и просто вычтя, мы теряем его из общего количества.
• Также же можно еще определить общее количество цифр.

Определи количество цифр

Стало известно, что четырехзначное число состоит из 4 разрядов, иначе говоря, из 4 цифр. Также было посчитано, что всего известно 9000 четырехзначных чисел. Тогда получаем: 9000 * 4 = 36000.

Ответ: всего существует 9000 четырехзначных чисел и если всех их записать в ряд, то выйдет 36000 цифр.