Тимофеев И.В. Дискретная математика для инженеров-физиков: сборник задач / Сост. И.В. Тимофеев. Красноярск, 2003. 35 с.
В сборник вошли 64 задачи, предлагавшиеся автором-составителем студентам Инженерно-физического факультета КрасГТУ в третьем семестре в рамках 34-часового курса «Дискретная математика». Все задачи снабжены ответами и указаниями к решению.
Содержание
ПЛАН КУРСА «ДИСКРЕТНАЯ МАТЕМАТИКА...................................................3
Краткая характеристика курса......................................................3
Темы лекций...........................................................................3
Основная литература..........................................................4
Дополнительная литература.....................................................4
Тяжелая литература...............................................................5
ЗАНЯТИЕ 1. ОСНОВЫ................................................................6
Множества, отображения и отношения.................................................6
0 Задача 1.1. Булеан (^Ф)..........................................................6
00 Задача 1.2. Доказательство на кружках...........................................6
00 Задача 1.3. Принцип Дирихле в арбузных корках (^Ф)..............................6
00 Задача 1.4. Отношение упорядочения..............................................7
Вероятности........................................................................7
** Задача 1.5. Азартная игра и справедливость (Ф)...................................7
00 Задача 1.6. Очень широкий танк (Ф)..............................................7
000 Задача 1.7. В квадратном часе (Ф)..............................................7
ЗАНЯТИЕ 2. КОЛИЧЕСТВО И ПОРЯДОК.................................................7
00 Задача 2.1. Числа количественные и порядковые ................................7
Правило сложения (включения-исключения) множеств..................................8
00 Задача 2.2. Правило гусениц.......................................................8
00 Задача 2.3. Правило красок (..............................................8
00 Задача 2.4. Инспектор запутался (Ф).........................................8
00 Задача 2.5. Куратор недосчитался (Ф)...............................................8
Правило умножения...................................................................8
0 Задача 2.6. Считалочка...............................................................8
00 Задача 2.7. Не роскошь, а средство передвижения (................................9
0 Задача 2.8. Ладейное перенаселение .............................................9
ЗАНЯТИЕ 3. ПРЕДСТАВЛЕНИЯ СТРОКИ....................................................9
000 Задача 3.1. Электронная логика .....................................................9
0 Задача 3.2. Скрытая цифра (Ф).........................................................10
00 Задача 3.3. Избыточность штрих-кода ............................................10
Системы исчисления.........................................................................10
** Задача 3.4. Считаем на пальцах (Ф)........................................................10
00 Задача 3.5. Автобиография математика (Ф)...............................................11
Растровые изображения..................................................................11
00 Задача 3.6. Оцифруй рисунок (Ф)............................................11
00 Задача 3.7. Нарисуй числа (Ф)................................................................11
000 Задача 3.8. Что показывают числа? (Ф)..................................................11
ЗАНЯТИЕ 4. ВЫБОРКИ...........................................................................12
00 Задача 4.1. Доживем до воскресенья (^Ф)...........................................12
Сочетания.................................................................................. 12
0 Задача 4.2. Звон бокалов (^Ф)...............................................12
0 Задача 4.3. Напиши родителям (Ф)................................................................12
0 Задача 4.4. Треугольник — клетка геометрии! (Ф)..........................................12
Сочетания с повторением..........................................................................12
0 Задача 4.5. Напиши друзьям (Ф)........................................................12
0 Задача 4.6. Коробки (Ф)......................................................................12
00 Задача 4.7. Возможные треугольники (Ф).......................................12
0000 Задача Муавра 4.8. (Ф)...............................................................13
0000 Задача 4.9. Счастливый билетик (...........................................13
ЗАНЯТИЕ 5. КОМБИНАТОРИКА........................................................................13
00 Задача 5.1. Перестановки с ограниченным запасом ........................................13
00 Задача 5.2. Комбинаторика сада ......................................................13
0000 Задача 5.3. Пространства .....................................................13
00 Задача 5.4. Не перегружайте математикой! (Ф)...................................14
0000 Задача 5.5. Джентельменское правило (Ф)...........................14
Четность, перестановки.......................................................14
00 Задача 5.6. Локальная сеть общежития..........................................14
** Задача 5.7. Тараканьи бега........................................................14
00 Задача 5.8. Наведи порядок.......................................................15
ЗАНЯТИЕ 6. ГРАФЫ....................................................................15
00 Задача 6.1. Эйлерова характеристика ...........................................15
00 Задача Эйлера 6.2. ...........................................................15
00 Задача 6.3. Волк, коза и капуста. Теория перевозки ................................16
00 Задача 6.4. Ханойская башня ........................................................16
0000 Задача 6.5. Гексафлексагон.....................................................16
0000 Задача 6.6. Дележ без ковша (Ф)....................................................17
000 Задача 6.7. Симметричный конденсатор.................................................17
ЗАНЯТИЕ 7. ИНФОРМАЦИЯ...................................................................17
Поиск...................................................................................17
00 Задача 7.1. Гроза фальшивомонетчиков ......................................17
000 Задача 7.2. Информативность взвешивания (Ф).........................................17
0000 Задача 7.3. Придворный заговор (Ф)...........................................17
Защита..................................................................................17
0 Задача 7.4. Маскарад тайнописи (^Ф^).................................................17
00 Задача 7.5. Военный приказ (Ф^)......................................................18
0 Задача 7.6. Тарабарщина (Ф^)......................................................18
Передача и сжатие......................................................................18
000 Задача 7.7. Русскоязычная раскладка .............................................18
000 Задача 7.8. Латинская раскладка ...................................................18
000 Задача 7.9. Телеграфная азбука Морзе..................................................19
000 Задача 7.10. Азбука Морзе на русский лад..............................................19
00 Задача 7.11. Код личный — двоичный!............................................19
00000 Задача 7.12. Сжатый код ........................................................19
ЗАНЯТИЕ 8. ЛАБИРИНТЫ, КОМБИНАТОРНЫЕ ГОЛОВОЛОМКИ..........................................19
00 Задача 8.1. Пути и ветвления ............................................................19
0 Задача 8.2. Объемный лабиринт .........................................................20
0000 Задача 8.3. Группа наперсточника.....................................................20
000 Задача 8.4. Ловушка Ллойда .............................................20
0000 Задача 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
