Зачем мне эта математика

Привет! Обычно перед публикацией задачи мы даём теорию. Но сегодня будет сразу задача: на какую цифру оканчивается число 2²⁰²³? А число 3²⁰²³? Ждём ваших решений под скрытым текстом.

Суперперестановки и любители аниме Иногда серьёзная математика возникает совершенно неожиданно. Сегодняшняя история этому пример. В не столь далёком 2011 году на имиджборде 4chan фанат аниме задал вопрос о сериале Меланхолия Харухи Судзумии. В его сюжете есть путешествия во времени, поэтому 14 серий первого сезона можно смотреть в разном порядке. Фанаты спорили, какой порядок серий лучше, а один пользователь спросил: если бы вы захотели посмотреть эти серии во всех возможных порядках, какое количество эпизодов было бы в самом коротком списке? Можно сформулировать задачу и по-другому. Если серии пронумеровать буквами (14 разных цифр у нас нет, поэтому берём буквы), то какова минимальная длина огромного слова, в котором присутствует любая из возможных перестановок 14 элементов? И это вопрос про кратчайшую суперперестановку! Разберёмся, что это такое. Суперперестановкой n символов называется слово, содержащее в качестве подслова каждую из возможных перестановок данных n символов. Тут легче сразу пояснить на примере. 😅 Пусть наш алфавит состоит только из двух символов: 1 и 2. Возможны всего две перестановки из этих элементов: 12 и 21. Кратчайшим словом, содержащим обе эти перестановки, будет 121 — в нём встречается и 12, и 21. Слово 212 тоже подходит. Как видно, в суперперестановке разрешён «нахлёст», то есть любой символ может быть частью разных подслов одновременно. Длина кратчайшей суперперестановки двух символов равна 3. Для алфавита из трёх символов ситуация поинтереснее. Здесь самая короткая суперперестановка имеет длину 9 — например, 123121321. Составить корректную суперперестановку несложно — можно просто выписать все перестановки одну за другой в виде длинного слова. Но это неспортивно! Математиков, конечно же, интересует кратчайшая из возможных суперперестановок для каждого n. При n = 4 она имеет длину 33, а при n = 5 — длину 153. Доказано, что для 1 ⩽ n ⩽ 5 кратчайшая суперперестановка n символов имеет длину 1! + 2! + … + n! (можете убедиться, что будут получаться именно значения 1, 3, 9, 33 и 153). Для случаев n > 5 данная формула, увы, не работает, и рассчитать точную длину кратчайшей перестановки сложно. Поэтому оценивают её нижнюю и верхнюю границы. Конечно, можно сказать, что нижняя граница равна 1, а верхняя — какому-нибудь большому числу вроде 10^{100}. Но ценности в таком результате мало. Математики хотят получить такие оценки границ, которые максимально близки к точному значению. Другими словами, важно, чтобы нижняя была как можно выше, а верхняя — как можно ниже. И лучшая из всех доказанных формул для нижней границы родилась именно на имиджборде! Буквально через час первому фанату ответил другой — он привёл в общем виде формулу для расчёта нижней границы на любое количество эпизодов: n! + (n − 1)! + (n − 2)! + n − 3. Из его рассуждения следовало, что для первого сезона этого сериала пришлось бы посмотреть не менее 93 884 313 611 серий подряд. Несколько лет это событие оставалось незамеченным, а потом копию постов увидели математики. Они всё проверили и написали статью с формально оформленным доказательством. Первым и главным автором они указали Анонимуса с 4chan, ведь имя этого героя до сих пор неизвестно. Вот такая великолепная история. Кстати, чтобы посмотреть те 14 эпизодов во всех возможных порядках, потребуется примерно 4 миллиона лет. Запасаемся попкорном!

[ продолжение поста о размещениях и сочетаниях ] Если порядок важен Если порядок важен, то вычислить количество возможных коктейлей из трёх ингредиентов поможет правило произведения: существует 10*9*8 = 720 вариантов. Мы только что нашли количество размещений из 10 по 3. Это похоже на «укороченную» перестановку: порядок важен, но количество доступных слотов меньше общего количества элементов. В общем виде количество размещений из n по k вычисляют как n! ÷ (n-k)! или n*(n-1)*(n-2)*…*(n-k+1). В записи через произведение будет k множителей. Размещения применяют: • Когда нужно выбрать несколько элементов для разных целей, разных дней, разных ролей. • В задачах на расположение, когда элементы различимы. Например, надо выбрать несколько человек из группы и разместить их на креслах в кинотеатре. Люди разные, поэтому имеет значение, кто где сядет. Если порядок не важен Вернёмся в ситуацию выбора 3 ингредиентов из 10. Теперь рассмотрим ситуацию, когда напитки просто перемешивают. Тогда порядок, в котором их выберут, не важен. Значит, набор ABC для нас не отличается от, например, набора BCA. Сколько наборов «склеятся» в один? Столько, сколько возможно перестановок из 3 элементов, то есть 3!. Значит, чтобы получить количество вариантов выбора 3 из 10 без учёта порядка, нужно предыдущий ответ поделить на 3!: (10*9*8) ÷ 3! = 720 ÷ 6 = 120. Число заметно уменьшилось! Мы нашли количество сочетаний из 10 по 3. В общем виде количество сочетаний из n по k вычисляют как n! ÷ ((n-k)!*k!). Cочетания применяют, если: • Выбирают несколько элементов одновременно. В учебниках по математике самый частый пример — мешок с шариками, из которого вытаскивают несколько шариков за раз, одной горстью. • Выбирают пару (тройку, группу) для взаимного или равноправного процесса. Например, двух человек для партии в шахматы, две команды для игры в хоккей, три бренда одежды для коллаборации, две точки для соединения отрезком, десять человек для хора. Задачка для вас Владелец ресторана составляет график работы официантов. Всего в штате 12 официантов, и каждый день должно работать 5 из них. 1) Сколько разных вариантов смен может составить владелец ресторана, если задачи всех официантов одинаковые? 2) Сколько разных вариантов смен может составить владелец ресторана, если в смене каждому официанту дают свою уникальную задачу? Ответы традиционно ждём в комментариях под скрытым текстом.

В комбинаторике есть два похожих термина: размещения и сочетания. Сегодня на конкретном примере разберём разницу между ними. Представим, что есть 10 напитков, из них нужно выбрать 3 для приготовления коктейля. Тут возможны две ситуации: когда порядок выбора важен и когда нет. Если по рецепту ингредиенты идут слоями — порядок важен. Коктейль со слоями ABC отличается от коктейля со слоями BCA. Если же ингредиенты просто перемешивают, то из наборов ABC и BCA получатся одинаковые коктейли. Это ситуация, когда порядок выбора не важен. Рассмотрим вначале ситуацию со слоями. Продолжение ↓↓↓

[ продолжение разбора задачи про роботов и масло ] Для каждого робота приготовим уникальную смесь масла. В смесь для N-ного робота добавим масло только из тех канистр, номер которых содержит единицу в N-ном разряде. Например, все «нечётные» роботы точно будут иметь в смеси масло из первой канистры, а «чётные» — не будут. Процесс приготовления смесей будет долгим, но зато потом можно одновременно залить масло сразу во всех роботов. Почти всё! Выжидаем 10 минут и смотрим, кто сломался. Каждый робот имеет только два состояния: 0 — исправен (если в нём только хорошее масло) или 1 — сломан (если в него попало испорченное масло). Обозначить можно и наоборот, но нам больше понравилось так. Через 10 минут мы получим номера сломанных роботов, а значит, номера разрядов с единичками. Они однозначно кодируют одну конкретную канистру. Например, если сломались только роботы с номерами 1, 2 и 3, то масло было испорчено в канистре с номером 000000000000111, то есть в седьмой. Поздравляем решивших правильно, это непростая задача!

Разбор задачи про роботов и масло 15 роботов достаточно! И доказать это нам поможет двоичная система. Переведём номер каждой канистры в двоичное представление. Запишем в виде чисел из 15 разрядов — количество разрядов равно количеству роботов (при необходимости слева допишем нули). 1 ∼ 000000000000001, 2 ∼ 000000000000010, 3 ∼ 000000000000011, 4 ∼ 000000000000100, 5 ∼ 000000000000101 и так далее. С помощью 15 разрядов в двоичной системе можно пронумеровать 2^{15} = 32 768 канистр. У нас их меньше, значит, каждая канистра получит уникальный номер. Последняя канистра будет иметь номер 30 000 ∼ 111010100110000. Пронумеруем роботов от первого до пятнадцатого. Поскольку разряды нумеруют справа налево, то и роботов пронумеруем так же. Продолжение ↓↓↓

Роботы и масло Сегодня предлагаем вам классическую задачу с собеседований, но в нашем прочтении. :)

Есть 30 000 канистр с маслом и 15 роботов, которые работают на этом масле. Известно, что в одной из канистр масло испорченное. Если робота заправить испорченным маслом (даже капелькой!), то уже через 10 минут он выйдет из строя. 

Масло в роботов заливают одновременно (способ для этого есть). Хватит ли 15 роботов, чтобы найти испорченную канистру?

1) Если нет, то укажите минимальное количество роботов, которое позволит её найти. 2) Если да, то напишите способ поиска испорченной канистры. Ваши варианты, как всегда, ждём в комментариях под скрытым текстом. Разбор задачи опубликуем в понедельник.

Прямой эфир Каналу «Практически математически» уже три месяца, а счётчик аудитории подошёл к 3000. Мы считаем, это хороший повод встретиться, поэтому в феврале проведём небольшой эфир. Предлагаем вам выбрать тему. Выберите самый интересный для вас вариант.

Прямой эфир: выбираем тему Каналу «Практически математически» уже три месяца, а счётчик аудитории подошёл к 3000 — это хороший повод встретиться. В феврале планируем провести небольшой эфир и предлагаем вам выбрать тему.

3D-графика В 3D всё зависит от используемого инструмента. Для создания 3D-моделей в редакторе вам вряд ли понадобится оперировать матрицами. Однако, если вы делаете какую-то игру, симуляцию или процедурную анимацию, то потребность в математике значительно возрастает. Из-за третьей координаты мы не можем просто так отобразить 3D-мир на экране, так как экран двумерный. Нужно как-то проецировать 3D в 2D. Для этого, как и в реальном мире, используется камера, только виртуальная — через неё мы «снимаем» виртуальный 3D-мир, и получаем 2D-картинку. Этот процесс называется рендерингом.  Как правило, рендеринг уже реализован в 3D-редакторах, но иногда для создания некоторых эффектов камеры требуется разбираться в его математике, которая построена на матричных операциях. Из-за появления камеры возникает ещё одна точка отсчёта — теперь 3D-объекты можно рассматривать как от какой-то фиксированной точки в пространстве (начало отсчёта), так и от положения камеры. В результате появляется необходимость говорить о базисе: у каждого объекта несколько наборов координат в зависимости от того, в каком базисе мы его рассматриваем. В 3D-редакторах базис обозначен осями, вдоль которых можно двигать и масштабировать объект, часто есть функция переключения между базисами. Иногда работать с координатами в одном базисе гораздо удобнее, чем в другом. В коде с базисами приходится работать исследователям компьютерного зрения, которые создают 3D-модели по фото и видео — например, эта задача возникает при разработке беспилотных автомобилей и роботов, а также оцифровке помещений. Вращение объектов в 3D и кватернионы, это отдельный большой топик и камень, о который бьются мизинцем многие начинающие артисты. Вкратце, для описаний вращений в 3D недостаточно трёх углов, как это может показаться (см. gimbal lock), требуется вводить понятие кватерниона, объекта, который задаётся 4-х мерным вектором и очень плохо интерпретируется человеком. Зато это позволяет легко производить любые вращения и повороты. Например, плавный поворот камеры для записи сцены. В основном необходимость напрямую взаимодействовать с кватернионами возникает при создании игр или какой-то процедурной графики — там, где приходится управлять 3D-объектами с помощью кода. Конечно, есть ещё много применений математики в 2D и 3D-графике, которые я не описал, но боюсь что попытка это сделать потребует отдельного блога 🙂 Отдельные богатые математикой смежные направления, на которые я могу указать: симуляции (физики, жидкости, плавучести, объёмного тумана, ...), генерация 3D-моделей через код, создание шейдеров, управление персонажем в играх.

2D-графика В 2D-графике сегодня основные инструменты — это графические редакторы и нейронные сети с текстовым интерфейсом. И там, и там вся математика находится под капотом удобных интерфейсов, и чтобы повернуть картинку, совсем не нужно думать о матрицах, а чтобы сгенерировать концепт-арт, не нужно думать о математике нейронных сетей. Есть направления creative coding/генеративное искусство/процедурная генерация, в которых графика создаётся через программирование. Вот здесь математика всплывает сразу. Как правило, в генеративном искусстве работа ведётся с различными примитивами: прямыми, точками, многоугольниками, каждый из которых задаётся наборами координат, которыми нужно манипулировать вручную. Нет кисточки, нельзя разместить объект, просто ткнув на экран — всё происходит через код. Объект создаётся, и ему выставляются просчитанные вами координаты, которые располагают его так, чтобы в итоге возник какой-то красивый арт. Чтобы рассчитать эти координаты, нужно применять разную математику в зависимости от желаемого расположения объектов. Поэтому, чтобы реализовывать свои идеи, может быть очень полезно понимать операции над векторами, уравнение прямой, полярные координаты, тригонометрию. Например, для генерации приложенной картинки понадобилось параметрическое уравнение спирали, синусы и косинусы, с помощью которых выставлялись координаты точек, к которым затем прибавлялся определённый уровень шума. Продолжение ↓↓↓

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

Разбор задачи про мышь Любой путь мышки можно записать при помощи последовательности букв П (право) и В (верх). Например, один из подходящих путей можно записать при помощи последовательности ППВПППВВВПППВВП. Каждый путь взаимно однозначно задаётся последовательностью из 15 букв, среди которых 9 букв П и 6 букв В. Значит, различных путей столько же, сколько таких различных последовательностей. Посчитаем способы выбрать 6 из 15 мест в последовательности для букв В, а на остальные места поставим П. Это сочетания, так как все буквы В идентичны и их перестановка внутри последовательности не влияет на результат. По формуле для количества сочетаний: 15! / (9! * 6!) = 5005. А если у вас под рукой есть треугольник Паскаля, то можно посчитать ряды в прямоугольнике и увидеть, что сыр стоит на шестом месте 15-го ряда (ряды и места в каждом ряду нумеруются с нулевого). Поэтому искомый коэффициент равен 2002+3003, то есть всё те же 5005. Научиться решать подобные задачи можно в модуле «Комбинаторика» бесплатного тренажёра по математике. Задачам на сочетания посвящен специальный урок.

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

Мышь бежит по линиям квадратной сетки 6×9, как показано на рисунке. Сколькими способами она может добраться до сыра?

Ответы и ход решения публикуйте в комментариях за скрытым текстом. Если видели задачу в тренажёре и знаете ответ — не раскрывайте его, пожалуйста. Разбор опубликуем завтра.

3 интерактива из основ математического анализа В курсах Практикума по математике нет видео, только текст и иллюстрации. Но порой статичных изображений не хватает, и тогда в дело идут интерактивы. Особенно много интерактивных иллюстраций в модуле по матану курса «Математика для анализа данных». Вот некоторые из них. Советуем смотреть на большом экране. График параболы — показывает, как изменение коэффициентов квадратичной функции влияет на положение и вид параболы. Меняйте значение коэффициентов и наблюдайте за поведением графика. Касательная к графику — иллюстрирует идею, что чем круче наклон касательной в точке, тем быстрее в этой точке растёт или убывает функция, а значит, больше модуль значения производной. Водите курсором по параболе и смотрите за производной. Площадь под кривой — иллюстрирует понятие определённого интеграла. Двигайте точки на оси Ox и наблюдайте, как меняется значение интеграла и площадь под кривой. Ну а чтобы увидеть, как интерактивные иллюстрации работают вкупе с текстом, приходите на курс «Математика для анализа данных». Ближайшая когорта стартует 23 января. Узнать больше про курс

Сегодня понедельник, поэтому возвращаемся к рубрике про простые числа! Занимательный факт: любое простое число, большее 3, обязательно представимо в виде x*k+1 либо x*k-1. Здесь k — произвольное натуральное число, а вот x — конкретное фиксированное натуральное число. Какое оно? Предлагаем вам выяснить самостоятельно перебором (это не займёт много времени). Когда вы найдёте x, в формулах останется только одна переменная. Придавая ей разные значения, можно будет найти все простые числа. Но будьте осторожны, утверждение работает только в одну сторону: верно, что все простые числа больше 3 описываются этими формулами, но неверно, что все числа, описываемые этими формулами — простые. Напоминаем, что универсального алгоритма для поиска простых чисел не существует.

Вчера мы предложили вам раскрасить математическую ель, следуя условиями теоремы о чётырёх красках. Рисунков было не очень много, зато все правильные. Спасибо тем, кто поучаствовал! Сегодня делимся нашей версией. Важное замечание: в задании не было указано, считать ли за область карты фон. В комментариях были разные варианты (и все они корректные). В нашей версии картой считается только сама ель, а фон — нет. Вот такая теорема! Кстати, у неё есть применение не только в картографии, но об этом расскажем в другой раз.

Раскрасьте ёлочку! Предлагаем вам проверить теорему, раскрасив эту праздничную математическую ель. Условия: 1) использовать не больше четырёх цветов, 2) любые две области с общим участком границы должны иметь разный цвет. Расходуйте краски экономно, и, быть может, у вас получится обойтись даже меньшим числом цветов. Раскрашенными рисунками делитесь в комментариях. Это могут быть как фотографии елей, раскрашенных вручную, так и скриншоты из графических редакторов. Спрятать иллюстрации за скрытым текстом не выйдет, поэтому рекомендуем не заглядывать в комментарии, пока не закончите красить. Ждём ваших рисунков до конца завтрашнего дня.

Теорема о четырёх красках Теоремы в математике бывают самые разные и порой возникают из вполне практических задач. В 1852 Фрэнсис Гутри составлял карту графств Англии и заметил, что хватает всего четырёх красок. Из этого факта родилась теорема: Всякую расположенную на плоскости или на сфере карту можно раскрасить не более чем четырьмя разными цветами (красками) так, чтобы любые две области с общим участком границы имели разный цвет. Уточнения: - область не может состоять из нескольких отдельных «кусков», каждый из них будет считаться отдельной областью; - в теореме речь про области, у которых есть общая граница ненулевой длины; если у двух областей только одна общая точка границы, то они могут быть и одноцветными. Переводя на язык географии: никаких эксклавов и никакой воды (под неё бы потребовался ещё один цвет). Точно ли хватит четырёх красок? Доказать теорему долгое время не удавалось. В конце XIX века доказали, что всегда будет достаточно пяти цветов, но для четырёх дело шло туго. В итоге доказательство нашли лишь в 1976 году, причём с помощью компьютера. Кстати, это была первая большая теорема, доказанная таким образом. На первом шаге доказательства авторы продемонстрировали набор из 1936 карт, ни одна из которых не могла содержать карту меньшего размера (которая опровергала бы теорему). Авторы использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из 1936 карт. Далее шёл вывод, что раз для этих карт нет контрпримера, то его не будет и дальше, так как любая бóльшая карта по сути является лишь склейкой из данных 1936 видов. Доказательство теоремы заняло несколько сотен страниц! Многие математики были недовольны: это вам не тёплое ламповое «человеческое» доказательство, да и вручную его не проверишь. А ещё в нём потом были найдены ошибки. 😇 К 2005 году ошибки устранили, всё перепроверили несколько раз и сконструировали более простое доказательство, основанное на том же принципе. Количество видов карт удалось сократить до 633. Так что сейчас всё в порядке, теоремой можно пользоваться!