Комбинаторика

Курс по выбору «Комбинаторика» Урок № 2. Тема   урока:        Магический   и   латинский   квадрат.   Правило произведения Цель урока: Познакомить учащихся с магическими и латинскими квадратами. Научить   решать   комбинаторные   задачи   с   помощью   правила произведения Наглядность   и   раздаточный   материал:   Презентация   №1,   слайды   с магическими и латинскими квадратами, карточки с задачами 1. Повторение 1) Что изучает Комбинаторика? 2) Методы решения комбинаторных задач 3) Решите   задачу:   Имеются   ткани   3   цветов.   Сколько   можно   сшить флажков с тремя различными горизонтальными полосами? Иванов Петров Решите задачу: Фамилии четырёх друзей: Иванов, Петров, Семёнов, Николаев, а их имена: Иван, Пётр, Семён, Николай. Известно, что только у Николаева имя совпадает с фамилией; Семёнова зовут не Петром. Определите имена и фамилии друзей.  Иван ­ ­ + ­ Петр + ­ ­ ­ 2. Правило произведения Теорема: Если множество А состоит из m элементов, а множество В – из n элементов, то число различных пар равно m ∙ n Семён ­ + ­ ­ Семёнов Николаев Николай ­ ­ ­ + Задача   1.  Имеются   4   вида   конвертов   без   марок   и   5   видов   марок. Сколькими способами можно выбрать конверт и марку?  Решение: 4 ∙ 5 = 20 Задача 2. В магазине имеются 7 видов пиджаков, 5 видов брюк и 4 вида галстуков. Сколькими способами можно купить пиджак, брюки и галстук? Решение: 7∙ 5 ∙ 4 = 140 3. Игра «Черный ящик» (по карточкам) 4. Магические квадраты ии Маг ческий, или волшебный квадрат , заполненная   числами   таким   образом,   что   сумма   чисел   в   каждой   строке, каждом   столбце   и   на   обеих   диагоналях   оказывается   одинаковой. Нормальным называется магический квадрат, заполненный целыми числами от  1  до  n2. Магические квадраты существуют для всех порядков   , за исключением n = 2.    — это квадратная таблица   Сумма чисел в каждой строке, столбце и на диагоналях, называется  магической константой, M. Магическая константа нормального волшебного  квадрата зависит только от n и определяется формулой Первые значения магических констант приведены в следующей таблице: Порядок n 3 4 5 6 13 15 34 65 111 175 260 369 505 671 870 1105 10 11 12 M (n) 7 8 9 Единственный   нормальный   магический   квадрат   3×3   был   известен   ещё   в Древнем Китае, первое изображение на черепаховом панцире датируется 2200 до н.э.. Магический   квадрат   третьего   порядка   существует всего один, все остальные магические квадраты 3­го порядка получаются из него же поворотом.   4 3 8 9 5 1 2 7 6       4 9 2 3 5 7 8 1 6 2 7 6 9 5 1 4 3 8 Самый ранний уникальный магический квадрат 4 × 4 обнаружен в надписи XI  века в индийском городе Кхаджурахо. Всего их существует 880.   7 2 16 9 12 13 3 6 1 8 10 15 14 11 5 4 Если в квадратную матрицу n × n заносится не строго натуральный ряд чисел, то данный магический квадрат ­  нетрадиционный. Ниже представлены два таких   магических   квадрата,   заполненные   в   основном  простыми   числами. Первый   имеет   порядок  n=3  (квадрат   Дьюдени);   второй   (размером  4x4)   ­ квадрат Джонсона. Оба они были разработаны в начале двадцатого столетия : 67 13 31 1 37 73 43 61 7 3 43 7 67 61 31 11 17 19 5 73 23 37 41 29 13 Построение магических квадратов Математики изобрели несколько методов построения магических квадратов. Рассмотрим  метод   террас,   который   применяется   для   построения магических   квадратов   нечётного   порядка:   пятого,   седьмого   и   т.   д. Рассмотрим его на примере магического квадрата пятого порядка. С четырёх сторон к исходному квадрату 5х5 добавляются террасы так, чтобы получился  зубчатый квадрат того же порядка, что и исходный (рис. 1). В полученной фигуре располагают числа от 1 до 25 в естественном порядке косыми   рядами   снизу   вверх   (рис.   1)   или   сверху   вниз   (рис.   2).   Числа   в террасах, не попавшие в квадрат, перемещаются как бы вместе с террасами внутрь   него   так,   чтобы   они   примкнули   к   противоположным   сторонам квадрата.   На   рис.   3   и   4   изображены   готовые   магические   квадраты,   они аналогичны по структуре, только один повёрнут на 90 градусов относительно центра квадрата.        5     10         14   20       4               3   9   15         2   8   1   7   13   19   25   6   12           11   17   23           18   24           16     22       21         21                 16         6 11   1   7 12     2   8 13       3   9 14                 4   5 10         18   17   22         23       19   24     25   15       20                             Рис. 1                                                       Рис. 2   3 16 9 22 15             20 8 21 14 2 7 25 13 1 19 24 12 5 18 6 11 4 17 10 23 11 24 7 20 3 4 12 25 8 16 17 5 13 21 9 10 18 1 14 22 23 6 19 2 15                          Рис. 3                                                        Рис. 4 Заметим,   что   методом   террас   можно   построить   не   только   традиционный магический квадрат нечётного порядка (то есть заполненный числами от 1 до n2), но и квадрат, заполненный любыми другими числами, лишь бы разность   между   каждым   последующим   и предыдущим числом была постоянной. Так, на 6 32 18 44 30 40 16 42 28 4 14 50 26 2 38 48 24 10 36 12 22 34 20 46 8 рис.   5   вы   видите   нетрадиционный   магический   квадрат   пятого   порядка, заполненный чётными числами от 2 до 50, построенный методом террас.                                                                                                                                             Рис. 5 5. Латинские квадраты  Латинским квадратом n × n называется квадрат, в каждой строке и в  каждом столбце которого находятся числа от 1 до n. Задачей отыскания  латинских квадратов занимался Леонард Эйлер .    1  3 2 2 1 3 3 2 1 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 В   качестве   примера,   приводящего   к   латинским   квадратам,   рассмотрим упрощенную задачу о составлении расписания. Пусть пять преподавателей Pi ( i  =   1,   2,   ...,   5)   школы   в   течение   пяти   последовательных   уроков   должны провести занятия в пяти классах  Kj  (  j  = 1, 2, ..., 5). При этом каждый из преподавателей  обязан  дать  один  урок  в каждом  классе.  В  этой  ситуации оказывается,   существует   1344   возможных   различных   расписаний.   Ниже приведено одно из них: К1 К2 К3 К4 К5 Р1 Р2 Р3 Р4 Р5 1 2 3 4 5 2 1 4 5 3 3 4 5 1 2 4 5 2 3 1 5 3 1 2 4 Домашнее задание: 1) составьте магический квадрат 3 × 3 2) составьте латинский квадрат 3 × 3 3) составьте латинский квадрат 4 × 4 4) составьте магический квадрат 7 × 7 5) В   футбольной   команде   11   человек.   Нужно   выбрать   капитана   и   его заместителя. Сколькими способами это можно сделать? 6) Король   решил   выдать   замуж   трёх   дочерей.   На   смотр   явились   100 женихов.   Сколькими   способами   дочери   короля   могут   выбрать   себе жениха?