В задаче по «упаковке цветов графа» (в оригинале packing coloring, — прим. пер.) спрашивается, сколько чисел необходимо для заполнения бесконечной сетки так, чтобы идентичные числа никогда не оказывались слишком близко друг к другу. И новый арифметический эксперимент с использованием компьютера даёт на удивление простой ответ.
Сколько чисел потребуется для заполнения бесконечной сетки так, чтобы расстояние между вхождениями одного числа было больше самого этого числа?Читать полностью »
В сообществе игры «Жизнь», изобретённой Джоном Конвеем, отмечали знаковое достижение, совершённое 9 ноября 2022 года. Идея, на воплощение которой ушли годы – проект «обратный шестометатель» — наконец дошла до той стадии, когда в наличии имелись все компоненты для этой сущности, позволявшие достичь заявленной цели.
Цель проста. Выбираем любой шаблон, который можно собрать в «Жизни» - например, ТихоходкуЧитать полностью »
Существует классическая задача:
Есть 2 емкости: 5 литров и 3 литра. Как отмерить 4 литра жидкости используя только эти 2 емкости?
Понятное дело что тут важно не сколько знание правильного ответа, а знание метода решения таких задач. Ведь вместо целевых 4х литров могут спросить отсчитать и 1,2,6,7 литров.
В этом тексте я решу эту задачу в общем виде при помощи конечного автомата. Так как тут явно можно проследить состояния и входные воздействия. Также я упомяну про малоизвестный язык Front-End разметки DotЧитать полностью »
Учимся находить лучшее для своего разбойника при помощи программирования. Также разбираемся, не водит ли нас программа «за нос».
В первой части поста мы рассказали о наших популярных онлайн-курсах на Stepik, а теперь выкладываем записи открытых лекций и видеокурсов на YouTube и напоминаем о том, что до 11 апреля открыт новый набор в CS центр в Санкт-Петербурге и Новосибирске.
Графы — схематическое обозначение во многих сферах.
Модель реальных объектов.
Круги — вершины, линии — дуги графа (соединения).
Если рядом с дугой цифра — это расстояние между точками на карте или стоимость на диаграмме Ганта.
В электрике и электронике вершины — это детали и модули, линии — проводники.
В гидравлике котлы, бойлеры, арматура, радиаторы и трубы.
На карте — города и дороги.
Из школьной задачи по математике:
Из пункта А в пункт Б выехал автобус. Расстояние между пунктами 30 км.
А что если расстояние 0?
Читать полностью »
Пару месяцев назад появилась занятная статья с анализом классической задачи о расстановке ферзей на шахматной доске (см. детали и историю ниже). Задача невероятно известная и вся уже рассмотрена под микроскопом, поэтому было удивительно, что появилось что-то действительно новое.
Сможете поставить ещё шесть? А найти все решения?
(картинка из статьи)
Далее, к сожалению, произошла какая-то совершенно невразумительная история из цепочки вот таких вот превращений:
Стоит отметить, что пять наугад открытых ссылок на русском ещё меньше проясняли картину происходящего.
Я тут подумал — надо бы кому-то эту странную цепочку прервать и нормальным языком изложить суть событий.
О чём пойдёт речь:
Сочетанием из 
по 
называется выборка из 
элементов, взятая на множестве содержащем 
элементов. Один и тот же элемент нельзя выбирать несколько раз; порядок, в котором нам предъявляют решение об избранности того или иного элемента не учитывается. Число всех возможных сочетаний из 
по 
равно 
— коэффициенту в биноме Ньютона. Факт известный каждому школьнику: о нём можно прочитать в википедии или любом учебнике, где вообще упомянаются сочетания и комбинаторика.
Однако почему эти два числа равны, нигде не объясняется. Возможно все считают этот факт очевидным и не требующим каких-то дополнительных пояснений.
На самом деле связь и вправду очень простая, если задуматься. Тем не менее, до какого-то момента связь между коэффициентами многочлена и комбинаторикой была для меня чем-то из области магии. Если для вас это и сейчас так, добро пожаловать под кат, буду объяснять очевидное.
Читать полностью »
После недавнего обновления экран «You win!» игры 2048 начал показывать количество ходов, потребовавшихся для победы, и я задался вопросом: сколько же нужно ходов, чтобы выиграть?
В первой части статьи мы ответим на этот вопрос, смоделировав игру 2048 в виде цепи Маркова и проанализировав её, чтобы показать, что вне зависимости от мастерства игрока для победы в среднем нужно не менее 938,8 ходов. Это даёт нам неплохое мерило отсчёта — если вы можете выигрывать примерно за такое количество ходов, то неплохо играете.
Количество ходов, необходимых для победы, зависит от случайности, потому что игра добавляет тайлы 2 и 4 случайным образом. Анализ также покажет, что распределение минимального количества ходов до победы имеет стандартное отклонение в 8,3 хода, и что его общая форма хорошо аппроксимируется смесью биномиальных распределений.
Читать полностью »
Так получалось, что мы рассказываем о наших проектах, но мало уделяем внимания содержанию наших нововведений. Сегодня мы постараемся рассказать об онлайн-магистратуре по современной комбинаторике через призму только что запущенного проекта — Лаборатории прикладных исследований МФТИ — Сбербанк.
