Образовательный портал Павла Добряка

7. КОМБИНАТОРИКА

Начала комбинаторики мной были изложены во втором разделе – «Кодирование» (параграф «Основы комбинаторики»). Вместе с тем она широко применяется в последующих задачах. Так, мы встречали комбинаторику в задачах на количество программ и чисел, на логические уравнения, на IP-адресацию. 

Вначале мы сделаем обзор таких задач. Для удобства сравнения формулировки задач сведены в таблицы. В идеале тренированный решать ЕГЭ читатель должен сразу по формулировкам задач видеть разницу в ходе их решения. Но, как показывает мой опыт, ученики успевают забыть комбинаторику при переходе к задачам на программирование (она, кстати, встречается и там). Поэтому повторение не бывает лишним даже для способных учеников.   Целесообразно прорешать эти задачи за одно занятие для образования системных связей (может потребоваться 120 минут). 

Далее идут задачи, которые я усложнил, чтобы подчеркнуть их «комбинаторную суть» и сделать невозможным угадывание ответа. Кроме того, приводится несколько олимпиадных задач (не из ЕГЭ). Их полезно прорешать тем ученикам, кто нацелился получить максимальный балл. Они формируют определенный стиль мышления и находчивость, которая позволит не растеряться, если вдруг на ЕГЭ встретится незнакомая задача.

В общем, в этом разделе, как и в следующем, мы делаем второй круг по сложным и интересным задачам ЕГЭ, интегрирующий знания из разных разделов информатики (прикладной математики).

7.1. Классические комбинаторные задачи

Задание 7.1.1. Сравните и решите задачи (определите сходство и различие).

Лампочка может быть включенной, выключенной или мигающей. Сколько сообщений можно передать с помощью четырех таких лампочек? 2.2.1

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

2.2.2

В магазине продают фрукты 7 видов. Мы хотим купить три вида фруктов, чтобы сделать салат. Сколько разных салатов мы можем сделать? 2.2.3

Сравните и решите модификации следующей задачи (также сравните с задачами из задания 7.1.1.):

Алфавит состоит из четырех символов. Сколько можно составить шестибуквенных слов в следующих случаях:

1) Нет никаких ограничений на каждую букву. 2.2.1

2) буква А в слове ровно 1 раз 

3) буква А в слове ровно 2 раза

4) буква А в слове ровно 3 раза

(остальные – сколько угодно или не встречаются вовсе) 2.2.4

Задача 7.1.3. Слово состоит из 10 символов. При этом буква А в нем встречается ровно 1 раз, B – ровно 2 раза, С – ровно 3 раза, D – ровно 4 раза. Сколько существует таких слов?

Задание 7.1.4. Сравните задачи из следующей таблицы (верхний ряд мы уже решали). Решите задачи из нижнего ряда.

Лампочка может быть включенной, выключенной или мигающей. Сколько сообщений можно передать с помощью пяти таких лампочек? 2.2.1

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

2.2.2

В магазине продают фрукты 7 видов. Мы хотим купить три вида фруктов, чтобы сделать салат. Сколько разных салатов мы можем сделать? 2.2.3

Азбука Морзе состоит из точек и тире. Сколько сообщений можно закодировать, если в сообщении не более 5 символов.

2.5.1

Есть четыре вымпела разного цвета. Мы можем их вывешивать на одну веревку. Сколько сообщений мы можем передать? (Пустая веревка – это тоже сообщение, на веревку может быть вывешено сразу несколько вымпелов, их порядок (слева или справа) имеет значение). 7.1.5.

В магазине продают фрукты 7 видов. Мы хотим купить от одного до трёх видов фруктов, чтобы сделать салат. Сколько разных салатов мы можем сделать?

7.1.6.

Задача 7.1.5. Есть четыре вымпела разного цвета. Мы можем их вывешивать на одну веревку. Сколько сообщений мы можем передать? (Пустая веревка – это тоже сообщение, на веревку может быть вывешено сразу несколько вымпелов, их порядок (слева или справа) имеет значение.)

Задание 7.1.7. Сравните и решите следующие задачи:

Лампочка может быть включенной, выключенной или мигающей. Сколько сообщений можно передать с помощью шести таких лампочек? 2.2.1

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

2.2.5

Сколько положений может быть у тумблера, если в устройстве 100 команд, которые программируются с помощью трех тумблеров? 2.2.8

Задание 7.1.8. Сравните задачи из следующей таблицы. Найдите «ядро» задач – что является мощностью алфавита, словами и ячейками.                                 

Метеостанция раз в день измеряет температуру. Сколько бит нужно на одно измерение, если диапазон измеряемой температуры от -64 до 64, а точность – 0,5 градуса.

2.2.9

Картинка размером 10 x 10 пикселей имеет палитру из 32 цветов. 

1) Какой объем в битах занимает это изображение?

2.2.10

2) Сколько картинок в принципе можно составить (напишите выражение, не вычисляя)? 2.2.10-примечание

Идет двухканальная запись звука с частотой дискретизации 100 Гц, количеством уровней дискретизации, равным 64, и продолжительностью 5 минут. Какой объем сигнала в байтах?

2.2.11

В соревновании участвуют 20 спортсменов.

1) Сколько бит надо, чтобы закодировать номера трех чемпионов? 2.2.5

2) Сколько может быть вариантов списков чемпионов?

2.2.5-примечание

Ав­то­мо­биль­ный номер дли­ной 7 сим­во­лов со­став­ля­ют из за­глав­ных букв (ис­поль­зу­ют­ся толь­ко 33 раз­лич­ных буквы) и де­ся­тич­ных цифр в любом по­ряд­ке. Каж­дый такой номер в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством бай­тов. 1) Опре­де­ли­те объём па­мя­ти, от­во­ди­мый этой про­грам­мой для за­пи­си 125 но­ме­ров. 2.2.13

2) Сколько всего может быть автомобильных номеров?

2.2.13-примечание.



Подробнее

7.2. Геометрические и графовые задачи

Задача 7.2.1Граф состоит из 11 вершин. Первая связана со второй одним путем, вторая с третьим – двумя, третья с четвертым – тремя и т.д. Сколько путей ведет из первой вершины в последнюю?

Задача 7.2.2

 

Полным графом называют граф, у которого любая пара вершин соединена ребром. Пусть граф состоит из 100 вершин. Сколько ребер в графе? 


Задача 7.2.3. Симплексом является простейший объект в многомерном пространстве:

0 измерений – точка:



 

1 измерение – отрезок:

 

 

2 измерения – треугольник:

 

3 измерения – тетраэдр

1 вершина

 

2 вершины, 

1 ребро

3 вершины, 

3 ребра

1 грань

4 вершины

6 ребер

4 грани

1 тело (гипергрань)

Сколько разных элементов (вершин, ребер, граней, гиперграней…) имеет симплекс в шестимерном пространстве?

Задача 7.2.4Сколько существует путей из А в G?



Подробнее

7.3. Комбинаторика в различных разделах ЕГЭ

Задача 7.3.1Логическая функция задается выражением x¬y (¬zw).

???

???

???

???

F

0

0

1

0

1

0

0

1

1

1

1

0

1

1

1

1) Сколько строчек в таблице истинности?

2) Сколько возможно расположений переменных в таблице истинности?

Задание 7.3.2. Сравните задачи на таблицу истинности с задачами про флаги и лампочки:

Лампочка может быть включенной, выключенной или мигающей. Сколько сообщений можно передать с помощью семи таких лампочек?

2.2.1

Есть пять флагов разного цвета. Их мы можем вывешивать на три мачты. Сколько сообщений мы можем передать?

2.1.2

Логическая функция F задается выражением x¬y (¬zw). 

???

???

???

???

F

0

0

1

0

1

0

0

1

1

1

1

0

1

1

1

1) Сколько строчек в таблице истинности? 7.3.1

 

 

2) Сколько возможно расположений переменных в таблице истинности? 7.3.1

Задание 7.3.3. Сравните задачи (предварительно решите правую задачу или посмотрите ее решение):

Лампочка может быть включенной, выключенной или мигающей. Сколько сообщений можно передать с помощью семи таких лампочек?

2.2.1

Маска подсети: 255.255.224.0. Сколько различных адресов компьютеров теоретически допускает эта маска, если два адреса (адрес сети и широковещательный) не используют? 4.6.3.

 

Задача 7.3.4. Число 2311 в некоторых системах счисления оканчивается на 1. Сколько существует таких систем счисления? 

Задача 7.3.5Дано число 30030.

1) Сколько существует натуральных делителей у этого числа?

2) Сколько существует разложений на множители этого числа? То есть разложений вида a ba b c, … (с точностью до перестановки множителей)

Задача 7.3.6. Из 0 нужно получить 6 с помощью двух операций: +1 и +2. Сколько существует программ?

Задание 7.3.7. Сравните задачи (предварительно решите среднюю задачу или посмотрите её решение):

Алфавит состоит из шести символов. Сколько можно составить пятибуквенных слов, если буква А встречается в слове ровно два раза, а остальные – сколько угодно или отсутствуют) 2.1.4

Из 0 нужно получить 6 с помощью двух операций:

+1, +2. 

Сколько существует таких программ? (Программа – это последовательность операций.) 3.2.8

Число 2311 в некоторых системах счисления оканчивается на 1. Сколько существует таких систем счисления? 7.3.4.

 

Задача 7.3.8. Даны все целые числа от 2 до 24. Сколько пар из этих чисел в произведении дают результат, делящийся на 6?


Подробнее

7.4. Комбинаторика при решении логических уравнений

Задание 7.4.1. Решите уравнения из следующей таблицы (если не сможете их решить, сперва посмотрите их аналоги в параграфе «4.5. Логические уравнения»). В чем состоит их комбинаторная суть?

Задача 7.4.2. Сколько есть решений в логическом уравнении: 

A  ⌐B  ⌐C  D = 1?

Задача 7.4.3. Сколько есть решений в логическом уравнении: 

(X  Y  Z (A  ⌐B  ⌐C  D (N  ⌐N) = 1

Задача 7.4.4. Сколько есть решений в логическом уравнении:

Задача 7.4.5. Сколько различных решений имеет система логических уравнений:

Задача 7.4.6. Сколько различных решений имеет система логических уравнений:








Подробнее