Max Home IndustryЕжегодная рождественская лекция Дональда Кнута в этом году посвящена совершенно новой проблеме, у которой нет долгой истории, и в этом суть. Он показывает, что математика — это живой и увлекательный предмет. Видео стоит посмотреть.
По традиции Стэнфордского университета в декабре Дональд Кнут надевает яркий джемпер и читает публичную лекцию, в которой, если это вообще возможно, используется та или иная древовидная структура. Этот год кажется еще одним годом без деревьев, поэтому я полагаю, что это должна быть лекция, не посвященная рождественским деревьям. Это называется «Гипотеза, которая должна была быть верной», но ее настоящая ценность в том, что она дает вам некоторое представление о том, что такое математические исследования.
Рекламное объявление о мероприятии гласит:
Несколько месяцев назад докладчик провел обширные вычисления, относящиеся к любопытной задаче комбинаторной геометрии; и полученные числа удовлетворяли удивительной формуле. Хотя было известно, что эта формула верна только в пяти или шести самых маленьких случаях проблемы, было невозможно представить себе достойный мир, в котором формула не была бы универсальной. Приходите на лекцию и узнайте об интересном продолжении.
Проблема очень проста и начинается с разделения прямоугольника на другие меньшие прямоугольники — проблема Мондриана? Например:
Вы можете охарактеризовать деление, присвоив целые числа каждой из линий деления. Таким образом, приведенный выше пример выглядит следующим образом:
Следующим шагом является формирование уменьшенной конфигурации, что по сути означает рисование координат разделительных линий квадратами одинакового размера:
Это то, что Кнут называет сокращенным шаблоном, и вы можете видеть, что прямоугольники имеют одинаковые координаты. Вы также можете видеть, что это эквивалентно оригинальному мондрианскому образцу.
Всякий раз, когда вы получаете такую комбинаторную компоновку, всегда возникает вопрос: «Сколько существует возможностей?». В этом случае представляет интерес вопрос «сколько там плотных дорожных покрытий?». Плотное покрытие — это укороченное покрытие с минимальным количеством прямоугольников. Оказывается, что для компоновки n x m наименьшее количество прямоугольников в уменьшенной компоновке равно n + m-1. Таким образом, плотное покрытие — это такое покрытие, в котором используется n + m-1 прямоугольников, но сколько их существует для любого n x m?
Кнут приводит в видео примеры для 2 x 2, 3 x 2, чтобы вы могли понять идею. Конечно, по мере увеличения размера вы должны использовать компьютер, и именно поэтому возникла гипотеза о взаимосвязи между n, m и количеством плотных дорожных покрытий.
А теперь посмотрите видео — это как раз мощь математики.
Если вы знаете, кто такой Дональд Кнут, перейдите к 1:45, чтобы избежать знакомства.
В этом видео так много интересного, но именно медленный прогресс от конкретного к абстрактному очень интересен и показывает, как математическое мышление прекрасно работает.