Комбинаторика
С тех пор, как было принято
решение (Инструктивное письмо №03-93ин/13-03 от 23.09.2003 г. Министерства образования РФ
«О введении элементов комбинаторики, статистики и теории вероятностей в содержание
математического образования основной школы») об изучении основ теории вероятностей в школе,
особое значение для школьного курса математики приобрели задачи по комбинаторике.
Если в 1980-1990-е гг. несложные задачи на эту тему подавались как занимательные и олимпиадные,
т.е. необязательные для изучения, то в последнее время ситуация изменилась: задачи, решаемые
с помощью формул комбинаторики, стали изучаться в 8-9 классах в связи с курсом теории вероятностей.
С тем, чтобы подготовить школьника
к пониманию такого типа задач целесообразно включать их в программу индивидуальных занятий
с репетиторами, конечно в том случае, если перед последними стоит цель не просто подтянуть ученика
и натаскать его на определённые темы, но и развить его математические способности.
Поэтому в рамках курса олимпиадных задач я обычно рассматриваю с моими учениками такого рода
задачи, причём с пятиклассниками и шестиклассниками.
Существует точка зрения, что предлагать
решать задачи по этой теме в пятом-шестом классах рановато, даже на дополнительных «кружковых»
занятиях по математике, однако в последнее время всё чаще и чаще задачи на комбинаторику попадают
в различные современные сборники задач и пособия для 5-6 классов как «дополнительные главы для 5-го
класса» или как «математические кружки» для 5-го класса. На возможности и необходимости изучения
такого рода задач с сильными учениками 5-6 классов настаивают и некоторые учителя, если судить
по статьям, размещённым в Интернете. При этом предлагается изучать только простейшие задачи на эту
тему и ограничиваться правилами суммы и произведения, а также определением числа перестановок.
Однако в вопросе о том, что рекомендуется изучать в пятом классе, а что нет, пусть на
дополнительных занятиях, учителя по-видимому ещё не пришли к единому мнению. Поэтому в одном
пособии для 5-го класса (автор Е.В. Смыкалова, изд. в 2001 г.) ученикам преподносятся только
правила суммы и произведения, и даётся понятие о перестановках без повторений,
а в другом (автор А.Ф. Крижановский, изд. в 2018 г.)— пятиклассникам предлагается решать задачи,
требующие знания формулы числа перестановок с повторениями. В последней из упомянутых книжек
шестиклассникам предлагаются формулы числа размещений и числа сочетаний. Судя по годам выхода книг
можно отметить, что комбинаторика, если можно так выразиться, «молодеет» — если в конце 1990-х
годов школьникам 5-6 класса предлагались только несложные задачи на тему комбинаторики, которые
можно решить, что называется «на пальцах», то теперь шестиклассникам необходимо «вооружаться» всеми
основными формулами комбинаторики.
С другой стороны, в последнее время
встречаются ученики, которые в 5-6 классах уже серьёзно занимаются программированием в качестве
дополнительных занятий. Им предлагается написать программы для решения некоторых задач, связанных
с перебором вариантов, т.е. фактически задач по комбинаторике. Таким ученикам уже бывает
недостаточно знания правила суммы или правила произведения. Им требуется знать и более серьёзные
формулы комбинаторики. Поэтому на этой странице приведены не только самые простые правила по
комбинаторике, но и более сложные, изучаемые в 8 — 9 классах, а также приведены задачи, решаемые
с помощью как простых правил, так и сложных. Для подготовки к занятию по комбинаторике с каждым
конкретным учеником, я ориентируюсь на его уровень и те задачи, которые перед ним стоят.
Вовсе необязательно, чтобы все пятиклассники могли решать все задачи, размещённые на этой странице.
Так или иначе, но знакомство пятиклассников и шестиклассников с такого рода
задачами служит хорошим введением в комбинаторику, способствующим пониманию её задач.
Что же такое комбинаторика? Судя по
названию (которое происходит от латинского слова, означающего «соединять, сочетать») — это раздел
математики в котором изучаются комбинации различных элементов. Другими словами, основной задачей
комбинаторики является определение количества комбинаций элементов, подчинённых заданным условиям.
Основными типами комбинаторных задач являются перестановки, размещения, сочетания.
Перестановками из n элементов
называют их комбинации, отличающиеся друг от друга только порядком входящих в них элементов. Другими словами,
в данном случае требуется узнать количество способов размещения n различных предметов на n различных местах.
|
Пример 1. Сколько четырёхзначных чисел можно составить из четырёх цифр при условии, что цифры не повторяются? Эта задача является по сути одним из этапов решения задачи 1 по криптографии, размещённой здесь. |
|---|
Решение. Согласно одному из основных
правил комбинаторики, это число рано 4! («четыре факториал») = 1*2*3*4.
Примечание репетитора
по математике:. Бывает, что школьники могут быть знакомы с тем, что такое факториал
до занятий с репетитором. Бывает, что нет. В любом случае, объяснение, что такое факториал,
обычно легко усваивается школьниками. Однако при первом знакомстве с факториалом необходимо
обратить внимание школьника на то, что 0!=1!=1.
Поскольку 4! — число небольшое,
школьники могут убедиться в этом простым перебором вариантов. Тем, кто хочет знать больше, можно
предложить следующую формулу комбинаторики:
Кроме того, необходимо учесть, что
эта формула работает тогда, когда находится число перестановки без повторений, что является
классической задачей комбинаторики. Перестановки состоят из одних и тех же элементов, но отличаются
между собой порядком.
Однако встречаются
и несколько другие задачи на перестановки.
|
Пример 2. Сколькими способами можно поселить 7 студентов в три комнаты общежития, если эти комнаты одноместная, двухместная и четырёхместная? |
|---|
Решение. Предположим, студентов зовут
Андрей, Борис, Владимир, Геннадий, Дмитрий, Евгений, Жорес. Если бы требовалось разместить
их на семи различных местах, то вариантов размещения было бы 7!. Однако если в одноместную комнату
может поселиться 7 студентов и вариантов таких 7, то при размещении студентов в двухместную комнату,
например, вариант «Андрей и Борис» тождественен варианту «Борис и Андрей». А при размещении четырёх
студентов в четырёхместную комнату тождественных вариантов уже несколько с участием всё тех же
Андрея и Бориса. Значит, в данном случае мы имеем задачу на перестановки с повторениями. Для таких
случаев пользуются следующей формулой:
Таким образом, задача из Примера 2
решается по формуле:
С пятиклассниками и шестиклассниками
полезно рассмотреть основные правила комбинаторики — правило суммы и правило произведения.
|
Правило суммы. Если объект A можно выбрать n способами, а объект B — m способами, то выбор A и B можно осуществить (m+m) способами. |
|---|
|
Правило произведения. Если объект A можно выбрать n способами, а объект B — m способами, то пару A и B можно выбрать (m*m) способами. |
|---|
Несмотря на относительную несложность этих формулировок, пятиклассникам и шестиклассникам
целесообразно показывать их действие на примерах.
|
Пример 3. Пусть на тарелке лежат 7 персиков и 3 апельсина. Сколькими способами можно выбрать один фрукт? |
|---|
Решение. Так как и выбрав персик, и выбрав апельсин мы выбираем какой-либо
фрукт, то ответом на вопрос будет число 10 ( 7 + 3 = 10).
|
Пример 4. В футбольной команде из 11 человек нужно выбрать капитана и его заместителя. Сколькими способами можно это сделать? |
|---|
Решение. Так как капитана
можно выбрать из 11-ти игроков, а его заместителя — уже из 10-ти, то всего комбинаций по правилу
произведения может быть 110.
Важно, чтобы у учеников отложилось
то наблюдение, что правило суммы работает тогда, когда происходит хотя бы одно из событий, а
правило произведения тогда, когда происходят оба события.
Задачи по комбинаторике всех типов
целесообразнее проходить в более старших классах — тогда, когда в курсе школьной программы
появляется теория вероятностей. Однако тут многое зависит от уровня каждого конкретного школьника.
Одному бывает нужны несложные задачи в качестве подготовки к олимпиадам. А другому, например,
занимающемуся программированием, хочется решать более сложные задачи по комбинаторике.
И уровень задачи из Примера 1 для них уже не представляет интереса. Поэтому ниже приведённые
задачи достаточно различны. И предлагать решать их ученикам следует только учитывая их уровень и задачи.
В расчёте на достаточно средний уровень учеников полезно рассматривать только несложные
занимательные задачи с элементами комбинаторики. Если же ученик хочет знать больше, то можно с ним
рассматривать и более сложные задачи по комбинаторике, а также формулы для определения числа размещений и числа сочетаний.
Для тех, кто хочет знать больше, можно показать следующую
формулу комбинаторики, по которой находится число размещений.
Размещения — это комбинации, составленные из n различных элементов по m элементов. Причём эти комбинации
отличаются либо составом элементов, либо их порядком.
С теми, кто хочет знать больше,
можно рассмотреть и ещё один тип комбинаторных задач — задачи на сочетания. Однако важно подчеркнуть,
что такие задачи всё-таки целесообразнее рассматривать со школьниками более старших
классов. Для того, чтобы было понятно, о чём речь, рассмотрим задачу:
|
Пример 5. Пусть в кружке по математике занимаются 4 девочки и 6 мальчиков. Сколькими способами можно составить из них команду из двух мальчиков и двух девочек для участия в городской олимпиаде по математике? |
|---|
Решение. Эту задачу уже «на пальцах» не решить.
Тут требуется знать формулу сочетаний:
Сочетания — это число всех выборов
m элементов из n данных без учёта их порядка называют числом сочетаний из n элементов по m.
Решение. Так как порядок выбора
не имеет значения, то двух девочек из четырёх мы можем выбрать по формуле:
Аналогично двух мальчиков из шести можно выбрать по формуле:
Так как любому набору мальчиков мы можем сопоставить любой набор девочек, то
полученные два числа следует перемножить, для того чтобы определить число всех способов:
Обратим внимание на то, что 4! и (6-2)! можно сократить. Получаем:
Несложных задач по комбинаторике,
которые можно рассматривать с пятиклассниками и шестиклассниками в качестве введения в этот
раздел математики, достаточно много. Иногда для их решения требуется смекалка.
Некоторые из них требуют знания формул комбинаторики, другие могут решаться достаточно просто,
даже интуитивно. Ниже приведены разнообразные задачи на эту тему — от простых до достаточно
сложных. Все эти задачи можно рассматривать на занятиях по олимпиадной математике
с пяти- шестиклассниками. Однако как отмечал выше, многое тут зависит от уровня ученика. Репетитору
важно учитывать способности ученика. Поэтому обычно для занятия по комбинаторике в рамках
курса по занимательной и олимпиадной математике я готовлю задачи из этой подборки к каждому
конкретному занятию, уже имея представление об уровне ученика.
1) Оператор на почте получил для продажи несколько пачек
по 100 конвертов в каждой. 10 конвертов он отсчитывает за 3 секунды. За сколько секунд он может отсчитать 60 конвертов? А 90 конвертов?
2) Восемь подружек решили обменяться фотографиями так, чтобы у каждой оказались
фотографии остальных подруг. Сколько фотографий для этого потребуется?
3) Десять человек обменялись рукопожатиями.
Сколько всего было рукопожатий?
4) Имеется 5 чемоданов и 5 ключей, но неизвестно,
какой ключ от какого чемодана. Какое наименьшее число проб достаточно для того, чтобы гарантированно разложить ключи на чемоданы,
которые ключи открывают в самом крайнем случае.
5) Иван Царевич добыл связку ключей от
нескольких комнат в подземелье, но не знал, какой ключ от какой комнаты. Сколько комнат в подземелье, если в худшем случае
ему достаточно 21 пробы, чтобы выяснить, какой ключ от какой комнаты?
6) Сколькими способами можно выложить
в ряд чёрный, белый, жёлтый, зелёный шарики?
7) Алёша, Боря, Вася и Гена — лучшие математики в классе. На школьную олимпиаду
нужно выставить команду из трёх человек. Сколькими способами это можно сделать?
8) В коробке лежат игрушки? 10 мишек и 7 зайцев.
Какое наименьшее число игрушек надо вытащить, чтобы среди них было точно 2 мишки и 1 заяц?
9) В ящике лежат 70 шаров — 20 белых, 20 чёрных, 20 красных, а остальные —
синие и зелёные. Шаря отличаются только цветом. Какое наименьшее количество шаров нужно вытащить, чтобы 10 из них обязательно были одного цвета?
10) У дрессировщика 7 львов, 5 тигров, 3 леопарда и 4 пумы. Для выступления
на празднике ему нужно выбрать по одному хищнику каждого вида. Сколькими способами он может сделать выбор?
11) Сколькими способами можно расставить чёрную и
белую ладьи на шахматной доске так, чтобы они не били друг друга?
12) Сколькими способами можно разместить на шахматной доске белого и чёрного
короля так, чтобы они не били друг друга?
13) Сколькими способами можно расставить чёрную и
белую ладьи на шахматной доске так, чтобы они били друг друга?
14) Сколькими способами можно
поставить на шахматную доску белого и чёрного королей так, чтобы получилась допустимая правилами
игры позиция?
15) 30 команд сыграли турнир
по олимпийской системе. Сколько всего было сыграно матчей?
16) Какое максимальное число ферзей, не бьющих друг друга, можно расставить на шахматной доске 8х8?
17) Сколькими способами можно сделать трёхцветный флаг с тремя горизонтальными полосками одинаковой ширины,
если имеется материя шести различных цветов?
18) Сколько различных чисел можно получить переставляя местами цифры в числе 7537?
19) Сколькими способами можно выбрать 3 краски из 5-ти различных?
20) В стране, в 15-ти городах есть
аэропорты. Каждый с каждым соединён авиалинией. Сколько авиалиний в этой стране?
21) В стране, в 15-ти городах
есть аэропорты, каждые два из которых соединены авиалинией. Сколько авиалиний в этой стране?
22) На плоскости отмечено
10 точек так, что никакие три из них не лежат на одной прямой. Сколько существует треугольников с вершинами в этих точках?
23) Cколько существует различных семизначных телефонных номеров (номер начинаться с нуля не может)?
24) В пассажирском поезде 17 вагонов.
Сколькими способами можно распределить по вагонам 17 проводников, если за каждым вагоном закрепляется один проводник?
25) В обыкновенном наборе домино 28 костяшек. Сколько костяшек содержал бы набор домино, если бы значения, указанные на костяшках,
изменялись не от 0 до 6, а от 0 до 12?
26) Каких прямоугольников с целыми сторонами больше: с периметром 1996 или с периметром 1998?
(Прямоугольники a*b и b*a считаются одинаковыми).
27) Сколькими способами можно разбить 10 человек на пары?
28) Сколько существует восьмизначных чисел, цифры которых идут
в порядке убывания?
29) Кубик бросают трижды.
Среди всех возможных последовательностей результатов есть такие, в которых хотя бы один раз
встречается шестерка. Сколько их?
30) Назовём натуральное число «симпатичным», если в его записи встречаются
только нечётные цифры. Сколько существует 4-значных «симпатичных» чисел?
31) Назовём натуральное число «гармоничным», если в его записи встречаются
только чётные цифры. Сколько существует 4-значных «гармоничных» чисел?
32) Монету бросают трижды.
Сколько разных последовательностей орлов и решек можно при этом получить?
33) Слово — любая конечная
последовательность букв русского алфавита. Анаграмма (по-гречески — «Новая запись») — способ
перестановки букв, в результате которого получается новое слово. Изначально считалось, что новое слово должно быть
осмысленным. Позже таким способом получались некоторые псевдонимы, причём новые слова могли быть при этом неосмысленными.
Сейчас анаграммами называют просто перемешивание букв составляющих исходное слово, то есть допускается получение
неосмысленных слов. Выясните, сколько различных анаграмм (включая неосмысленные слова) можно
составить из слов: а) ребус; б) математика; в) арифметика; г) литература;
д) комбинаторика; е) телефон.
34) В киоске «Роспечать» продаются
6 видов конвертов и 5 видов марок. Сколькими способами можно купить конверт с маркой?
35) В классе 24 ученика. Сколькими
способами можно сформировать команду из 4 человек для участия в математической олимпиаде?
36) Сколькими различными способами
можно избрать из 12-ти человек делегацию в составе 5-ти человек?
37) Из ящика, где находится 15 шаров,
нумерованных последовательно от 1 до 15, требуется вынуть 3 шара. Определить число возможных
комбинаций при этом?
38) Сколькими способами можно
разместить 6 пассажиров в четырехместной каюте?
39) Бригадир должен отправить на работу
бригаду из 4 человек. Сколько бригад по 4 человека в каждой можно составить из 13 человек?
40) Шифр для сейфа составляется из пяти различных цифр.
Сколько различных вариантов составления шифра?
41) В пятом классе изучаются 8 предметов. Сколько
различных вариантов расписания можно составить на пятницу, если в этот день должно быть 4 урока и все уроки разные?
42) В столовой в продаже есть три первых блюда, четыре вторых блюда,
а на третье — кисель, компот, чай и сок. Сколько различных вариантов обеда из трёх блюд можно заказать?
43) Из 14-ти девушек и 12-ти юношей выбирают команду,
состоящую из пяти человек. Сколькими способами это можно сделать, если в команду должно войти не более трёх юношей?
Репетитор по математике в Москве, Александр Анатольевич, 8-968-423-9589.
Имею большой опыт работы репетитором. За два десятилетия выработаны собственные методики занятий. Окончил технический ВУЗ – Московский автомобильно-дорожный институт в 1987 г.
Еще в институте оказывал помощь однокурсникам по высшей математике. Репетиторством занимаюсь с 1998 г. За это время мною подготовлено к различным экзаменам более 200 учеников.
Специализируюсь на подготовке в лицеи и математические школы, готовлю к сдаче ОГЭ и ЕГЭ. Занимаюсь также сопровождением школьной программы — подготовкой к контрольным
и самостоятельным работам. Прививаю навыки быстрого устного счета, рассматриваю с учениками логические и нестандартные задачи, направленные на воспитание интереса к предмету,
на развитие логического мышления.