Снова о пандемии и математике

Время от времени я думаю про себя, что у пандемии есть и свои плюсы. Звучит страшно, и мне, наверное, должно быть стыдно за такие мысли, когда так много людей страдает физически и так много теряет материальную основу существования. Это правда. Мы останемся с ковидом на некоторое время, возможно, ненадолго. Что будет дальше? Как это изменит нас? Многое, я считаю. Университет, в котором я работаю, уже объявил, что даже после пандемии лекции будут дистанционными, а только упражнения и лаборатории, как и прежде, в комнате с доской и… даже не мелом, а только с войлоком. кончик пера.

Но я должен написать о математике. Я не единственный, кто пришел к выводу, что мы должны учить наших учеников и студентов полностью, но это совсем не то, что было, скажем, 10 лет назад. Изменения подтолкнула не только пандемия, но и сумасшедшее ускорение, которое переживает наш современный мир. Тридцать лет назад в моем дачном поселке (несколько тысяч жителей) было пять таксофонов. В настоящее время в моей квартире пять телефонов и пять компьютеров. Ну, я все еще нахожу это странным.

Очень часто мы покупаем что-то через Интернет, товары оперативно доставляются на дом или в ближайший посылочный автомат. Разработка маршрута курьера для доставки нескольких десятков посылок требует поистине первоклассной математики. я мало что знаю о Алгоритмы задачи коммивояжера, потому что так называется экономическая проблема достижения многих точек, разбросанных по территории.

По телевизору стараюсь смотреть только спортивные передачи. Меня давно интересует «математика спорта». Поэтому сегодня два вопроса о планировании игр. Они показывают, что Королева наук имеет применение не только в строительной технике.

Лыжный спринт

Обычно в соревнованиях по лыжному спринту принимают участие 30 спортсменов. Четвертьфиналы разыгрываются сразу: пять раундов по шесть участников в каждом. Обладатели первого и второго места и так называемые удачливые неудачники, счастливчики-неудачники — двое (два) с лучшим временем из остальных. Но интересно — и совсем не элементарно — математика приходит с самого начала.

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

Горизонтальные строки такой таблицы называются ее строками, вертикальные — ее столбцами. Следующие пять забегов проводятся участниками с номерами из каждой строки: в первом заезде 1, 10, 11, 20, 21, 30 и т. д.

Давайте посмотрим, насколько математически сложна эта система — как тонко она сочетает порядок со случайностью. За каждым четным числом следует нечетное число в каждой строке и столбце, и наоборот. Мы можем выразить это, присвоив каждому четному числу ноль, а нечетному числу 1. Тогда массив будет выглядеть так:

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

Посмотрим, как выглядит массив с точки зрения «по модулю 3» — то есть разные цвета соответствуют остатку от деления чисел в массиве на 3.

Вот наша кроссовая таблица, рассматриваемая по модулю 5. В последнем такте все поля одного цвета, потому что все числа делятся на 5. Остальные поля одного цвета соединены движением шахматного коня.

Теперь давайте посмотрим на столбцы нашей матрицы распределения. В первом из них находятся числа из первой пятерки, расположенные в порядке 1, 4, 5, 2, 3. Заменив числа последовательными буквами, мы можем определить его как порядок ADEBC. Номера второго столбца расположены в порядке 10, 7, 6, 9, 8, что дает EBADC. Эти заказы связаны следующим образом:

Если вы помните, что такое перестановки, то она у вас есть. Мы видим взаимно обратные друг другу перестановки. Это еще один пример тонкого сочетания хорошего микширования с некоторой регулярностью.

Следовательно краткий курс теории перестановок. Мы, наверное, помним, что такое перестановка: это расположение цифр, букв, предметов в определенном порядке, в определенном порядке. Перестановка 1, 2, 3, 4, 5 (по буквам ABCDE) называется тождеством.

Если при перестановке большее число стоит перед меньшим (более поздняя буква алфавита перед более ранней), то говорят, что пара образует инверсию. Например, в перестановках 1, 2, 3, 5, 4 одна инверсия, в перестановках 2, 3, 4, 5, 1 — четыре, а в перестановках 5, 4, 3, 2, 1 — столько же. насколько это возможно для пяти элементов: 10.

Подсчитаем вообще, сколько инверсий имеет перестановка, располагающая элементы в порядке, обратном натуральному: 5, 4, 3, 2, 1 или е, d, с, Ь, а. Если есть n, то в этой перестановке каждое число образует инверсию с любым другим. Отсюда следует, что мы имеем здесь

инверсия. Произведение n (n-1) нужно было разделить на 2, иначе мы бы считали каждую инверсию дважды.

Для каждой перестановки существует обратная. Образно говоря, если рассматривать перестановку как смешение чего-то, то обратная перестановка восстанавливает естественный порядок. Например, обратная перестановка 3, 4, 1, 5, 2 равна 3, 5, 1, 2, 4. Это легко понять таким образом. Если у нас есть установка 3, 4, 1, 5, 2, то мы восстановим естественный порядок, расположив эти числа в порядке: третье (это 1), пятое (это 2), первое (= 3), второй (= 4), четвертый (= 5). Иногда перестановка противоположна самой себе, например 2, 1, 3, 5, 4. Перестановка 5, 4, 3, 2, 1 обладает этим свойством.

Сделаем еще одно наблюдение по поводу посева игроков. Мы будем рассматривать перестановки столбцов матрицы рассеяния, то есть 1, 4, 5, 2, 3, затем 10, 7, 6, 9, 8 и так далее. После преобразования цифр в буквы это будут перестановки ADEBC, EBADC, затем снова ADEBC, EBADC и снова то же самое: ADEBC, EBADC. Перестановки ADEBC и EBADC противоположны друг другу.

Отдельные шестерни должны быть выровнены; поэтому лучше всего, если среднее значение рейтинга будет одинаковым во всех из них. Но они также должны быть похожи с точки зрения дисперсии. Было бы нехорошо, если бы в одной гонке стартовали номера 1, 2, 3, 18, 19, 20, а в другой — 8, 9, 10, 11, 12, 13.

Стандартное отклонение является мерой статистической дисперсии. Мы определяем их как корень суммы квадратов отклонений от среднего, но это было бы утомительным путешествием в высшую математику.

Давайте взглянем на другие тонкие зависимости, управляющие настройкой плеера. Читатели, знакомые с линейной алгеброй, поймут следующие несколько предложений. Что ж, строка матрицы интервалов равна 2, поэтому наименьшим он может быть для чисел от 1 до 30. Это дополнительный аргумент в пользу того, что придуманный федерацией интервал сочетает регулярность со случайностью. Также обратите внимание, что система гарантирует, что два лучших участника не встретятся до финала. Совершенно понятно, что так и должно быть. Имея все это в виду, мы видим, что лыжная федерация наняла хорошего математика для составления схемы спринта.

Вернемся к интересной и непростой, но элементарной математике.

Гонки по спидвею

Признаюсь, не понимаю популярности этого вида спорта, но не в этом дело. Вот где проблема заполнения действительно касается серьезной математики. Итак, сначала «теоретическое введение».

Леонард Эйлер (1707-1783, швейцарский математик и физик, много лет проживший в Петербурге) размышлял над проблемой, которая казалась чистой загадкой, не имеющей практического применения. Шесть полков отправляют на парад по шесть офицеров разных рангов. Можно ли их разместить в квадрате 6 на 6 так, чтобы полки и ступени не повторялись ни в одном ряду или столбце?

Рассмотрим более общий момент. Есть офицеры из n разных полков. Легко организовать порядок так, чтобы у каждого полка был свой представитель в каждом ряду и столбце. Вот одна из возможных настроек. Пронумеруем полки от 0 до. Поставить офицера из полка номер + на место () парадной площади. Символ мод означает, что данное число делится на и мы берем остаток от этого деления. При = 6 имеем

Квадрат, содержащий числа от 1 до так, что одинаковые числа не повторяются ни в горизонтальных рядах, ни в вертикальных столбцах, называется латинским квадратом. Название происходит от старой привычки использовать здесь буквы латинского алфавита, а не цифры.

Мы можем получить тот же квадрат другим способом, тоже алгебраическим. Вместо сложения рассмотрим умножение по модулю 7. Это похоже на умножение дней недели: 3 раза в четверг — это 12 дней друг от друга, то есть от понедельника до следующей пятницы: 3 · 4 = 12≡5 7 и т. д. Давайте составим таблицу умножения. по модулю 7:

Вы видите, что это «та же самая» таблица, что и предыдущая. Порядок нужно немного изменить. Расставляем числа 1, 2, 3, 4, 5, 6 в порядке 1, 3, 2, 6, 4, 5 и перенумеровываем на 0, 1, 2, 3, 4, 5.

Квадрат, который мы выяснили, таков: каждое число находится рядом с каждым, как в строке, так и в столбце. На параде будет генерал, который будет ходить рядом с лейтенантом, и капитан рядом с адмиралом. Если бы серия почтовых марок была издана на листе, расположенном в виде полного латинского квадрата, филателисты получили бы удовольствие: можно было бы собирать марки парами, каждая рядом с каждой. Все латинские квадраты, расположенные по правилу умножения по модулю некоторого простого числа, полны.

В терминологии, поясняемой в следующем абзаце, такой квадрат ортогонален своей транспозиции.

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

Положим первое на второе, затем первое на третье и, наконец, второе на третье. Мы будем получать последовательно

В каждом из них символы определенных типов перемешаны наилучшим образом: друг с другом, но нет повторений ни в строках, ни в столбцах. Если это так, то квадраты К и L (а также квадраты К, М и L, М) называются ортогональными. Квадраты и мы уже называем греко-латинскими; это потому, что Эйлер обозначал элементы этих квадратов латинскими и греческими буквами.

Задача (для моих студентов IT-колледжа она была достаточно сложной). Докажите, что для квадрата N нет ортогонала.

И вот мы подошли к мотогонкам. В соревнованиях принимают участие 16 игроков. В каждой гонке их четыре. Вы должны планировать пробежки так, чтобы каждый встречался с каждым один раз. Сколько передач нужно? Как их оформить?

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

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

Wiersze: (1-2-3-4) (5-6-7-8) (9-10-11-12) (13-14-15-16)

Kolumny: (1-5 -9-13) (2 -6-10-14) (3-7-11-15) (4-8-12-16)

Затем смотрим на позиции буквы А в первом квадрате. Это позиции 1, 6, 11, 12. Эти участники стартуют в девятом заезде. В десятом считаем места буквы в первом квадрате, затем С, Г и переходим к следующему квадрату (буквы) и третьему (цифры 1, 2, 3, 4). Получаем порядок передач 9-20:

А: (1-6-11-12) Б: (2-5-12-15) В: (3-8-9-14) Г: (4-7-10-16)

a: (1-14-7-12) b: (2-8-11-13) c: (3-5-10-16) d: (4-6-9-15)

1: (1-8-10-15) 2: (2-7-9-16) 3: (3-6-12-13) 4: (4-5-11-14)

Мастера ревущего двигателя удивились бы, если бы узнали, что они трутся о теории латинских ортогональных квадратов. Хотя они могли бы и вовсе не удивиться, потому что это ничего бы им не сказало. Но не все должны знать все. У меня нет прав на вождение мотоцикла.

Однако мы подошли к высшей математике. Еще Леонард Эйлер подозревал, что невозможно составить греко-латинский квадрат из шести строк и шести столбцов. В 1782 году он сформулировал более общую гипотезу о невозможности составить такой квадрат из любого числа форм = 4 + 2. В 1959 г. Бозе, Шрикханде и Паркер продемонстрировали ложность этой гипотезы Эйлера для > 6, то есть расположили квадраты любого порядка k для > 6. Греко-латинского квадрата порядка 6 до сих пор не существует.

Может быть, нет, потому что этого не может быть, а может, никто не придумал подходящей идеи.