Дискретная математика для инженеров-физиков. Задачи с решениями

Министерство образования российской федерации Красноярский государственный технический университет

ДИСКРЕТНАЯ МАТЕМАТИКА для инженеров-физиков Тимофеев Иван Владимирович

Красноярск 2006

Посвящается моим школьным учителям Ларину Сергею Васильевичу, Лариной Полине Ивановне, Ореховой Ларисе Ивановне, Соснину Михаилу Викторовичу ПОСОБИЕ НЕ БЫЛО ИЗДАНО УДК 535.14(07) Ф50 Рецензент: В.П. Тимофеев, к-т. физ.-мат. наук, проф. кафедры ВЭПОМ КГТУ Ф50 Дискретная математика для инженеров-физиков: сборник задач / Сост. И.В. Тимофеев. Красноярск: ИПЦ КГТУ, 2003. 35 с. В сборник вошли 64 задачи, предлагавшиеся автором-составителем студентам Инженерно-физического факультета КрасГТУ в третьем семестре в рамках 34-часового курса «Дискретная математика». Все задачи снабжены ответами и указаниями к решению. Дискретная или конечная математика является универсальным языком описания и исследований в таких научных разделах и направлениях как теория алгоритмов, теория графов, теория групп. Дискретный анализ охватывает практически все области инженерного знания от электрических цепей и задач оптимизации до проблемы квантового компьютера. Без знания основ дискретной математики немыслимо понимание современных методов работы с информацией: поиск, защита, сжатие. На дискретную математику опираются принципы работы таких широко распространенных аппаратов, как сотовый телефон, mp3-плейер, сканер штрихкодов. Освоение студентом программы данного курса предполагает знание основ алгебры и геометрии, элементарных математических понятий и терминов. © КГТУ, 2006 © Тимофеев И.В., 2006 Печатается в авторской редакции Печатается по решению редакционно-издательского совета факультета. 2

ПЛАН КУРСА «ДИСКРЕТНАЯ МАТЕМАТИКА». Краткая характеристика курса Дискретная или конечная математика является универсальным языком описания и исследований в таких научных разделах и направлениях как теория алгоритмов, теория графов, теория групп. Дискретный анализ охватывает практически все области инженерного знания от электрических цепей и задач оптимизации до проблемы квантового компьютера. Без знания основ дискретной математики не мыслимо понимание современных методов работы с информацией: поиск, защита, сжатие. На дискретную математику опираются принципы работы таких широко распространенных аппаратов, как сотовый телефон, mp3-плейер, сканер штрихкодов. Освоение студентом программы данного курса предполагает знание основ алгебры и геометрии, элементарных математических понятий и терминов. Курс рассчитан на 8 лекций и 8 практических занятий. Краткость курса заставляет отказаться от традиционного жесткосистематического подхода и сместить ударение на популярное изложение с задачами олимпиадного характера и занимательного оформления. Данный курс существенно отличается от классических университетских курсов дискретной математики. Понятия, утверждения и способы решения задач излагаются согласно наглядно-эмпирическому подходу. Разделы начинаются с простых школьных задач, требующих скорее сообразительность, нежели знаний. Темы лекций Лекция 1. Введение. Теория множеств. Примеры множеств. Основные обозначения. Действия над множествами и их свойства. Диаграммы Эйлера-Венна. Лекция 2. Правила сложения (включений и исключений) и умножения мощностей множеств. Прямое произведение и разбиение. Отображения «на», «в», взаимно однозначные. Лекция 3. Представления строки нулей и единиц: а) вектор Евклидова пространства, вершина многомерного куба; б) подмножество множества, характеристический вектор подмножества, булеан; в) логическая функция; г) двоичное представление натурального числа, системы исчисления; 3

д) состояние памяти вычислительной машины: команды, величины, текст; е) результат эксперимента, сообщение; ж) монотонный путь на прямоугольной сетке; з) растровый рисунок; и) штрих-код, азбука Морзе. Лекция 4. Выборки. Сочетания и размещения с повторением и без повторения. Факторизация и факториал. Двойственность того набора, из которого выбирают, и того, в который выбирают. Лекция 5. Таблица основных формул комбинаторики. Перестановки с повторением. Бином Ньютона. Треугольник Паскаля, его вероятностная интерпретация. Лекция 6. Графы. Определения. Локальные степени. Подграфы. Бинарные отношения на графах. Матрицы смежности и инцидентности. Связность. Маршруты и цепи. Расстояние. Радиус и диаметр графа. Эйлеровы цепи и гамильтонов путь. Деревья. Правила обхода лабиринтов. Лекция 7. Поиск, защита, сжатие информации Поиск и двоичное дерево. Неравенство Крафта. Информационная энтропия и ее свойства. Сжатие информации: код Шеннона-Фэно, алгоритм Хаффмена, Зива-Лемпеля. Лекция 8. Графы и перестановки на примере электрических цепей, лабиринтов, комбинаторных головоломок и логических игр Основная литература 1. Романовский И.В. Дискретный анализ. Учебное пособие по прикладной математике и информатике. 3-е изд. СПб.: Невский диалект, 2004 г. 2. Липский В. Комбинаторика для программистов. М.: Мир, 1988 г. 3. http://physmatik.narod.ru/ Дополнительная литература 4. Цих А.К. Введение в специальность «математика». 2-е изд. Изд-во КрасГУ, 2002 г. 5. Акимов О.Е. Дискретная математика: логика, группы, графы -М. : Лаборатория Базовых Знаний , 2001. 6. Оре О. Теория графов. М.: Наука, 1968 г. 7. Калужнин Л.А., Сущанский В.И. Преобразования и перестановки. М.: Наука, 1979 г. 8. Виленкин Н.Я. и др. Алгебра и математический анализ. 11 кл.: Учеб. Пособие для шк. и кл. с углубл. изуч. математики. М.:Мнемозина, 2000 г. (главы 11,12) 4

9. Шарыгин И.Е. Геометрия (5-6 кл), (7-9 кл) и (10-11 кл): Учеб. Пособие для школ. 10. Дубровский В.Н., Калинин А.Т. Математические головоломки. Вып. 1. М.:Знание, 1990 г. 11. Яглом И.М. Необыкновенная алгебра. Серия: Популярные лекции по математике. М.:Наука, 1968 г. 12. Гарднер М. Математические головоломки и развлечения. Пер. с англ. Ю.А. Данилова. М.: "Мир", 1971, 511 с. 13. Зельдович Я.Б., Мышкис А.Д. Элементы математической физики. Среда из невзаимодействующих частиц. М.:Наука, 1973, 351 с. 14. Пенроуз Р. Новый ум короля: О компьютерах, мышлении и законах физики. М.: Едиториал УРСС, 2003 г. Тяжелая1 литература 15. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988 г. 16. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. М.:Наука, 1982 17. Яблонский С.В. Введение в дискретную математику: Учеб. Пособие для вузов. М.: Высш. шк. 2003 г. 18. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике: Учеб. Пособие. М.: Физматлит, 2004 г. к.ф.-м.н., Тимофеев И.В. ([email protected])

1

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

5

ЗАНЯТИЕ 1. ОСНОВЫ Множества, отображения и отношения ’2 Задача 1.1. Булеан ("3š4) Перечислите подмножества множества из 3 элементов A = {a,b,c}. Включите в число подмножеств само множество и пустое множество5. Сколько подмножеств6 имеет множество из N элементов? ’’ Задача 1.2. Доказательство на кружках С помощью диаграммы Эйлера-Венна7 докажите правила де Моргана8: A∪ B = A∩ B A∩ B = A∪ B ’’ Задача 1.3. Принцип Дирихле9 в арбузных корках ("š) Пятеро друзей (студенты-математики) разрезали арбуз на пять кусков. Когда арбуз был съеден, получилось шесть корок. Причем корки не ломали. Изобразите возможное разрезание.

2

Количество звездочек перед заголовком определяет сложность задачи. Знак " указывает, что задача упоминается, а, возможно, и разбирается на лекции. 4 Знак š указывает на расчетную задачу, числовые данные в которой могут быть легко изменены. 5 Все множество и пустое множество называются несобственными подмножествами. 6 Множество подмножеств называется булеаном в честь американского математика Буля, исследовавшего алгебру нулей и единиц. В данном случае единицы понимаются как наличия, а нули — отсутствия данного элемента в подмножестве. Буль (Boole) Джордж (2.11.1815, Линкольн, - 8.12.1864, Баллинтемпл близ Корка), английский математик и логик. 7 Эйлер (Euler) Леонард [4(15).4.1707, Базель, Швейцария, - 7(18).9.1783, Петербург], математик, механик и физик. Венн (Venn) Джон (4.8.1834, Драйпул, близ Халла, - 4.4.1923, Кембридж), английский логик. 8 Морган (1806-1871) Август де (1806-1871), английский математик и логик. 9 Принцип Дирихле́ утверждает, в частности, что если посадить 11 кроликов в 10 клеток, то найдется клетка, в которой окажется не менее двух кроликов. Дирихле́ (Dirichlet) Петер Густав Лежён (13.2.1805, Дюрен, - 5.5.1859, Гёттинген), немецкий математик. 3

6

’’ Задача 1.4. Отношение упорядочения Девять борцов пронумерованы №№1-9 так, что борец с большим номером побеждает борца с меньшим номером. Составьте 3 команды по 3 борца так, чтобы в поединках сильнейший с сильнейшим, слабейший со слабейшим и средний со средним по числу побед первая команда побеждала вторую, вторая − третью, а третья − первую. Какое из свойств упорядоченного множества нарушается для команд борцов?

Вероятности ’’ Задача 1.5. Азартная игра и справедливость (š) Саша, Витя, Дима и Женя бросают один раз два игральных кубика. Если выпадает 12 или 4 очка, то выигрывает Саша; если 11 или 3 — выигрывает Витя; если 10 или 2 — выигрывает Дима, если выпадает 5 — выигрывает Женя. Справедлива ли эта игра? Почему? ’’ Задача 1.6. Очень широкий танк (š) Танк шириной 3 метра наудачу наползает на цепь мин, расположенных на расстоянии 18 метров друг от друга перпендикулярно направлению движения. Если мина попадает под гусеницу или между гусениц, танк взрывается. Какова вероятность, что танк уцелеет? Размером мин пренебречь, ответ обосновать. Как изменится вероятность, если танк едет под углом 300 к цепи. ’’’ Задача 1.7. В квадратном часе (š) Ромео и Джульетта договорились встретиться в саду с 22:00 до 23:00. Каждый из них приходит наудачу (равновероятно) в любой момент времени из оговоренного интервала и ждет 20 минут, после чего обязан удалиться. Какова вероятность встречи возлюбленных? 1 11 ЗАНЯТИЕ 2. КОЛИЧЕСТВО И ПОРЯДОК 21 ’’ Задача 2.1. Числа количественные и 1211 10 порядковые (" ) 111221 312211 Натуральные числа применяют не только для ответа ... на вопрос «Сколько?», но и для ответа на вопрос «КаЧисла количекой по счету?». Сколько тебе лет? — 18 лет. Какой ственные и порядковые 10

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

7

годок идет? — 19-ый год. Другими словами, следует отличать числа количественные и порядковые. Имея это ввиду, продолжите последовательность в рамке.

Правило сложения (включения-исключения) множеств ’’ Задача 2.2. Правило гусениц По ветке ползут две гусеницы, сумма длин которых равна длине ветки. Что больше: длина участка ветки, по которому ползут обе гусеницы, или сумма длин участков ветки, по которым не ползет ни одна гусеница? Почему? ’’ Задача 2.3. Правило красок () Узор состоит из четырех окружностей, расположенных симметрично и касающихся центра и границы общего круга. Какой краски потребуется больше — в точечку или в клеточку? Почему? ’’ Задача 2.4. Инспектор запутался (š) В отчете об обследовании 80 студентов сообщалось, что Правило красок все три иностранных языка знают 5 человек, немецкий и испанский − 10, французский и испанский − 8, немецкий и французский − 20, испанский − 40, немецкий − 24, французский − 50. Назовите две причины, по которым инспектора, давшего отчет, уволили. ’’ Задача 2.5. Куратор недосчитался (š) Куратор потока дал следующие сведения о студентах: «На потоке 40 студентов, в том числе 25 парней. 30 студентов получают повышенную стипендию, в том числе 16 парней. Спортом занимаются 28 учащихся, в том числе 18 парней и 17 студентов, получающих повышенную стипендию. 10 парней получают повышенную стипендию и занимаются спортом». Найдите ошибку.

Правило умножения ’ Задача 2.6. Считалочка Шел Кондрат в Ленинград, 8

А навстречу − 12 ребят. У каждого по 3 лукошка, В каждом лукошке − кошка, У каждой кошки − 12 котят, У каждого котенка в зубах по 4 мышонка. И задумался Кондрат: "Сколько мышат и котят Ребята несут в Ленинград?" (Глупый, глупый Кондрат! Он один и шагал в Ленинград. А ребята с лукошками, С мышами и кошками Шли навстречу ему — В Кострому.) Корней Иванович Чуковский Ладно. Сколько мышат и котят ребята несли в Кострому? ’’ Задача 2.7. Не роскошь, а средство передвижения () Автомобили Красноярского края в правой части номера имеют пометку «24 RUS». Каждый номер содержит три буквы, читаемые как в русском, так и в латинском алфавитах, а также три цифры. Номера с тремя Не роскошь, нулями «000» исключаются. Преда средство передвижения ставьте, что не существует особых зарезервированных номеров. Для какого по счету автомобиля в Красноярском крае не хватит номера с отметкой «24 RUS»? ’ Задача 2.8. Ладейное перенаселение (") Какое наибольшее количество ладей можно расставить на шахматной доске так, чтобы они не били друг друга? Сколькими способами это можно сделать?

ЗАНЯТИЕ 3. ПРЕДСТАВЛЕНИЯ СТРОКИ ’’’ Задача 3.1. Электронная логика (") При включенном двигателе (1) легкового автомобиля реле поворота должно работать,

Электронная логика 9

если водитель повернул рычажок поворота (2). Но когда водитель выключает зажигание ( не 1 = 1 ), реле должно отключиться. Вдруг водитель забудет отключить рычажок поворота. А оставленный автомобиль не будет мигать, привлекать внимание и садить аккумулятор. Однако реле поворота должно сработать и в случае, когда нажата кнопка аварийной сигнализации (3). И должно работать, если выключен рычажок поворота ( 2 ) и даже если выключен двигатель ( 1 ). Инженер Винтик предложил электрическую схему, которая успешно включает и выключает реле поворота. Как можно усовершенствовать схему? ’ Задача 3.2. Скрытая цифра (š)

Отечественный прибор содержит штрих-код EAN-13 (European Article Numbering) с полосами, соответствующими цифрам 602887 000010. Определите самую первую цифру кода, не обозначенную полосами. Для правильных штрих-кодов сумма цифр, стоящих на нечетных местах, и утроенных цифр, стоящих на четных местах, делится на 10.

Скрытая цифра

’’ Задача 3.3. Избыточность штрих-кода ()

Самый распространенный для товаров штрих-код EAN-13 (European Article Numbering), состоящий из 13 цифр, кодирует цифры при помощи чередующихся светлых и темных полос. Сканер штрих-кода распознаИзбыточность ет тонкую, среднюю и широкую линии. Какое максимальное количество различных знаков можно сопосташтрих-кода вить сериям из пары светлых и пары темных полос? Сколько различных штрих-кодов может распознать сканер, сколько из них будут приняты как верные? Выходит, что помимо комбинаций, шифрующих цифры, существует множество бессмысленных комбинаций. Для чего это нужно?

Системы исчисления ’’ Задача 3.4. Считаем на пальцах (š)

Выпиши числа от 0 до 31 в четырех столбцах в десятеричной, восьмеричной, двоичной и шестнадцатеричной системах исчисления. Почему обще10

принята десятеричная система исчисления? Где встречаются другие системы исчисления? ’’ Задача 3.5. Автобиография математика (š)

Я окончил курс университета 44 лет от роду. Через год, будучи еще совсем молодым человеком, я женился на юной 34-летней девушке. Жалование у меня было в месяц всего 200 рублей, из которых 1/10 приходилось отдавать за квартиру, так что мы жили на 130 рублей в месяц. Спустя несколько лет у меня была уже небольшая семья — всего 10 человек, считая детей, меня и жену. Сколько рублей я платил в месяц за квартиру, и сколько у меня детей, если я женился в 100 лет?

Растровые изображения ’’ Задача 3.6. Оцифруй рисунок (š) 11

Черно-белый растровый рисунок размером 8х8 точек представлен столбцом из восьми 8значных двоичных чисел. Выпишите числа в 10-тичной системе исчисления. ’’ Задача 3.7. Нарисуй числа (š)

1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 Оцифруй рисунок

Черно-белый растровый рисунок размером 8х8 точек представлен столбцом из восьми 8значных двоичных чисел. Восстановите рисунок, если числа в 10-тичной системе исчисления записываются как: 0; 40; 0; 56; 68; 124; 64; 56. ’’’ Задача 3.8. Что показывают числа? (š)

Черно-белый растровый рисунок размером 16х16 точек представлен столбцом из шестнадцати 16-значных двоичных чисел. Восстановите рисунок, если числа в 16-ричной системе исчисления записываются как: 0C10; 0260; 0180; 8180; 668C; 2482; 1041; 1021; 2301; C002; 4024; 24CA; 2402; 4804; 8C08; 03F0.

11

Растр (нем. Raster, от лат. raster, rastrum - грабли, мотыга) — в полиграфии называют прямоугольную сетку, фотографируя через которую, тоновое изображение разбивают на точки.

11

ЗАНЯТИЕ 4. ВЫБОРКИ ’’ Задача 4.1. Доживем до воскресенья ("š)

Студент, проживающий в общежитии, умеет готовить четыре блюда: яичницу, картошку с луком, пельмени, особое-студенческое. Завтра студент уезжает домой. В общежитии ему осталось продержаться обед, ужин и завтрак, — сготовить 3 раза. Сколько выборов меню имеет студент? Получите 4 ответа для случаев, если повторять или не повторять блюда, если учитывать или не учитывать порядок блюд.

Сочетания ’ Задача 4.2. Звон бокалов ("š)

Десять человек поднимают бокалы. Сколько раз прозвучит «дзынь», когда каждый чокнется с каждым по разу? ’ Задача 4.3. Напиши родителям (š)

В почтовом отделении продаются открытки 5 видов. Сколькими способами можно купить 3 различные открытки? ’ Задача 4.4. Треугольник — клетка геометрии! (š)

Сколько различных треугольников можно составить, используя четыре отрезка с длинами 4, 5, 6, 7 см? На сколько увеличится число треугольников, если считать различными зеркально симметричные треугольники (например, 4,5,6 и 4,6,5)?

Сочетания с повторением ’ Задача 4.5. Напиши друзьям (š)

В почтовом отделении продаются открытки 5 видов. Сколькими способами можно купить 3 открытки, не обязательно различные? ’ Задача 4.6. Коробки (š)

Сколько можно построить различных прямоугольных параллелепипедов, длины ребер которых выражаются натуральными числами от 1 до 6? ’’ Задача 4.7. Возможные треугольники (š)

Сколько различных треугольников можно составить из неограниченного числа отрезков с длинами 1, 2, 3, 4 см? Выпишите соответствующие тре12

угольникам стороны. Исключите треугольники, не удовлетворяющие неравенству треугольника; исключите треугольники, вырождающиеся в отрезок. ’’’’ Задача Муавра12 4.8. (š)

Сколько существует упорядоченных наборов из трех неотрицательных целых чисел, дающих в сумме 10? Другими словами, сколько точек, все координаты которых — неотрицательные целые числа, принадлежат плоскости x + y + z = 10? А сколько неупорядоченных троек дают в сумме 10? ’’’’ Задача 4.9. Счастливый билетик ()

Счастливым называется билет, в котором сумма первых трех цифр совпадает с суммой последних трех цифр. Например, 848 956. Как много существует шестизначных счастливых билетов? Какова вероятность получить счастливый билетик при оплате за проезд?

ЗАНЯТИЕ 5. КОМБИНАТОРИКА ’’ Задача 5.1. Перестановки с ограниченным запасом (")

Счастливый билетик

Сколькими способами можно упорядочить буквы слова «математика»? Бессмысленные последовательности учитываются. ’’ Задача 5.2. Комбинаторика сада (")

Садовник получил 20 саженцев, чтобы посадить 5 рядов по 4 дерева в каждом. Однако выполнил задание с помощью 10 саженцев. Как выглядел сад? ’’’’ Задача 5.3. Пространства (")

Изобразите пространства близких точек, соответствующих элементам указанных ниже множеств.

12

Муавр (Moivre) Абрахам де (26.5. 1667, Витри-ле-Франсуа, - 27.11.1754, Лондон), английский математик. Задача Муавра в алгебре многочленов: степень (a + b + c)10 раскладывается на одночлены вида ax by cz.

13

а) B3 — множество троек булевых переменных (нулей и единиц). Близкими считаются тройки, которые отличаются нулем и единицей в одном положении. Например, «100» и «110». б) R2+ — множество пар положительных действительных чисел. Близкими считаются пары, для которых составляющие их первые и вторые числа близки по величине соответственно. Например, (π; e) и (3,14; 2,72). в) BxNxR —элемент этого множества состоит из булевой, натуральной и действительной величин. Близость определяется близостью составляющих величин. г) S4 — множество перестановок четырех элементов. Перестановка близка трем другим перестановкам, которые получаются из нее обменом двух соседних мест. Например, «1234» и «1324». ’’ Задача 5.4. Не перегружайте математикой! (š)

В течение 5 дней студенты должны сдать 5 зачетов, в том числе по «Дискретной математике» и «Математическому анализу». Сколькими способами можно составить расписание зачетов (по одному в день), чтобы зачеты по математике не шли друг за другом? Считайте порядок нематематических предметов значимым. ’’’’ Задача 5.5. Джентельменское правило (š)

Сколькими способами можно расставить в очередь за стипендией 5 парней и 5 девчат так, чтобы по мере уменьшения очереди парней оставалось не меньше, чем девчат? Найдите общую формулу.

Четность, перестановки ’’ Задача 5.6. Локальная сеть общежития

Покажите, что 33 компьютера нельзя соединить друг с другом так, чтобы каждый был соединен ровно с тремя другими. ’’ Задача 5.7. Тараканьи бега

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

14

’’ Задача 5.8. Наведи порядок

В шести секторах круга расставлено 6 шашек, по одной в каждом секторе. Одним ходом разрешается любые две шашки передвинуть в соседний сектор так, что одна движется по часовой стрелке, а другая − против чаНаведи порядок совой стрелки. Можно ли такими ходами собрать все шашки в одном секторе? Если да — то как? Если нет — то почему?

ЗАНЯТИЕ 6. ГРАФЫ ’’ Задача 6.1. Эйлерова характеристика13 (")

Вычислите эйлерову характеристику куба, тетраэдра, октаэдра, додекаэдра, икосаэдра, усеченного икосаэдра (футбольного мяча), куба с диагоналями-ребрами, «дырявого куба».

Тетраэдр

Куб

Футбольный мяч

Октаэдр

Додекаэдр

Куб с трещинами

Икосаэдр

Дырявый куб

Эйлерова характеристика ’’ Задача Эйлера 6.2. (")

Возможно ли обвести рисунки, не отрывая ручки от бумаги и не обводя ни одну черту повторно14? Если возможно — как? Если нет — почему? 13

Эйлерова характеристика многогранника = «количество вершин» + «количество граней» - «количество ребер». Грани — многоугольники на поверхности многогранника. Ребра и вершины многогранника — это ребра и вершины граней.

15

Задача Эйлера ’’ Задача 6.3. Волк, коза и капуста. Теория перевозки (")

В вашем распоряжении Волк, Коза, Мешок капусты и Лодка, вмещающая, помимо вас, не более одного из трех грузов. Все имущество нужно перевезти через реку. Капусту нельзя оставлять с козой, а козу − с волком. Докажите, что переправа возможна, построив связный граф положений имущества между перевозами (состояний задачи). Укажите способ обозначения состояний. Сколько возможно различных решений? Каков порядок связности получившегося графа? ’’ Задача 6.4. Ханойская башня ()

Головоломка Ханойская башня ⎯ это три стержня, на первом из которых размещено некоторое количество дисков. Диск наименьшего диаметра находится сверху, а ниже ⎯ диски последовательно увеличивающегося диаметра. Следует перекладыХанойская башня вать по одному диску со стержня на стержень так, чтобы диск большего диаметра никогда не размещался выше диска меньшего диаметра и чтобы в конце концов все диски оказались на другом стержне. Постройте граф состояний Ханойской башни для двух дисков. ’’’’ Задача 6.5. Гексафлексагон

Определите карту состояний гекса-гексафлексагона: ориентированный граф, вершины которого — различные состояния, а дуги — переходы в одно выворачивание. Определите радиус и диаметр графа, а также соответствующего неориентированного графа. Проинтерпретируйте полученные числа. Как сделать гексафлексагон, показано в приложении. 14

Такой обход графа называется эйлеровым путем.

16

’’’’ Задача 6.6. Дележ без ковша (š)

Два студента имеют полный бочонок кваса в 8 ведер, а также два пустых бочонка в 5 и 3 ведра. На боченках нет никаких измерительных засечек. Форма бочки не позволяет определить, когда она наполнена наполовину. Как студентам разделить квас поровну? Найдите кратчайшее решение, построив полный граф возможных переливаний. Укажите способ обозначения состояний. Во сколько определенных состояний воды в трех бочонках можно прийти? ’’’ Задача 6.7. Симметричный конденсатор

Имеется 5 точек в пространстве. Через каждую пару проведен соединительный провод с конденсатором емкости 1 мкФ. Найдите емкость такой батареи, если выводы подключать в любые две точки.

ЗАНЯТИЕ 7. ИНФОРМАЦИЯ Поиск ’’ Задача 7.1. Гроза фальшивомонетчиков (")

Как за 2 взвешивания среди 9 одинаковых монет обнаружить одну поддельную, которая легче настоящих? Изобразите алгоритм деревом взвешиваний. ’’’ Задача 7.2. Информативность взвешивания (š)

Докажите, что 20 взвешиваниями на чашечных весах нельзя упорядочить по массе 10 предметов. ’’’’ Задача 7.3. Придворный заговор (š)

За день до пира царь узнал, что одна из 30 бочек меда отравлена, причем действие яда проявляется лишь на следующий день. Какое минимальное количество смертников понадобится царю, чтобы выявить отравленную бочку? Опишите способ обнаружения отравленной бочки.

Защита ’ Задача 7.4. Маскарад тайнописи ("š)

Расшифруйте записанное в квадрате с помощью маски, которую надо повора-

Х

Ч А С Х Н С Т Х Х А К Ю М О Е Маскарад тайнописи

З Т Ь А

17

чивать против часовой стрелки. ’’ Задача 7.5. Военный приказ (š)

Расшифруйте записанное в квадрате с помощью маски, которую надо поворачивать против часовой стрелки. Х Х Х П Н Л А Я Е С Р Х У Т Е В Т Ь Т О Х Х Х У М П У С У Л Т Х Ф Я Р Е Л 1 А А Х Х 6 Н Н С В И Г Е Х Х Е Н Н У П И Т М Х Х Я Р Л А Б В А С Х Х А Н Р Н И Я Е И Военный приказ ’ Задача 7.6. Тарабарщина (š)

Запишите по-русски слово, каждая согласная буква которого заменена по правилам Тарабарской грамоты (простой литореи), где все согласные буквы в азбучном порядке выстроены в 2 ряда замен. ощомополнолощполкь Ö ? ракеракита Ö ? гесошет Ö ?

бвгджзклмн щшчцхфтсрп

Тарабарщина

Передача и сжатие ’’’ Задача 7.7. Русскоязычная раскладка ()

Какую нагрузку несут различные пальцы при слепой печати? КаРусскоязычная раскладка кова нагрузка рук? Почему именно такая русская раскладка клавиатуры пользуется популярностью? Возьмите частоты знаков из приложения 7. ’’’ Задача 7.8. Латинская раскладка ()

Какую нагрузку несут различные пальцы при слепой печати? Какова нагрузка рук? Почему 18

Латинская раскладка

именно такая латинская раскладка клавиатуры пользуется популярностью? Возьмите частоты знаков из приложения 7. ’’’ Задача 7.9. Телеграфная азбука Морзе

В эфире слышна морзянка. Длительность точки 1/8 секунды. Текст из 26 букв латинского алфавита идет без знаков препинания. Какова ожидаемая длительность передачи, если длина текста 1000 знаков, включая пробелы? Воспользуйтесь приложением 7. ’’’ Задача 7.10. Азбука Морзе на русский лад

В эфире слышна морзянка. Длительность точки 1/8 секунды. Текст из 31 буквы русского алфавита, исключая «ё» и «ъ», идет без знаков препинания. Какова ожидаемая длительность передачи, если длина текста 1000 знаков, включая пробелы? Воспользуйтесь приложением 7. ’’ Задача 7.11. Код личный — двоичный!

Составьте свой личный равномерный двоичный код русского языка (31 буква и пробел). Укажите правила кодировки. Запишите сообщение из двух слов. Сообщение должно содержать только нули и единицы, без пробелов и прочих знаков. ’’’’’ Задача 7.12. Сжатый код (")

Составьте оптимальный (методом Хаффмена15) префиксный двоичный код русского языка (31 буква и пробел). Воспользуйтесь приложением. Представьте полученный код в виде дерева. Запишите сообщение из двух слов. Какова средняя длина кода на один символ?

ЗАНЯТИЕ 8. ЛАБИРИНТЫ, КОМБИНАТОРНЫЕ ГОЛОВОЛОМКИ ’’ Задача 8.1. Пути и ветвления ()

Сколько кратчайших путей ведет из левого нижнего в правый верхний конец лабиринта?

Пути и ветвления

15

Хаффмен (Huffman) Дэвид А., [1925-1999], американский математик, электротехник. Алгоритм опубликован в 1952 году.

19

’ Задача 8.2. Объемный лабиринт ()

Проведите дорогу из левого нижнего в правый нижний конец лабиринта. Лабиринт не позволяет пользоваться правилом правой или левой руки. Объемный лабиринт

’’’’ Задача 8.3. Группа наперсточника

Составьте таблицу группы перестановок 3 элементов. Обладает ли операция умножения перестановок свойством коммутативности? Образуют ли четные перестановки подгруппу? ’’’ Задача 8.4. Ловушка Ллойда16 ()

В игре «Пятнашки» требуется прийти из положения слева в положение справа (повернуть расположение на 900). Если это возможно, то как? Если нет, почему?

4

8 12

1

2

3

4

3

7 11 15

5

6

7

8

2

6 10 14

9 10 11 12

1

5

9 13

13 14 15

Ловушка Ллойда

’’’’ Задача 8.5. Кубик Рубика17 ()

Кубик Рубика

16

Куб, окрашенный краской, разрезан на кубики в 3 раза меньшего размера. Сколько получилось маленьких кубиков? Сколько из них оказалось не раскрашено? Сколько раскрашено с одной, двух, трех сторон? Сколько различных состояний может принимать кубик Рубика? Точнее, до скольких состояний можно добраться, поворачивая стороны кубика на 900? Запрещается разбирать кубик, или переклеивать цветные ярлыки.

Лойд (Loyd) Сэмюель [31.01.1841, Филадельфия, 9-ый ребенок в семье – 10.04.1911, Нью-Йорк], американский изобретатель головоломок и шахматных задач, фокусник. «Пятнашки» изобретены в 1878 году. Второе имя головоломки — «такeн». Это название имеет двоякий смысл: по-французски jeu du taquin — задорная игра, по-английски takein — обман. 17 Рубик (Rubik) Эрно [13.07.1944, Будапешт], венгерский изобретатель и скульптор. Изобретенный в 1974 году кубик Рубика начал свое победное шествие по свету с 1978 года, когда с ним впервые ознакомились математики на Международном математическом конгрессе в Хельсинки.

20

ОТВЕТЫ Занятие 1. Основы Множества, отображения и отношения

’ Задача 1.1. Булеан (") Множество A = {a,b,c} имеет 8 подмножеств: {a}, {b}, {c}, {ab}, {ac}, {bc}, а также пустое множество A ∩ B = A ∪ B ∅ и само множество {a,b,c}. Множество из N элементов имеет 2N подмножеств.

’’ Задача 1.2. Доказательство на кружках /// - A , \\\ - A

A ∪ B : /// - A , \\\ - B

A∪ B

/// - B , \\\ - B /// - A , \\\ - B Второе правило де Моргана доказывается аналогично.

A∩ B

’’ Задача 1.3. Принцип Дирихле в арбузных корках (") Если 4 куска имеют 5 корок, то найдется кусок, имеющий не менее двух корок. Разрез с таким куском в центре представлен на рисунке.

’’ Задача 1.4. Отношение упорядочения Первая команда: №№1, 5, 9 Вторая команда: №№2, 6, 7 Третья команда: №№3, 4, 8

Разрез арбуза 21

Нарушается свойство транзитивности (от лат. transitivus - переходный): первая побеждает вторую, вторая — третью, но первая не побеждает третью. Ни одну команду нельзя назвать сильнейшей. Интересно, что существует только два искомых разделения на три команды (с точностью до перестановки команд). Попробуйте доказать это. Вероятности

’’ Задача 1.5. Азартная игра и справедливость (š) Каждый игрок имеет вероятность выигрыша 4/36 = 1/9. Игра справедлива. Кажущаяся несправедливость: «Женя выигрывает только в одно случае». Она преодолевается встречной несправедливостью: вероятность того, что выпадет 5 очков в 4 раза больше вероятности выпадения 12 очков.

’’ Задача 1.6. Очень широкий танк (š) Вероятность подрыва 3/18=1/6. Если танк едет наискосок, вероятность увеличивается вдвое. Указание: равновероятное множество событий удобно представлять характеристической точкой танка, например, центром танка (дулом), или правым краем (гусенницей).

’’’ Задача 1.7. В квадратном часе (š) Вероятность встречи 5/9. Указание: пространство всех равновозможных событий представляет собой квадратный час, в котором несложно вычислить площадь, занимаемую благоприятными событиями. Занятие 2. Количество и порядок 1 ’’ Задача 2.1. Числа количественные и порядковые 11 (") 21 Смотрите рисунок. 1211 Правило сложения (включения-исключения) множеств 111221 312211 ’’ Задача 2.2. Правило гусениц 13112221 Длины равны. Если принять длины гусениц за А и В, то 1113213211 Пересечение гусениц: (A и B) равняется свободной ... ветке A + B − (A или B), где A + B — длина всей ветки. Числа количеA∪ B = A+ B − A∩ B ственные и порядковые ’’ Задача 2.3. Правило красок () Понадобится равное количество краски, т.к. площади равны: ( A1 ∩ A2 ) + ( A2 ∩ A3 ) + ( A3 ∩ A4 ) + ( A4 ∩ A1 ) = A1 + A2 + A3 + A4 − ( A1 ∪ A2 ∪ A3 ∪ A4 )

22

Слева площадь в клеточку, справа площадь в точку. A1,2,3,4 — равные площади малых кругов, сумма которых равняется площади большого круга, так как радиусы малого и большого кругов отличаются в 2 раза.

’’ Задача 2.4. Инспектор запутался (š) Условие задачи:

Н: 24

НИ: 10

Исключение: И: 40

НФИ: 5

НФИ: -1

НФИ: 5

НФИ: 5 ФИ: 8

НФ: 20

НФИ: 27

НФИ: 3

НФИ: 15

Ф: 50

НФИ: 27

Н — немецкий язык, Ф — французский, И — испанский. Выходит, что только немецкий язык изучает “-1” человек! А всего на потоке учится 81 студент.

’’ Задача 2.5. Куратор недосчитался (š) Условие задачи:

С: 28

СП: 18

Исключение: П: 25 СОП: 3

СОП: 10

СОП: 10 ОП: 16

СО: 17

СОП: 1

СОП: 8

СОП: 7 О: 30

СОП: 6 СОП: 7

С — спортсмены, О — отличники, П — парни. Выходит, что всего на потоке учится 42 студента. Правило умножения

’ Задача 2.6. Считалочка 12 ребят х 3 лукошка х 1 кошка х 12 котят = 432 котенка, 432 котенка х 4 мышонка = 1728 мышат.

’’ Задача 2.7. Не роскошь, а средство передвижения () Русская азбука: АБВГДЕЁЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ Латинский алфавит: ABCDEFJHIJKLMNOPQRSTUVWXУZ. Общие буквы: АВЕКМНОРСТУХ — 12 букв. 23

123 букв х (103 – 1) чисел + 1 = 1726273 1726273-ему автомобилю не хватит номера с пометкой 24RUS. Стоит отметить, что население края почти вдвое превышает эту цифру.

’ Задача 2.8. Ладейное перенаселение (") В каждом ряду располагается одна и только одна ладья. Для каждой из 8 возможностей поставить ладью в первый ряд существует 7 возможностей поставить ладью во второй ряд и так далее. Всего существует 8 х 7 х 6 х 5 х 4 х 3 х 2 х 1 = 8! = 40320 возможностей расставить 8 ладей так чтобы они не били друг друга. 9 ладей расставить невозможно, так как по принципу Дирихле найдется ряд, в котором стоит не менее двух ладей, которые бьют друг друга. Занятие 3. Представления строки 1 2 3 Выход ’’’ Задача 3.1. Электронная логика (") - - Самая простая схема показана на рисунке. - - + + Легко убедиться, что приведенная электрическая - + цепь выдает ту же логическую функцию, что и ис- - + + + ходная. Подробное решение подобной задачи приве- + - дено в [4], стр. 29. + - + + + + + + + + + Простая схема

’ Задача 3.2. Скрытая цифра (š) Штрих-код имеет вид X602887 000010, где X — искомая цифра. Складываем цифры, стоящие на четных местах штрик-кода 6 + 2 + 8 + 0 + 0 + 1 = 17 Полученную сумму умножаем на три 17 * 3 = 51 Складваем цифры, стоящие на нечетных местах X + 0 + 8 + 7 + 0 + 0 + 0 = X + 15 Складываем числа, полученные в предыдущих пунктах X + 15 + 51 = X + 66 — это число делится на 10 Отбрасываем десятки X + 6 = 10, X = 10 – 6 = 4 Ответ: Не обозначенная полосами цифра — «4».

24

’’ Задача 3.3. Избыточность штрих-кода () Если сканер штрих-кода распознает 3 вида полос: П = {тонкая, средняя, широкая}, то набор из четырех полос — это элемент прямого произведения П4, содержащего 34=81 элемент. Это позволяет кодировать не 10 цифр, а 81 знак. Однако 71 комбинация полос остается бессмысленной. Вообще из 40 полос можно составить 348 = 79766443076872509863361 ≈ 8 1022 штрих-кодов, однако лишь 1012 из них оказываются верными. Если сканер собьется при считывании комбинации полос, то с подавляющей вероятностью получится несуществующий штрих-код, и сканер потребует повторить считывание. Таким образом, избыточность кода предотвращает ошибочное считывание. Системы исчисления

’’ Задача 3.4. Считаем на пальцах (š) Перечисления содержатся в приложении 2. Указание. Начинайте считать на пальцах, пользуясь не 10-ю, а 8-ю пальцами. Получится счет в 8-ричной системе исчисления. Как только загнете восьмой палец, не пишите «8» (в 8-ричной системе исчисления нет цифры «8»), а напишите «10» (не один «десяток», а одна «восьмерка»), и начинайте считать единицы второй «восьмерки». Вся электронно-цифровая техника сегодня основывается на двоичной системе исчисления, хотя в истории электроники испытывались и компьютеры на троичной системе исчисления. Штрих-код основан на троичной системе исчисления. В языках многих народов сохранились указания на двенадцатеричную систему исчисления (английские «цифры» «eleven» — «11», «twelve» — «12», в отличие от составного «thirteen» — «три на десять (дцать)»; немецкие elf, zwölf, в отличие от dreizehn). Оборот Луны (месяц) приблизительно в 12 раз чаще, чем оборот Солнца (год). В древнем Египте использовалась 60-ричная система исчисления, 60 различных цифр! Однако, сегодня общепринята 10-ричная система исчисления. И, пожалуй, основная тому причина — 10 пальцев на двух человеческих руках.

’’ Задача 3.5. Автобиография математика (š) Кажущаяся несуразность рассказа венчается тем, что 44 + 1 = 100. Следовательно, повествование идет в пятеричной системе исчисления. В обычной для нас десятеричной системе рассказ представляется таким. «Я окончил курс университета 4*5 + 4 = 24 лет от роду. Через год, будучи еще совсем молодым человеком, я женился на юной 3*5 + 4 = 19-летней девушке. Жалование у меня было в месяц всего 2*52 = 50 рублей, из кото25

рых 1/(1*5) = 1/5 приходилось отдавать за квартиру, так что мы жили на 1*52 + 3*5 = 40 рублей в месяц. Спустя несколько лет у меня была уже небольшая семья — всего 1*5 = 5 человек, считая детей, меня и жену. Сколько рублей я платил в месяц за квартиру, и сколько у меня детей, если я женился в 1*52 = 25 лет?». Ответ теперь очевиден. Растровые изображения

’’ Задача 3.6. Оцифруй рисунок (š) Запись в десятичной системе исчисления приведена справа 1 1 0 0 0 0 0 0

0 1 1 1 0 0 0 0

0 1 1 1 1 1 0 0

0 0 1 1 1 0 0 0

0 0 1 0 1 1 0 0

0 0 0 0 0 1 1 0

0 0 0 0 0 0 1 1

0 0 0 0 0 0 0 1

128 224 120 112 56 44 6 3

0 0 0 0 1 1 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 40 0 56 68 124 64 56

’’ Задача 3.7. Нарисуй числа (š) 0 0 0 0 0 0 0 0

0 0 0 0 1 1 1 0

0 1 0 1 0 1 0 1

0 0 0 1 0 1 0 1

0 1 0 1 0 1 0 1

’’’ Задача 3.8. Что показывают числа? (š) 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0

26

0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0

0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0

0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0

0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1

0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1

1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 0

1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1

0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1

0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1

0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0

0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0

0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0

0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0

0 C 1 0 0 2 6 0 0 1 8 0 8 1 8 0 6 6 8 C 2 4 8 2 1 0 4 1 1 0 2 1 2 3 0 1 C 0 0 2 4 0 2 4 2 4 C A 2 4 0 2 4 8 0 4 8 C 0 8 0 3 F 0

Занятие 4. Выборки

’’ Задача 4.1. Доживем до воскресенья ("š) Ответ содержится в приложении 4 (m=4,w=3). Разъяснения — в приложении 3. Сочетания

’ Задача 4.2. Звон бокалов ("š) Способ 1. Все сочетания из десяти бокалов по два образуют «дзинь». 10! 10 ⋅ 9 = = 45 2!8! 1 ⋅ 2 Способ 2. Каждый бокал произвел «дзинь» 9 раз, а каждый «дзинь» был произведен двумя бокалами. 90/2=45. Способ 3. Первый бокал чокнулся с 9-ю оставшимися. Второй — с 8-ю, не считая первого. Третий — с 7-ю, не считая первых двух. И так далее 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0 = 45. Способ 4. Если вершины некоторого Способы 2, 3 10-угольника сопоставить бокалам, то соударения бокалов будут соответствовать сторонам и диагоналям 10-угольника. Пересчитайте их. C102 =

’ Задача 4.3. Напиши родителям (š) C53 = 10

Способ 4

’ Задача 4.4. Треугольник — клетка геометрии! (š) C43 = 4 треугольников и еще 4 зеркально симметричных.

Указание: можно перечислять не тройки отрезков, являющихся сторонами треугольника, а отрезки, не являющиеся сторонами треугольника. C43 = C44 −3 = 4

Сочетания с повторением

’ Задача 4.5. Напиши друзьям (š) C53 =

7! 7 ⋅ 6 ⋅ 5 = = 35 4!3! 1 ⋅ 2 ⋅ 3

’ Задача 4.6. Коробки (š) C63 =

8! 8 ⋅ 7 ⋅ 6 = = 56 5!3! 1 ⋅ 2 ⋅ 3

27

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

’’ Задача 4.7. Возможные треугольники (š) 6! 6 ⋅ 5 ⋅ 4 = = 20 не упорядоченных с повторением троек 3!3! 1 ⋅ 2 ⋅ 3 отрезков. Все их можно определить, заполнив таблицу в приложении 3. Именно 111, 112, 113, 114, 234, 221, 222, 223, 224, 134, 331, 332, 333, 334, 124, 441, 442, 443, 444, 123. Подчеркнуто 4 треугольника, вырожденные в отрезок. Зачеркнуто 3 треугольника, невозможных по неравенству треугольника.

Возможно C43 =

’’’’ Задача Муавра 4.8. (š) 12! 12 ⋅ 11 = = 66 2!10! 1 ⋅ 2 10 раз выбираем одну из величин x, y или z. Сколько раз выбрана величина, таково ее значение. Полезно для решения следующей задачи нарисовать целочисленные узлы кубической решетки, принадлежащие треугольнику

C310 =

⎧ x + y + z = 10, ⎨ ⎩ x, y , z ≥ 0,

и пересчитать их. Неупорядоченным тройкам соответствуют узлы, расположенные на одной шестой части указанного треугольника. Их насчитывется 14.

’’’’ Задача 4.9. Счастливый билетик () Ответ: 55252 счастливых билета. Почти каждый 18-ый билет. Условимся называть сумму трех цифр просто суммой. Из 1000 упорядоченных троек цифр только «000» обладает суммой 0. Суммой 1 обладают три тройки: «001», «010», «100». Сумма равна 2 в шести случаях: «002», «020», «200», «011», «101», «110» и так далее.

28

Подсчет счастливых билетиков Сумма

Тройки все- Тройки с Пересечения Количество возможных двухначными в лишних троек цифр чисел числами тройках

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Итого

1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210 231 253 276 300 325 351 378 406

0 0 0 0 0 0 0 0 0 0 3 9 18 30 45 63 84 108 135 165 198 234 273 315 360 408 459 513

Количество счастливых билетов

1 3 6 10 15 21 28 36 45 55 63 69 73 75 75 73 69 63 55 45 36 28 21 15 10 6 3 1 1000

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 9 18 30 45 63 84 108

1 9 36 100 225 441 784 1296 2025 3025 3969 4761 5329 5625 5625 5329 4761 3969 3025 2025 1296 784 441 225 100 36 9 1 55252

80 70 60 50 40 30 20 10

(а)

26

24

22

20

18

16

14

12

10

8

6

4

2

0

0

(б)

(а) Каждая из 1000 х 1000 точек рисунка соответствует некоторому билету. По осям откладываются первое и второе трехзначные числа, причем числа упорядочены по сумме цифр. Черными точками обозначены счастливые билеты. (б) Распределение трехзначных чисел по сумме цифр.

29

Счастливый билет с суммой 0 уникален: «000 000»18. Счастливых билетов с суммой 1 существует 3 х 3 = 9. Сумма 2 встречается в 6 х 6 = 36 счастливых билетах и так далее. Полный расчет приведен в таблице. Сделаем спорное предположение, что все номера билетов равновероятны. Тогда вероятность взять в автобусе счастливый билет 5,5252%. Общая формула для количества счастливых билетов: 27

K = ∑ ( C3i − 3C3i −10 + 3C3i − 20 ) . 2

i =0

Однако геометрические соображения предыдущей задачи позволяют получить тот же ответ проще. Примечание. В задаче «Азартная игра и справедливость» рассматривалось распределение суммы двух равномерно распределенных показаний игральных кубиков (дискретный аналог распределения Симпсона). В задаче о счастливом билетике строится распределение суммы трех равномерно распределенных цифр. Это распределение сильнее приближается к нормальному и тем самым служит прекрасным примером на центральную предельную теорему теории вероятностей. Занятие 5. Комбинаторика

’’ Задача 5.1. Перестановки с ограниченным запасом (") В слове «математика» 2 буквы «м», 3 «а», 3 «т», 1 «е», 1 «и», 1 «к». 10! = 10 ⋅ 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 = 151200 2!3!2!1!1!1! различных слов можно составить из букв слова «математика». P (10;2,3,2,1,1,1) =

’’ Задача 5.2. Комбинаторика сада (") Два примера приведены на рисунке. Два других примера постройте самостоятельно. Комбинаторика сада

18

Кондуктора говорят, что такой билет существует.

30

’’’’ Задача 5.3. Пространства (")

(а) Булев куб

(б) Четверть плоскости

(в) Два ряда прямых

(г) Усеченный октаэдр (подробнее в [2], стр. 33)

’’ Задача 5.4. Не перегружайте математикой! (š) Ответ: Возможно 72 расписания. Всего существует 5! = 120 расписаний — размещений пяти дисциплин по пяти дням недели. Причем, математические дисциплины можно разместить в расписании 5 х 4 = 20-ю способами, для каждого из которых имеется 3! = 6 способов разместить остальные предметы. Из двадцати размещений математических предметов мы должны исключить 8 запрещенных, когда предметы поставлены в соседние дни. Остается 12 х 6 = 72 возможности.

’’’’ Задача 5.5. Джентельменское правило (š) 10! 10 ⋅ 9 ⋅ 8 ⋅ 7 = 42 . ( 6 − 5) = 6!5! 1⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 Указание. Рассмотрите взаимно однозначное соответствие между очередями из 10 человек и монотонными путями по ребрам квадратной решетки 5 х 5. Подробнее смотрите задачу о лабиринте «Пути и ветвления», приложение , а также [13] на стр. 269-275. 31

Ответ: C55+5 − C54+5 =

Четность, перестановки

’’ Задача 5.6. Локальная сеть общежития Каждый компьютер имеет три выхода, всего 3 х 33 = 99 входов. Каждое соединение можно представить проводом, имеющим два выхода. Число входов нечетное, поэтому хотя бы один вход останется пуст.

’’ Задача 5.7. Тараканьи бега Пусть таракан пробежал N сторон в направлении вверх. Так как таракан вернулся в исходную точку, то и в направлении вниз он пробежал N сторон. Каждый раз он поворачивал под прямым углов, то есть бежал попеременно то вверх или в низ, то вправо или влево. Следовательно, вправо и влево он пробежал столько же, сколько вверх и вниз, то есть, 2N сторон. Всего 4N сторон за целое число N секунд.

’’ Задача 5.8. Наведи порядок Белизной расстановки назовем количество шашек, стоящих на белых (четных) секторах. В исходном положении белизна равна трем. В конечном положении она равна шести, либо нулю. Как может поменяться четность белизны? Ведь если при ходе обе шашки двигаются из закрашенных (нечетных) секторов, то белизна увеличивается на 2. Если же обе шашки берутся из белых секторов, белизна уменьшается на 2. И, наконец, если ходят шашки, принадлежащие секторам различного цвета, белизна не меняется. В любом случае четность белизны — величина сохраняющаяся. И собрать шашки в одном секторе невозможно. Примечание. Если разрешить шашкам ходить в одном направлении, например, обе шашки двигать по часовой стрелке, то ответ не изменится. Занятие 6. Графы

’’ Задача 6.1. Эйлерова характеристика (") Очень полезно честно обсчитать многогранники. Так, для четырехгранника (тетраэдра) вершин и граней — по 4, а ребер — 6: 4 + 4 – 6 = 2. Для куба и октаэдра 8 + 6 – 12 = 6 + 8 – 12 = 2. Двойка не получается только для куба с дыркой. Почему? Это легко понять, используя понятия развертки, склейки и графа-дерева. Итак, развертка многогранника — это многоугольник, составленный из всех граней многогранника, соединенных частью ребер так, что будучи перегнутой по ребрам, развертка дает поверхность многогранника. Чтобы соединить оставшуюся часть ребер, обычно оставляют язычки на ребрах 32

развертки. Если же язычков не оставлять, то придется отдельно изготовить «склейку»: склеивающие язычки-ребра из липкой ленты. Развертка четырехгранника представляется в виде графа, вершинами которого являются середины граней, а ребрам соответствуют ребра четырехгранника. Склейка также представляет собой граф. в данном примере графы развертки и склейки эквивалентны. Оба графа односвязны и не имеют циклов, то есть являются деревьями. Это значит, что число ребер в каждом из них на единицу меньше числа вершин: ⎧ Грани − Ребра развертки = 1 ⎧4 − 3 = 1 +⎨ +⎨ ⎩ Вершины − Ребра склейки = 1 , для четырехгранника ⎩ 4 − 3 = 1 Грани + Вершины − Ребра = 2 4+4−6=2

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

19

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

33

’’ Задача Эйлера 6.2. (") Ответ: (а,в,г) — обход существует, (б) — нет.

Эйлеров путь на графе. Числа отмечают последовательность обхода вершин. Круги обозначают ловушки.

Мосты в Кенигсберге Вершины нечетной степени назовем ловушками графа и пометим кружками. В ловушке число выходов не равно числу входов. Если выходов меньше, то в ловушке путь заканчивается, если выходов больше, то в ловушке путь начинается. Не отрывая ручки от бумаги, можно нарисовать либо две ловушки (начало и конец линии), либо ни одной (когда начало и конец совпадают). Эти две возможности соответствуют случаям (а) и (в). Случай (г) рассмотрите самостоятельно. В графе (б) четыре ловушки, поэтому при рисовании придется сделать хотя бы один разрыв линии. Примечание 1. Число ловушек в графе всегда четно, так как четна сумма степеней всех вершин графа. Смотрите задачу «Локальная сеть общежития». Примечание 2. Метод однократного обхода ребер графа был разработан Леонардом Эйлером при попытке найти маршрут для обхода мостов в Кенигсберге (ныне Калининград). Можно ли обойти все мосты по разу, не выходя за пределы карты и не пускаясь вплавь?

’’ Задача 6.3. Волк, коза и капуста. Теория перевозки (") Вообще возможно 16 состояний, когда на левом берегу остается любое подмножество множества {ВКМЛ} из четырех элементов. Однако, 6 из этих состояний недопустимы, 34

Волк, Коза и Мешок капусты. Л — лодка, ~ — река.

когда Коза остается на любом берегу без Лодки, но с Мешком, с Волком, либо с обоими одновременно. Остальные 10 состояний связаны переправами. Граф двусвязный, возможно два решения.

’’ Задача 6.4. Ханойская башня ()

Ханойская башня

Каждый диск независимо от другого может находиться на одном из трех стержней. Поэтому допустимых состояний 32 = 9. Состояния сопоставляются элементам прямого произведения множества стержней на себя: {123}x{123}. Первая цифра указывает положение тяжелого диска, вторая — легкого. Диски перекладываются с одно стержня на другой за 3 хода. Например, (11) Æ (13) Æ (23) Æ (22).

’’’’ Задача 6.5. Гексафлексагон У гекса-гексафлексагона 36 треугольных поверхностей, 6 из которых одновременно видны. Таким образом, в различных состояниях можно увидеть 36/6 = 6 различных рисунков. К тому же, некоторые из них могут являться в перевернутом виде. Экспериментально обнаруживается 9 различных состояний, связанных путями, указанными на рисунке. Ориентированный граф имеет диаметр 6. Это длина кратчайшего пути между наиболее удаленными состояниями. Например, 4 Æ 3 Æ 1 Æ 2 Æ 3 Æ 2 Æ 6. Радиус графа равен 4. Это длина кратчайшего пути от одной из центральных вершин до наиболее удаленной от нее вершины. Например, 1 Æ 2 Æ 3 Æ 2 Æ 6. Радиус больше полудиаметра, Карта гексаэто говорит о высокой связногексафлексагона. сти графа. Соответствующий неориентированный граф имеет диаметр 3 и радиус 2. Можно сделать вывод, что любой гекса-гексафлексагон собирается за 2 хода (!), если разрешается как открывать, так и закрывать сторону. Совет. Во время составления карты не путайте стороны гекса-гексафлексагона. На тыльной стороне риСостояния сунки появляются в другой последовательности. и траектории ’’’’ Задача 6.6. Дележ без ковша (š) переливаний Ответ: Возможно 16 состояний. Чтоьбы разделить квас 35

пополам, необходимо совершить по меньшей мере 7 переливаний. Обозначим объем кваса в боченках 3, 5 и 8 через x,y и z. Состояние полностью определяется количеством кваса в 3-х и 5-литровом сосудах. Поэтому можно обозначать состояние точкой в прямоугольнике 3 х 5 с координатами x,y (рисунок). Переливания x-z соответствуют горизонтальным траекториям, на которых определены лишь крайние положения: x = 0 или x = 3 (ведрам). То есть переливание может прекратиться только когда один из бочонков пуст, либо полон. Промежуточные состояния неизмеримы, так как по условию на бочонках нет засечек. Далее, переливания y-z соответствуют вертикальным траекториям. А переливания x-y соответствуют наклонным траекториям вида x + y = const. На рисунке определенные состояния выделены кружками, а начальное и искомое состояния — звездочками. Кратчайший путь обозначен жирной ломаной. Второй путь, встречный, имеет длину 8 переливаний.

’’’ Задача 6.7. Симметричный конденсатор Ответ: 5/2 мкФ. Замечание 1. Если выводы подключать в любые две из пяти точек, емкость окажется одна и та же, так как граф конденсаторных соединений — полный, а, следовательно, симметричный граф. Замечание 2. Если вместо конденсаторов стоят сопротивления в 1 Ом, то общее сопротивление окажется 2/5 Ома. Указание. Три промежуточных узла цепи имеют одинаковый потенциал, поэтому соединяющие их конденсаторы можно не рассматривать: либо соедините эти три узла в один, либо просто уберите три связывающих конденсатора. Решение легко обобщается на любое число вершин. Занятие 7. Информация Поиск

’’ Задача 7.1. Гроза фальшивомонетчиков (") Девять монет обозначены буквами abcdefghi.

36

Дерево взвешиваний. Проход дерева через два взвешивания приводит к фальшивой монете.

’’’ Задача 7.2. Информативность взвешивания (š) В общем случае все предметы различны по массе. Допустим, существует алгоритм взвешиваний. Тогда для алгоритма существует дерево взвешиваний. Дерево алгоритма должно иметь не менее 10! = 3628800 свободных вершин, так как все 10! упорядочений предметов по массе изначально возможны и требуют проверки. С другой стороны, могут рассматриваться лишь два случая: перетягивает левая или правая чаша. Случай равновесия учитываться не должен. Таким образом, из узла дерева идет не более двух ветвей. Двоично ветвящееся дерево с 20-ю уровнями ветвления имеет не более 220 = 1048576 свободных вершин. Получилось противоречие.

’’’’ Задача 7.3. Придворный заговор (š) Требуется 5 смертников.

Смертники

Бочки 1 2 3 4 5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

29 # # #

30 # # #

31 # # # #

#

32 # # # # #

Соответствие подозрительных бочек и выпивших из них смертников. 37

Приведем возможный алгоритм. Для упрощения алгоритма, добавим еще две бочки с водой (№№31,32). Как видно из таблицы, первый смертник прикладывается к половине бочек с номерами больше 16 (вторая партия). Уже по этому одному смертнику можно определить 16 не отравленных бочек. Если через сутки он будет здоров, на пир можно отрядить последние 16 бочек. Иначе отравлена одна из бочек второй партии и первая партия годится для пира. По составу всех пострадавших смертников, можно однозначно определить столбец таблицы. Ведь столбцы представляют собой двоичную запись чисел от 0 до 31. Замечание 1. Существуют непредусмотренные алгоритмом обстоятельства, как-то несвязанная с бочками болезнь смертника, или его исключительный иммунитет, или, наконец, недостоверность сведений о том, что ровно «одна» бочка отравлена. Замечание 2. Как и в предыдущей задаче допускается описание на языке двоичного дерева. Так, для пяти смертников возможно 25 = 32 различных исхода. А требуется различить 30 исходов. Еще общее, бочки — это «возможные события», смертники — «отображающие объекты, биты20». Количество бочек-событий можно считать мерой информации, скрытой в бочках. Количество смертников-битов — информативность алгоритма. Очевидно, эти меры разные. Количество событий зачастую огромная и неудобная мера. А количество бит — это порядок двоичного числа, записывающего количество событий, логарифм количества событий. Итак, сообщение «одна из 30 бочек отравлена» требует еще log 2 30 ≈ 5 бит информации, чтобы определить отравленную бочку. Защита

’ Задача 7.4. Маскарад тайнописи ("š) Ответ: ЗНАЮЧТОЕСТЬМАСКА Æ «Знаю, что есть маска».

’’ Задача 7.5. Военный приказ (š) Ответ: НАСТУПЛЕНИЕПЛАНИРУЕТСЯ16СЕНТЯБРЯ5УТРАВНИМАНИЕЛЕВ ОМУФЛАНГУРВСА Æ «Наступление планируется 16 сентября 5 утра. Внимание левому флангу. РВС (Революционный военный совет)».

20

Бит (от англ. binary - двоичный и digit - знак, цифра), то же, что двоичная единица измерения количества информации.

38

’ Задача 7.6. Тарабарщина (š) Ответ: Обороноспособность (это слово можно угадать сразу, в нем 6 букв «о»), математика, человек. Передача и сжатие

’’’ Задача 7.7. Русскоязычная раскладка () Сложим частоты букв, нажимаемых одним пальцем. Затем сложим частоты пальцев каждой руки. Левая рука – 0,5265

Правая рука – 0,4735

Мизинец Безымянный Средний Указательный Большой Большой Указательный Средний БезымянныйМизинец

0,028 0,035 0,111 0,277 0,07550,0755 0,272 0,060 0,034 0,032 Нагрузка пальцев рук при печати на русскоязычной клавиатуре. Сразу бросается в глаза то обстоятельство, что левая рука нагружена сильнее. Из 1000 нажатий клавиш на нее приходится 526-527. Разве клавиатура предназначена для левшей? Но, возможно, это компенсируется неучтенными клавишами абзаца («ввод») и возврата («забой»). В готовом художественном тексте ввод встречается один раз на 200 знаков, а возврат вообще не встречается. Однако, на деле это очень частые клавиши. Не учтены и знаки препинания «,.» (кстати, в русском языке запятая встречается чаще). Но тогда почему правый мизинец работает больше безымянного пальца? Раскладка «ЙЦУКЕН» не обеспечивает наискорейший набор, малую частоту опечаток, быструю обучаемость или удобство при работе. Ведь изобрели раскладку еще до революции и не в России21. К тому же при обилии букв в азбуке существенный выигрыш давало бы удлинение клавиатуры на две-три клавиши, как на клавиатурах советстких компьютеров. С другой стороны, раскладка придумана не произвольно. Большинство частых букв находится в центре. А причины распространенности раскладки следует искать в привычке и неприхотливости пользователей.

21

В СССР первая пишущая машинка (модель "Яналиф") была выпущена только в 1929 году в Казани. Вначале она производилась с латинским шрифтом. Это значит, что как минимум 30 лет с момента появления на рынке все пишущие машинки с русским шрифтом были иностранного производства. Подробнее читайте на http://ergosolo.ru/rus/reviews/keyboard_layout/

39

Частоты нажатия основных клавиш раскладки «ЙЦУКЕН»

’’’ Задача 7.8. Латинская раскладка () Сложим частоты букв, нажимаемых одним пальцем. Затем сложим частоты пальцев каждой руки. Левая рука – 0,561

Правая рука – 0,439

МизинецБезымянный СреднийУказательный БольшойБольшойУказательныйСреднийБезымянныйМизинец

0,064 0,071 0,156 0,175 0,095 0,095 0,174 0,060 0,097 0,013 Нагрузка пальцев рук при печати на русскоязычной клавиатуре. Несоразмеренность работы пальцев и рук сильнее, чем на русскоязычной раскладке. Видно, что раскладка Шоулза22 «QWERTY» не самая удобная. Существует два мнения на этот счет. Согласно первому, раскладка "QWERTY" оптимизирована под первые механические печатные машинки, где решалась проблема столкновения печатающих кулачков. Позднейшие изыскания профессора статистики Дворака и ныне существующей фирмы Малтрон дают в умелых руках на электронных клавиатурах чуть ли не удвоенную продуктивность по набору текста: скорость, снижение опечаток и прочее. Но удобные раскладки, как новые стандарты, не могут выйти на рынок по экономическим и социальным законам. Согласно второму мнению, эксперименты Дворака были подстроены. И на деле возможные улучшения раскладки дают ничтожный выигрыш.

22

Шоулз (Sholes) Кристофер [14.02.1819 – 17.02.1890], американский журналист, в 1868 году получивший патент на изобретение пишущей машинки, а в 1873 году — на изобретение раскладки «QWERTY».

40

Частоты нажатия основных клавиш раскладки «QWERTY»

’’’ Задача 7.9. Телеграфная азбука Морзе Ответ: ~ 17 минут. На 1000 знаков англоязычного текста, согласно приложению, ожидается 190 пробелов, длительность каждого — 2 четверти секунды, всего 380 четвертей. Далее встретится в среднем 97 букв «e», длительность каждой из которых — 2 четверти секунды, всего 194 четверти. И так далее... 380("_") + 194(" e ") + 237(" t ") + 256(" a ") + 448(" o ") + ... = = 4041(сек / 4) = 1010, 25 сек = 16 мин 50 1 4 сек

’’’ Задача 7.10. Азбука Морзе на русский лад Ответ: ~ 19 минут. На 1000 знаков англоязычного текста, согласно приложению, ожидается 151 пробел, длительность каждого — 2 четверти секунды, всего 302 четверти. Далее встретится в среднем 94 буквы «о», длительность каждой из которых — 7 четвертей секунды, всего 658 четвертей. И так далее... 302("_") + 658(" о ") + 148(" е ") + 256(" a ") + 180(" и ") + ... = = 4586(сек / 4) = 1146,5 сек = 19 мин 6 1 2 сек

41

’’ Задача 7.11. Код личный — двоичный! Возможный равномерный шифр Знак пробел а б в г д е ж з и

0 0 0 0 0 0 0 0 0 0

Шифр 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0

й к л м н о п р с т у

0 1 0 1 0 1 0 1 0 1

0 0 0 0 0 0 1 1 1 1 1

1 1 1 1 1 1 0 0 0 0 0

0 0 1 1 1 1 0 0 0 0 1

1 1 0 0 1 1 0 0 1 1 0

0 1 0 1 0 1 0 1 0 1 0

ф х ц ч ш щ ы ь э ю я

1 1 1 1 1 1 1 1 1 1 1

0 0 0 1 1 1 1 1 1 1 1

1 1 1 0 0 0 0 1 1 1 1

0 1 1 0 0 1 1 0 0 1 1

1 0 1 0 1 0 1 0 1 0 1

«ученье свет» зашифруется как 1010011000001100111011100001100000010010000110011010011

А как расшифруется 01110001101010011000001100111011100001100000010011111000110100001?

’’’’’ Задача 7.12. Сжатый код (") Возможный оптимальный префиксный шифр знак

код

пробел 0

42

1

1

а

1

0

0

1

б

1

0

0

0

1

в

0

0

1

1

1

г

1

0

1

0

0

д

1

1

0

1

1

е

0

0

0

1

ж

0

0

0

0

1

0

з

1

0

1

0

0

0

и

1

0

1

1

1 1

0

й

0

0

0

0

0

к

1

0

1

0

л

0

0

1

м

1

1

н

0

о

ф

0

0

0

0

0

0

0

1

х

0

0

0

0

1

0

1

0

1

ц

1

0

0

0

0

0

0

0

1

0

ч

1

0

0

0

0

1

1

0

1

ш

1

0

0

0

0

0

1

1

1

1

щ

1

0

0

0

0

0

0

0

п

1

1

0

0

1

ы

0

0

0

0

1

1

р

0

0

1

0

0

ь

1

0

0

0

1

0

с

0

0

1

1

0

э

0

0

0

0

0

0

0

0

т

0

1

0

0

ю

0

0

0

0

0

0

0

1

у

1

1

0

0

я

0

0

0

0

0

1

0

0

1

0

0

1

1

0

Дерево получения оптимального шифра

«ученье свет» теперь зашифруется как 11000100001000101011000100001011001100011100010100. 50 знаков вместо 55 для равномерного кода. А как расшифруется 01010001110001000010001010110001000010110100100010110101001?

Занятие 8. Лабиринты, комбинаторные головоломки

’’ Задача 8.1. Пути и ветвления () Ответ: 100 кратчайших путей. Указание. Для подсчета удобно считать количество путей, приходящих в каждую вершину, складывая пути, приходящие из предыдущих вершин.

’ Задача 8.2. Объемный лабиринт ()

Объемный лабиринт

43

’’’’ Задача 8.3. Группа наперсточника Каждой перестановке соответствует размещение трех элементов в трех местах. Следовательно перестановок 3! = 6. Если пронумеровать элементы, то размещение {123} под действием перестановок будет переходить в одно из 6 размещений: {123}, {312}, {231}, {213}, {132} или {321}. Введем краткие обозначения перестановок. Для этого представим элементы расположенными в вершинах равностороннего треугольника. {123} Æ {123}: Û — все остается на месте, тождественная перестановка; {123} Æ {312}: — элементы переходят по кругу; {123} Æ {231}: — элементы переходят против круга; {123} Æ {213}: — обмениваются первые два элемента; {123} Æ {132}:  — обмениваются последние два элемента; {123} Æ {321}: — обмениваются первый и последний элементы; В самом деле, перестановки соответствуют всем самосовмещениям равностороннего треугольника. Тождественное совмещение, два поворота вокруг центра и три отражения (или поворота вокруг высот). Последовательное выполние двух поворотов по кругу приводит к повороту против круга: х = . Таким образом, заполняется таблица умножения. Последовательность перестановок существенна. Так, если сначала сместить {123} по часовой стрелке в {312}, а затем поменять первые два элемента {132}, то в результате первый элемент останется на месте, а х =  . Если же поменять последовательпоследние обменяются: ность действий, то на месте останется второй элемент: х = . 2

Û



Û Û



1

х

Û  Û

  Û





Û

Û  Таблица умножения группы перестановок трех элементов. Первый множитель в левом столбце, второй — в верхнем ряду.

44

Таблица показывает, что для перестановок выполняются все определяющие свойства группы. 1. Произведение перестановок всегда перестановка. 2. Единичный элемент Û. 3. Каждый элемент имеет обратный. Например, -1 = : х = х =Û. 4. Порядок выполения умножений не важен, например, ( х  ) х = х ( х ) =  , хотя порядок множителей важен. Перестановка, переставляющая местами только 2 элемента называется парной перестановкой, или "обменом". Любую перестановку можно разложить в произведение обменов. Число множителей при разложении разными способами данной перестановки в произведение обменов всегда будет либо чётным, либо нечётным. В соответствии с этим и перестановку называют либо чётной, либо нечётной. Например, обмен — нечетная перестановка. С другой стороны, четность перестановки — это четность числа неупорядоченностей. Например, в {123} все числа упорядочены по возрастанию, число упорядоченностей 0 — четное, соответствующая перестановка Û — четная. А в {312} две неупорядоченности, т.к. 3 стоит впереди 1 и впереди 2. Следовательно тоже четная перестановка. Итак, Û — четная перестановка. {123} — 0 неупорядоченностей, — четная перестановка. {312} — 2 неупорядоченности, — четная перестановка. {231} — 2 неупорядоченности, — обмен, нечетная перестановка. {213} — 1 неупорядоченность, {132} — 1 неупорядоченность,  — обмен, нечетная перестановка. {321} — 3 неупорядоченности, — обмен, нечетная перестановка. Оба определения четности эквивалентны, так как обмен всегда изменяет число неупорядоченностей на нечетное число, то есть меняет четность. Ответ: Группа перестановок 3 элементов некоммутативна. Четные перестановки образуют подгруппу с таблицей умножения: 2 х Û 1 Û Û Û Û

45

’’’ Задача 8.4. Ловушка Ллойда () Ответ: Из данного положения пятнашки собрать невозможно. Указание. Правильное положение следует считать начальной четной упорядоченной перестановкой (см. предыдущую задачу «Группа наперсточника») шестнадцати элементов, учитывая пустое место как 16-ый элемент. Каждый ход — обмен: меняет пустое место с соседним квадратом. Количество ходов до собранного состояния четное: сколько раз пустое место сместится вверх, столько же вниз, сколько влево, столько же вправо. Покажите, что приведенное в задаче начальное положение соответствует нечетной перестановке.

’’’’ Задача 8.5. Кубик Рубика () Ответ: Кубик Рубика состоит из 27 подкубов. Один не раскрашен, 6 раскрашено в 1 цвет, 12 раскрашено в 2 цвета и 8 подкубов раскрашено в 3 цвета. Кубик Рубика имеет 43252003274489856000 ≈ 43 квинтилиона состояний. Количество состояний определяется тем, что для трехцветного кубика можно получить любое из восьми положений и любое из трех направлений, а для двухцветного кубика — любое из 12 положений и из 2 направлений. Одноцветные кубики неподвижны. Оценим полное число состояний по правилу прямого произведения множеств: 8!⋅ 38 ⋅ 12!⋅ 212 = 519024039293878272000 .

На самом деле возможно лишь каждое 12-ое из пересчитанных состояний23. Всего состояний 8!⋅ 38 ⋅ 12!⋅ 212 = 43252003274489856000 . 2⋅2⋅3

23

Несложно доказать, что пересчитанные состояния имеют различные четности (подобно состояниям "пятнашек" из предыдущей задачи). Так, поворот стороны сохраняет четность по направлениям двухцветных подкубиков. Это значит, что если руками вынуть двуцветный подкубик и, развернув, вставить на место, кубик Рубика по-честному не соберется. Выходит, что пересчитанные состояния разбиваются на два непереходящих друг в друга равномощных подмножества состояний различной четности. Каждое из подмножеств разбивается на 3 равномощные части по направлениям трехцветных подкубиков. Затем 6-ая часть делится еще на 2 части по положениям. Поворот стороны является нечетной перестановкой как для двуцветных, так и для трехцветных подкубиков, и четность меняется совместно. Другими словами,невозможно получить состояние с нечетной перестановкой двухцветных и четной перестановкой трехцветных. Например, нельзя поменять местами два двухцветных подкубика, не поменяв трехцветных.

46

Отсюда следует оценка, что любой честно разобранный кубик Рубика можно собрать за два десятка ходов. Действительно, из собранного состояния, делая поворот одной из 6 сторон на 900 по или против часовой стрелки, мы попадаем в одно из 12 состояний. Каждое из этих состояний ведет еще к 11-ти новым, исключая исходное. Если число достигаемых состояний увеличивается за каждый ход в 11 раз, то в любое состояние можно попасть за log11 43252003274489856000 = 18.85552540 ≈ 19 ходов!

Кубику Рубика три десятилетия, однако, несмотря на огромную популярность головоломки, его группа изучена не до конца. От первых 50ходовых алгоритмов сборки люди шагнули к 20-ходовым компьютерным стратегиям, но доказать, что алгоритмы оптимальны, пока не получилось.

47

ПРИЛОЖЕНИЕ 1. СЛОЖЕНИЕ МНОЖЕСТВ (ОЛИМПИЙСКИЕ КОЛЬЦА) Правило включений-исключений определяет мощность объединения как N

N

U M i = ∑ ( −1) i =1

i =1

( i +1)

∑ Iσ M

σ ∈C Ni

ki ,σ ∈

ki ,σ

,

где M 1..N — объединяемые множества, CNi — множество сочетаний индексов. Убедимся в справедливости утверждения на простом примере. Четыре одинаковых круга, центры которых расположены в вершинах квадрата, попарно пересекаются. Точки, принадлежащие всем четырем кругам, Диаграмма Эйлера-Венна сложения множеств закрашены в алый цвет, трем кругам соответствует белый цвет, двум − вишневый, одному − голубой. Остальные точки не окрашены. Сколько раз мы включаем и вычитаем площади каждого цвета, когда ищем раскрашенную площадь по правилу сумм? Пересечения По одному По два По три По четыре Итого кругов Голубой +1 +1 Вишневый +2 -1 +1 Белый +3 -3 +1 +1 Алый +4 -6 +4 -1 +1 Количества включений-исключений располагаются в треугольник Паскаля. И правило сводится к утверждению, что знакопеременная сумма строки в треугольнике Паскаля равна нулю. Например, + 1 – 4 + 6 – 4 + 1 = (1 – 1)4 = 0. Дополнительно. Попробуйте вычислить, какую площадь покрывают четыре круга радиусом 2 с центрами в точках (1,1); (1,-1); (-1,1); (-1,-1). Очевидно, что в этой задаче площади Б, В, Г рассчитать сложно, а площади пересечения кругов по два: А + Б1 + Б2 + В1, А + Б1 + Б3 и по три: А + Б1 рассчитать легче.

48

ПРИЛОЖЕНИЕ 2. СИСТЕМЫ ИСЧИСЛЕНИЯ

49

ПРИЛОЖЕНИЕ 3. ПЕРЕЧИСЛЕНИЕ ВЫБОРОК Ниже приведены примеры перечисления выборок из 3 по 2 и по 3 с повтором и без него, с порядком и без него. Таблица для выборок из 4 по 3 оставлена пустой, ее предлагается заполнить самостоятельно.

50

ПРИЛОЖЕНИЕ 4. ВЫБОРКИ (МНОГОВЕРТ И ЕГО ДЕТИ) В Дисмагороде правящий род Комбинаториев по вечерам закатывает пышные пиры. По обычаю в знак внимания к гостям повелевают, чтобы каждому вельможе был особый выбор напитков. Царь Многоверт допускает подносить одному гостю одно вино много раз. А также снисходит к тому, что различным гостям подносятся одни зелья, лишь бы в разном порядке. Старший царевич, Одноверт Многовертович, на своем пиру не терпит повторений, справедливо полагая, что каждый званый должен вкусить побольше разнообразного зелья. Средний сын, Многоряд Многовертович, увещевает слуг следить за порядком подношений. И если одному вельможе подали квас, а затем медовуху, то другому воспрещается потреблять квас за медовухой, как тот же выбор во вредной очередности. Младший наследник, Одноряд Многовертович, в гуляниях держится прихотей обоих братьев. Число бочек различного вина означает месяц в году. Число подношений определяется днем недели. При таких порядках спрашивается, по каким дням недели и месяцам, сколько разных пиров допускается и сколько гостей на них зазывается? Решение

Количество гостей на пире определяется одной из четырех выборок (размещения и сочетания с повторением и без). Ответ выражается таблицей. Порядок +

−

m! ( m − k )! Размещения без повторения

Повтор

+

Amk = m k Размещения с повторением Amk =

− ( m + k − 1)! Cmk = ( m − 1)! k ! Сочетания с повторением m! Cmk = ( m − k )! k ! Сочетания без повторения

51

52

12

11

10

9

8

7

6

5

4

3

2

1

m\w

1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8

9

9

10

10

11

11

12

12

1

1

2

2

3

3

4

4

5

5

6

6

7

7

8

8

9

9

10

10

11

11

12

12

1

132

144

110

121

90

100

72

81

56

64

42

49

30

36

20

25

12

16

6

9

2

4

-

1

2

66

78

55

66

45

55

36

45

28

36

21

28

15

21

10

15

6

10

3

6

1

3

-

1

1320

1728

990

1331

720

1000

504

729

336

512

210

343

120

216

60

125

24

64

6

27

-

8

-

1

3

220

364

165

286

120

220

84

165

56

120

35

84

20

56

10

35

4

20

1

10

-

4

-

1

11880

20736

7920

14641

5040

10000

3024

6561

1680

4096

840

2401

360

1296

120

625

24

256

-

81

-

16

-

1

4

495

1365

330

1001

210

715

126

495

70

330

35

210

15

126

5

70

1

35

-

15

-

5

-

1 -

1

95040

248832

55440

161051

30240

100000

15120

59049

6720

32768

2520

16807

720

7776

120

3125

-

1024

-

243

-

32

Выборки Комбинаториев 5

792

4368

462

3003

252

2002

126

1287

56

792

21

462

6

252

1

126

-

56

-

21

-

6

-

1

665280

2985984

332640

1771561

151200

1000000

60480

531441

20160

262144

5040

117649

720

46656

-

15625

-

4096

-

729

-

64

-

1

6

924

12376

462

8008

210

5005

84

3003

28

1716

7

924

1

462

-

210

-

84

-

28

-

7

-

1

3991680

35831808

1663200

19487171

604800

10000000

181440

4782969

40320

2097152

5040

823543

-

279936

-

78125

-

16384

-

2187

-

128

-

1

7

792

31824

330

19448

120

11440

36

6435

8

3432

1

1716

-

792

-

330

-

120

-

36

-

8

-

1

ПРИЛОЖЕНИЕ 5. ТРЕУГОЛЬНИК ПАСКАЛЯ Простое и наглядное представление треугольника Паскаля — это «многослойное сито». Если в каждый узел этого сита поместить число невосходящих путей, ведущих в данный узел, то числа образуют треугольник, который носит имя Паскаля24. Если через такое сито просеивать крупицы, то число частиц в узлах одного горизонтального ряда будет приблизительно соответствовать числам треугольника Паскаля.

(а) Многослойное сито

(б) Треугольник Паскаля

Свойство 1. Число путей с n правыми и m левыми ребрами равно числу сочетаний n из n+m ребер: Cnn+ m = Cnm+ m .

Свойство 2. В каждый узел ведут два ребра. Пути, ведущие через эти ребра, складываются: Cnn+ m = Cnn−−11+ m + Cnm+−m1−1 .

Свойство 3. В ряд с номером N ведет 2N путей, так как число путей на каждом ряду удваивается. Поэтому

∑

N n =0

C Nn = 2 N

Свойство 4. Знакопеременная сумма ряда равна нулю:

∑ ( −1) N

n =0

n

C Nn = 0 .

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

24

Паскаль (Pascal) Блез [19.6.1623, Клермон-Ферран, - 19.8.1662, Париж], французский религиозный философ, писатель, математик и физик.

53

(а)

(б)

(в) Биномиальное и нормальное распределения. (а) Число сочетаний из n+m по m. Число путей из n правых и m левых ребер. (б) Вероятности для крупицы попасть в узел. В физике это простейшая решеточная модель для описания процессов протекания, диффузии, теплопроводности. (в) Логарифмы сочетаний. В каждом ряду логарифмы образуют параболу рогами вниз. Свойство 5. Числа одного ряда дают плотность биномиального распределения, которая с ростом ряда стремится к нормальному виду: n N N

C 1 ⎯⎯⎯ → e N →∞ 2 2π

⎛ n−N 2 ⎞ −⎜ ⎜ N 2 ⎟⎟ ⎝ ⎠

2

.

Это утверждение хорошо иллюстрируется графиками.

54

ПРИЛОЖЕНИЕ 6. ГЕКСАФЛЕКСАГОНЫ [12]

Тригексафлексагон

Гексагексафлексагон

Тригексафлексагон складывают из полоски бумаги, предварительно размеченной на 10 равносторонних треугольников (а). Полоску перегибают по линии ab и переворачивают (б). Перегнув полоску еще раз по линии cd, расположим ее концы так, чтобы предпоследний треугольник оказался наложенным на первый (в). Последний треугольник нужно подогнуть вниз и прикрепить к оборотной стороне первого треугольника (г). Чтобы "открыть" тригексафлексагон, его нужно одной рукой взять за два соседних треугольника, примыкающих к какой-нибудь вершине шестиугольника, а другой рукой потянуть за свободный край двух противоположных треугольников. Если флексагон не открывается, нужно попробовать ухватить его за два других треугольника. При открывании шестиугольник выворачивается наизнанку, и наружу выходит поверхность, которая ранее скрывалась внутри. Гексагексафлексагоны складывают из полоски бумаги, разделенной на 19 равносторонних треугольников (а). Треугольники на одной стороне полоски обозначены цифрами 1,2,3; треугольники на другой стороне цифрами 4,5,6. Вместо цифр треугольники можно раскрасить в различные цвета (каждой цифре должен соответствовать только один цвет) или нарисовать на них какую-нибудь геометрическую фигуру. Как складывать полоску, ясно из рисунка. Перегибая гексагексафлексагон, можно увидеть все шесть его разворотов.

55

ПРИЛОЖЕНИЕ 7. ЧАСТОТА ЗНАКОВ В ТЕКСТЕ И ДЛИТЕЛЬНОСТЬ В АЗБУКЕ МОРЗЕ Русская азбука ЧастоДлина26 25 та пробел 0,151 2 о 0,094 7 е 0,074 2 а 0,064 4 и 0,060 3 т 0,055 3 н 0,055 4 с 0,046 4 в 0,040 6 р 0,038 5 л 0,037 6 Знак

Знак к м д у п я ы ь б ч з

Частота Длина 0,029 0,028 0,026 0,025 0,022 0,018 0,017 0,016 0,015 0,015 0,014

6 5 5 5 7 7 8 7 6 8 7

Знак г й ж х ш ю щ ц э ф ъ

Частота Длина 0,014 0,009 0,008 0,008 0,008 0,005 0,003 0,003 0,002 0,001 0,000

6 8 6 5 9 7 8 7 7 6 нет

Латинский алфавит в английском языке Знак Частота27 Длина пробел 0,190 2 e 0,097 2 t 0,079 3 a 0,064 4 o 0,064 7 n 0,055 4 h 0,054 5 i 0,052 3 s 0,048 4

25

Знак Частота Длина r 0,042 5 d 0,041 5 l 0,033 6 u 0,025 5 w 0,022 6 m 0,020 5 y 0,018 8 g 0,018 6 c 0,018 7

Знак Частота Длина f 0,016 6 b 0,014 6 p 0,013 5 k 0,008 6 v 0,006 5 j 0,002 6 x 0,001 5 28 q 0,000 8 z 0,000 6

За основу взят текст книги Щетинина М.П. «Объять необъятное: записки педагога» 26 За единицу длительности букв взято две точки, так как длительности всех букв соответствуют четному числу точек. Например, буква «ж»: «Я бук-ва Жее» включает три точки (3), одно тире (3), три промежутка между знаками (3) и один промежуток между буквами (3). Итого 12 точке, или 6 пар точек. 27 За основу взят текст книги Твена М. «Приключения Тома Сойера» 28 На 368203 знаков текста пришлось 178 букв «q». Меньше 1 на две тысячи.

56

ПРИЛОЖЕНИЕ 8. ТЕЛЕГРАФНАЯ АЗБУКА МОРЗЕ Букве соответствует комбинация из длинных посылок (тире) и коротких посылок (точек). За единицу длительности принимается длительность точки. Длительность тире равняется длительности трех точек. Пауза между знаками в букве —точка, между буквами в слове — 3 точки, между словами — 7 точек. A

А

N

Н

1

6

B

Б

O

О

2

7

C

Ц

P

П

3

8

D

Д

Q

Щ

4

9

E

Е

R

Р

5

0

F

Ф

S

С

G

Г

T

Т

H

Х

U

У

I

И

V

Ж

J

Й

W

В

K

К

X

Ь

L

Л

Y

Ы

M

М

Z

З

?

Ч

/

Ш

||

Э

!

Ю

,

Я

знак раздела Перебой (исправление)

Начало передачи Готовность к приему Начало действия Окончание передачи

57

ИЗУЧЕНИЕ АЗБУКИ МОРЗЕ Вся сложность изучения азбуки Морзе заключается в том, что недостаточно просто запомнить комбинацию точек и тире для каждой буквы. Даже наоборот, это очень вредно для последующего серьезного изучения CW. Поначалу, на малых скоростях, вам, возможно, удастся просчитать количество точек и тире, но при увеличении скорости вы наверняка собьетесь! В приведенной ниже таблице указаны напевы для букв телеграфной азбуки, которые и стоит запоминать. Каждый напев начинается на соответствующую букву, слоги с гласными буквами "О" и "А" пропеваются протяжно, обозначая длинную посылку (тире), а все остальные коротко (точки):

58

1

И-тооль-коо оод-наа

6

Поо шес-ти-бе-ри

2

Две не хоо-роо-шоо

7

Даа-Даа- се-ме-ри

3

Три те-бе маа-лоо

8

Воось-моо-гоо и-ди

4

Чет-ве-ри-те-каа

9

Наа-ноо-наа-ноо-ми

5

Пя-ти-ле-ти-е

0

Нооль-тоо оо-коо-лоо

A

А

Ай-даа!

N

Н

Ноо-мер

B

Б

Баа-ки те-кут

O

О

Оо-коо-лоо

C

Ц

Цаа-пли наа-ши

P

П

Пи-лаа поо-ёт

D

Д

Даа и-ди

Q

Щ

Щаа ваам не Шаа

E

Е

Есть

R

Р

Ре-шаа-ет

F

Ф

Фи-ли-моон-чик

S

С

Си-не-е

G

Г

Гаа-раа-жик

T

Т

Таак

H

Х

Хи-ми-чи-те

U

У

У-нес-лоо

I

И

И-ди

V

Ж

Я бук-ва Жее

J

Й

Йош-каа-роо-лаа

W

В

Ви-даа-лаа

K

К

Каак де-лаа?

X

Ь

Тоо мяг-кий знаак

L

Л

Ли-шаай-ни-ки

Y

Ы

ЫЫ не наа-доо

M

М

Маа-маа

Z

З

Заа-каа-ти-ки

Содержание ПЛАН КУРСА «ДИСКРЕТНАЯ МАТЕМАТИКА. ............................................................................................................. 3 Краткая характеристика курса ................................................................................................................................... 3 Темы лекций..................................................................................................................................................................... 3 Основная литература .................................................................................................................................................... 4 Дополнительная литература ........................................................................................................................................ 4 Тяжелая литература ..................................................................................................................................................... 5 ЗАНЯТИЕ 1.

ОСНОВЫ..................................................................................................................................................... 6

МНОЖЕСТВА, ОТОБРАЖЕНИЯ И ОТНОШЕНИЯ ......................................................................................................................... 6 ’ Задача 1.1. Булеан ("š)............................................................................................................................................ 6 ’’ Задача 1.2. Доказательство на кружках ............................................................................................................. 6 ’’ Задача 1.3. Принцип Дирихле в арбузных корках ("š) ...................................................................................... 6 ’’ Задача 1.4. Отношение упорядочения .................................................................................................................. 7 ВЕРОЯТНОСТИ ......................................................................................................................................................................... 7 ’’ Задача 1.5. Азартная игра и справедливость (š) ............................................................................................... 7 ’’ Задача 1.6. Очень широкий танк (š).................................................................................................................... 7 ’’’ Задача 1.7. В квадратном часе (š) ................................................................................................................... 7 ЗАНЯТИЕ 2.

КОЛИЧЕСТВО И ПОРЯДОК ................................................................................................................. 7

’’ Задача 2.1. Числа количественные и порядковые (") ................................................................................... 7 ПРАВИЛО СЛОЖЕНИЯ (ВКЛЮЧЕНИЯ-ИСКЛЮЧЕНИЯ) МНОЖЕСТВ ........................................................................................... 8 ’’ Задача 2.2. Правило гусениц .................................................................................................................................. 8 ’’ Задача 2.3. Правило красок ()........................................................................................................................... 8 ’’ Задача 2.4. Инспектор запутался (š).................................................................................................................. 8 ’’ Задача 2.5. Куратор недосчитался (š)................................................................................................................ 8 ПРАВИЛО УМНОЖЕНИЯ ........................................................................................................................................................... 8 ’ Задача 2.6. Считалочка ............................................................................................................................................. 8 ’’ Задача 2.7. Не роскошь, а средство передвижения () ................................................................................... 9 ’ Задача 2.8. Ладейное перенаселение (").................................................................................................................. 9 ЗАНЯТИЕ 3.

ПРЕДСТАВЛЕНИЯ СТРОКИ................................................................................................................. 9

’’’ Задача 3.1. Электронная логика (")............................................................................................................ 9 ’ Задача 3.2. Скрытая цифра (š)........................................................................................................................ 10 ’’ Задача 3.3. Избыточность штрих-кода ().................................................................................................... 10 СИСТЕМЫ ИСЧИСЛЕНИЯ ........................................................................................................................................................ 10 ’’ Задача 3.4. Считаем на пальцах (š) .................................................................................................................. 10 ’’ Задача 3.5. Автобиография математика (š)................................................................................................... 11 РАСТРОВЫЕ ИЗОБРАЖЕНИЯ ................................................................................................................................................... 11 ’’ Задача 3.6. Оцифруй рисунок (š) .................................................................................................................. 11 ’’ Задача 3.7. Нарисуй числа (š)............................................................................................................................. 11 ’’’ Задача 3.8. Что показывают числа? (š) ....................................................................................................... 11 ЗАНЯТИЕ 4.

ВЫБОРКИ................................................................................................................................................. 12

’’ Задача 4.1. Доживем до воскресенья ("š) ....................................................................................................... 12 СОЧЕТАНИЯ ........................................................................................................................................................................... 12 ’ Задача 4.2. Звон бокалов ("š) ............................................................................................................................... 12 ’ Задача 4.3. Напиши родителям (š) ....................................................................................................................... 12 ’ Задача 4.4. Треугольник — клетка геометрии! (š) .............................................................................................. 12 СОЧЕТАНИЯ С ПОВТОРЕНИЕМ ............................................................................................................................................... 12 ’ Задача 4.5. Напиши друзьям (š)............................................................................................................................. 12 ’ Задача 4.6. Коробки (š) .......................................................................................................................................... 12 ’’ Задача 4.7. Возможные треугольники (š)......................................................................................................... 12 ’’’’ Задача Муавра 4.8. (š).................................................................................................................................. 13 ’’’’ Задача 4.9. Счастливый билетик () ........................................................................................................ 13 ЗАНЯТИЕ 5.

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

’’ Задача 5.1. Перестановки с ограниченным запасом (") .................................................................................. 13 ’’ Задача 5.2. Комбинаторика сада (")................................................................................................................. 13 ’’’’ Задача 5.3. Пространства (") .................................................................................................................... 13 ’’ Задача 5.4. Не перегружайте математикой! (š) ............................................................................................ 14 ’’’’ Задача 5.5. Джентельменское правило (š) ................................................................................................ 14 ЧЕТНОСТЬ, ПЕРЕСТАНОВКИ................................................................................................................................................... 14 ’’ Задача 5.6. Локальная сеть общежития ........................................................................................................... 14

59

’’ Задача 5.7. Тараканьи бега................................................................................................................................... 14 ’’ Задача 5.8. Наведи порядок.................................................................................................................................. 15 ЗАНЯТИЕ 6.

ГРАФЫ ...................................................................................................................................................... 15

’’ Задача 6.1. Эйлерова характеристика (")................................................................................................... 15 ’’ Задача Эйлера 6.2. (") .................................................................................................................................... 15 ’’ Задача 6.3. Волк, коза и капуста. Теория перевозки (")................................................................................... 16 ’’ Задача 6.4. Ханойская башня () ...................................................................................................................... 16 ’’’’ Задача 6.5. Гексафлексагон........................................................................................................................... 16 ’’’’ Задача 6.6. Дележ без ковша (š) ................................................................................................................. 17 ’’’ Задача 6.7. Симметричный конденсатор ....................................................................................................... 17 ЗАНЯТИЕ 7.

ИНФОРМАЦИЯ....................................................................................................................................... 17

ПОИСК ................................................................................................................................................................................... 17 ’’ Задача 7.1. Гроза фальшивомонетчиков (") ..................................................................................................... 17 ’’’ Задача 7.2. Информативность взвешивания (š)........................................................................................... 17 ’’’’ Задача 7.3. Придворный заговор (š)............................................................................................................ 17 ЗАЩИТА ................................................................................................................................................................................. 17 ’ Задача 7.4. Маскарад тайнописи ("š)............................................................................................................ 17 ’’ Задача 7.5. Военный приказ (š) ..................................................................................................................... 18 ’ Задача 7.6. Тарабарщина (š)............................................................................................................................. 18 ПЕРЕДАЧА И СЖАТИЕ ............................................................................................................................................................ 18 ’’’ Задача 7.7. Русскоязычная раскладка ()..................................................................................................... 18 ’’’ Задача 7.8. Латинская раскладка () .......................................................................................................... 18 ’’’ Задача 7.9. Телеграфная азбука Морзе............................................................................................................ 19 ’’’ Задача 7.10. Азбука Морзе на русский лад ...................................................................................................... 19 ’’ Задача 7.11. Код личный — двоичный!................................................................................................................ 19 ’’’’’ Задача 7.12. Сжатый код (") .................................................................................................................. 19 ЗАНЯТИЕ 8.

ЛАБИРИНТЫ, КОМБИНАТОРНЫЕ ГОЛОВОЛОМКИ............................................................... 19

’’ Задача 8.1. Пути и ветвления () ..................................................................................................................... 19 ’ Задача 8.2. Объемный лабиринт () .................................................................................................................... 20 ’’’’ Задача 8.3. Группа наперсточника............................................................................................................... 20 ’’’ Задача 8.4. Ловушка Ллойда ().................................................................................................................... 20 ’’’’ Задача 8.5. Кубик Рубика () ..................................................................................................................... 20 ОТВЕТЫ.................................................................................................................................................................................... 21 ПРИЛОЖЕНИЕ 1. СЛОЖЕНИЕ МНОЖЕСТВ (ОЛИМПИЙСКИЕ КОЛЬЦА)......................................................... 48 ПРИЛОЖЕНИЕ 2. СИСТЕМЫ ИСЧИСЛЕНИЯ .............................................................................................................. 49 ПРИЛОЖЕНИЕ 3. ПЕРЕЧИСЛЕНИЕ ВЫБОРОК........................................................................................................... 50 ПРИЛОЖЕНИЕ 4. ВЫБОРКИ (МНОГОВЕРТ И ЕГО ДЕТИ)....................................................................................... 51 Решение.......................................................................................................................................................................... 51 ПРИЛОЖЕНИЕ 5. ТРЕУГОЛЬНИК ПАСКАЛЯ .............................................................................................................. 53 ПРИЛОЖЕНИЕ 6. ГЕКСАФЛЕКСАГОНЫ [12]............................................................................................................... 55 ПРИЛОЖЕНИЕ 7. ЧАСТОТА ЗНАКОВ В ТЕКСТЕ И ДЛИТЕЛЬНОСТЬ В АЗБУКЕ МОРЗЕ ............................. 56 РУССКАЯ АЗБУКА................................................................................................................................................................... 56 ЛАТИНСКИЙ АЛФАВИТ В АНГЛИЙСКОМ ЯЗЫКЕ ..................................................................................................................... 56 ПРИЛОЖЕНИЕ 8. ТЕЛЕГРАФНАЯ АЗБУКА МОРЗЕ ................................................................................................... 57 ИЗУЧЕНИЕ АЗБУКИ МОРЗЕ .............................................................................................................................................. 58

60