XVIII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Латинские прямоугольники
Автор работы награжден дипломом победителя I степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
В современном мире очень популярна игру «Судоку», где в свободные клетки заполняются цифрами от 1 до 9 так, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате 3×3 каждая цифра встречалась бы только один раз.
Сложность судоку зависит от количества изначально заполненных клеток и от методов, которые нужно применять для её решения.
Но однажды я подумала, что в судоку заполняются квадраты, а можно ли заполнять числами, таким образом, и прямоугольники?
Мне стало интересно. И в интернете я обнаружила информацию о прямоугольниках, которые тоже заполняются цифрами. Я узнала, что их называют латинскими. Оказывается, в истории латинскими прямоугольниками занимались крупнейшие математики. Современные исследования латинских прямоугольников повышают эффективность информационных технологий. В результате изучения темы латинских прямоугольников я выяснила, что латинские прямоугольники имеют широкое применение во различных областях жизни человека.
Основная часть
Латинские прямоугольники
Если прямоугольник разбить строками и столбцами на m х n квадратов и в каждый квадрат разместить одно из натуральных чисел 1, 2, 3, … n , притом так, чтобы все числа в каждой строке и в каждом столбце были различны, то получается прямоугольник, который называется латинским. В нем каждое из чисел 1, 2, 3, … n повторяется m раз.
Раньше такие прямоугольники заполняли буквами латинского алфавита, поэтому и назвали такой прямоугольник латинским.
Латинским прямоугольником называется прямоугольная таблица элементов, в которой каждый ряд представляет собой перестановку из одних и тех же п элементов, причем в каждом столбце все элементы различны.
Математическая дисциплина КОМБИНАТОРИКА занимается подсчетом числа различных наборов и конфигураций. Задача перечисления латинских прямоугольников также относится к комбинаторике.
Выбором объектов и расположением их в том или оинм порядке приходиться заниматься чуть ли не во всех областях человеческой деятельности, например, конструктору, разрабатывающему новую модель механизма, ученому - агроному, планирующему распределение посевы сельскохозяйственных культур на нескольких полях, химику, изучающему строение органических молекул, имеющих данный атомный состав.
С аналогичными задачами, получившими название комбинаторные, люди столкнулись в глубокой древности. Несколько тысячелетий назад в древнем Китае увлекались составлением магических квадратов, в которых заданные числа располагали так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же. В Древней Греции подсчитывали число различных комбинаций длинных и коротких слогов стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата и т.д.
Задача перечисления латинских прямоугольников тоже относиться к комбинаторике. Этой задачей занимались крупнейшие математики. Прошло более 200 лет между подсчетом числа «двухстрочных» и «трехстрочных» прямоугольников.
«Двухстрочные» латинские прямоугольники впервые перечислил француз Монмор еще в 1713 году. «Трехстрочные» латинские прямоугольники начал исследовать американский математик Риордан в 1953 году.
Кроме красивых явных формул Монмора и Риордана для этих прямоугольников были найдены удобные реккурентные формулы великим Эйлером в 1782 году и индийцем Керавалой.
Существование латинских прямоугольников
Теорема 1.
Для любых чисел m ≤ n существует латинский mхn – прямоугольник.
Доказательство.
Будем расставлять числа в m-этажном прямоугольнике с верхней строчки . На m- строчке расставим числа 1,2, 3, …..n. На (m -1) – й строчке начнем расставлять числа с двойки: 2, 3, …n, 1; на (m -2) – й строчке с тройки: 3, 4, …n,1. 2, и так далее; наконец, на 1-й строчке начнем расставлять с числа m: m, m+1, … n, 1, 2, … m -1. Тогда прямоугольник будет заполнен как в таблице
|
1 |
2 |
3 |
… |
n |
n-1 |
|
2 |
3 |
4 |
… |
n |
1 |
|
… |
… |
… |
… |
… |
… |
|
m |
m+1 |
m +2 |
… |
m-2 |
m-1 |
При такой расстановке нет двух одинаковых чисел на одной строчке и или на одном столбце. Следовательно, это «m- этажный» латинский прямоугольник длиной n. Значит, mхn – прямоугольники существуют.
Латинские прямоугольники в «Две строки»
Теперь подойдем к подсчету числа латинских прямоугольников. Особенно просто решается эта задача для однострочных прямоугольников.
Теорема 2.
Число латинских 1 х n - прямоугольников равно n!=1*2*…* n.
Доказательство.
Латинский 1 хnпрямоугольник – это просто произвольная перестановка из nчисел. Таких перестановок всего n! ( на первое место ставили любое из nчисел, на второе – любое из n-1 оставшихся, на третье – любое изn-2 оставшихся после этого и т.д.
Перейдем к 2 х n - прямоугольникам. Верхняя строка этого прямоугольника – любая перестановка. Нижняя сточка – перестановка, в которой на каждом месте стоит число, не равное числу, стоящему на том же месте в первой перестановке. Если произвольным образом переставим столбцы нашего прямоугольника, он останется латинским, и при этом верхнюю перестановку можно сделать любой.
Получается, что какую бы конкретную перестановку ни взять, число латинских прямоугольников , у которых верхняя сточка совпадает именно с этой перестановкой., будет одним и тем же для всех перестановок. Латинский 2хn- прямоугольник называется нормализованным, если в его верхней строчке числа стоят подряд: 1, 2, 3,…, n-1, n.
Тогда число L(2, n)латинских 2хn- прямоугольников равно числу Dnнормализованных латинских2хn- прямоугольников, умноженному на число перестановок n чисел,
т.е. L(2, n) =n!*Dn.
Для числа Dnнормализованных латинских2хn- прямоугольников имеется изящные формулы.
ФормулаЭйлера
Dn= (n – 1)( Dn-1 + Dn-2)
Реккурентная формула: зная D1= 0 иD2= 1, то можно найти с ее помощью последующие Dn:
D3=2*(1+0) =2,
D4= 3*(2+1) =9,
D5= 4*(9+2) =44,
D6 = 5*(44 +9) =265 и т.д.
Теорема 3. Dn= nDn-1 + (-1)n.
Доказательство.
Пусть Dn - nDn-1= Еn. Из формулы Эйлера
Еn= Dn - nDn-1= (n – 1) Dn-1 + (n – 1) Dn-2 - n Dn-1=
= - Dn-1+ (n – 1) Dn-2 = - Еn-1.
Значит,
En= - En- 1= En- 2= … = (-1)nE 2. НоE 2= 1- 2*0 = 1,
значит,En = (-1)nи Dn = nDn-1+ (-1)n.
Найдем реккурентную и явную формулу дляDn.
Теорема 4. Формула Монмора
Dn = n!(
Доказательство.
Dn = nDn-1+ (-1)n= n! (n-1) Dn-2 + (-1)n-1n +(-1)n=
= n (n-1) (n-2) Dn-1 + (-1)n-2n (n-1) + (-1)n-1n + (-1)n= … =
= n (n-1) (n-2)* …* 3D2 - n (n-1)* … * 4 + n (n-1)*… / 5 -
… (-1)n-1n + (-1)n = n!(
Латинские прямоугольники в «Три строки»
Попытки нахождения числа L(3,n)латинских 3хn - прямоугольников завершилось в 1944 году, тогда американец Риордан, опираясь на результаты длинной цепочки предшественников, выписал окончательную формулу, которая громоздкая и выходит за рамки школьной математики.
Приведем только реккурентную формулу Керавалла – Риордана:
если Кn =L(3,n) , то
Кn = n2Kn-1 + n(n-1) Kn-2+ 2n(n-1)(n-2) Kn-3 + (-1)n(en+ 2nen-1) (n≥4).
Пользуясь этими формулами и тем, что К1=К2= 0, К3= 2, можно найти Кn при всех n.
Например, К5= 552,
К7= 1073760;
Отсюда, числа Кnстремительно растут; числа L(3,n) растут еще быстрее.
Более трех строк
Задача перечисления латинских прямоугольников с числом строк более трех считается, изучается и исследуется современными учеными – математиками.
Применение латинских прямоугольников
Латинские прямоугольники представляют собой весьма распространенный комбинаторный объект, так как обладают очень интересными свойствами. Они широко применяются также при планировании экспериментов.
Планирование эксперимента с помощью латинских прямоугольников дает возможность изучить влияние выбранных факторов как на один, так и на несколько выходных параметров объекта исследований. Важно отметить, что при планировании эксперимента можно использовать как качественные, так и количественные факторы.
В сельском хозяйстве.
Латинские прямоугольники используются в основных методах агрономических исследований, этапах планирования эксперимента, методики закладки и проведения полевого опыта, основных элементах методики полевого опыта.
Рассмотрим размещение делянок в натуре на опытном поле с сельскохозяйственными культурами.
Рендомизированное (случайное) размещение вариантов предусматривает случайное расположение их на делянках каждого повторения. В практике опытного дела наиболее распространенными считают метод латинского квадрата и латинского прямоугольника.
Размещение опытных делянок методом латинского квадрата позволяет в значительной степени сэлиминировать, устранить влияние систематического изменения плодородия почвы опытного участка на результаты опыта по двум взаимно перпендикулярным направлениям.
Для этого земельный участок квадратной или прямоугольной формы разбивают в горизонтальном и вертикальном направлениях на столько рядов и столбцов сколько вариантов в опыте. Любой ряд и любой столбец включают полный набор изучаемых вариантов, которые размещаются на делянках квадратной или прямоугольной формы. При удлиненной форме делянок латинский квадрат не имеет особых преимуществ перед методом рендомизированных повторений.
Расположение опыта латинским квадратом требует, чтобы число повторений обязательно было равно числу вариантов. Поэтому общее количество делянок в опыте всегда будет равно квадрату числа вариантов схемы. При четырех вариантах в опыте будет 4× 4=16 делянок, при пяти – 5× 5=25, при шести – 6× 6=36 делянок и т.д. На площади их размещают рядами и столбцами. В каждом ряду и столбце должен быть полный набор всех вариантов, и, следовательно, ни один из вариантов не повторяется дважды ни в строке, ни в столбце. Кроме этих двух ограничений, варианты размещаются внутри столбцов и рядов случайно, по таблице случайных чисел.
В информационных системах
Современная наука, техника и производство тесно связаны с автоматическим и автоматизированным управлением, широко использующим сложные информационные системы. Рядом существенных требований, предъявляемых к устройствам обработки информации, является высокая надежность работы, экономичность, большая емкость. Наиболее надежны устройства обработки информации матричной структуры (латинские прямоугольники). Реализация процессов отбора внутри матричных информационных устройств дает возможность уменьшить количество логического оборудования, мощность селектирующих сигналов, требования к идентичности характеристик рабочих элементов и т.д.
В теоретическом плане изучение сетей адресных шин позволило исследовать новые виды таких комбинаторных конструкций, как уравновешенные неполные блок-схемы с переменным объемом блока, а также множества ортогональных латинских гиперпрямоугольников.
Широко известно использование матричных структур (латинских прямоугольников) в различных средствах обработки информации, к которым относятся:
- матричные оперативные запоминающие устройства электронных вычислительных и управляющих машин;
- матричные устройства коммутации массовых информационных потоков в системах автоматизации сложных объектов;
- матричные вычислительные системы.
.Заключение.
Латинские прямоугольники сыграли играют важную роль в развитии компьютеров и информационных систем и технологий..
Латинские прямоугольники позволяют проводить сельскохозяйственные опыты и распределять площади под посевы.
Изучение латинских прямоугольников, позволило мне вдуматься в изучаемый материал, углубить знания по математике, расширить кругозор,
Литература
Квант - научно- популярный физико – математический журнал, Москва., Россия, №5, 1990 г.
Математическая энциклопедия. – Москва, Россия, 1982 т.3
Барсуков В.С., Дворянкин С.В., Шеремет И.А. Безопасность связи в каналах телекоммуникаций. - М.: Россия, 1993. - Т.20, - 123 с. 2. Мафтик С. Механизмы защиты в сетях ЭВМ. - М.: МИР, 1993.- 216
Эйнгорина Т. Н. Исследование и расчет адресных сетей матричных структур информационных систем
Научная библиотека диссертаций и авторефератов disserCat http://www.dissercat.com/content/issledovanie-i-raschet-adresnykh-setei-matrichnykh-struktur-informatsionnykh-sistem#ixzz55aSylGyh