Олимпиадная комбинаторика

А вот кстати, завтра закроется регистрация на математический курс от Jet Brains. За три недели мы там поговорили про многочлены в целом, про разностный многочлен и вычисление разных сумм, про интерполяцию. Сейчас у нас первая неделя комбинаторного (дискретно-вероятностного) блока. И в нем мы дали одну, кажется, довольно трудную задачу. На вчерашний день ее правильно решил только один человек... из 400 зарегистрировавшихся на курсе (ну ладно, кого я обманываю, из 80-ти активно решающих). В конце ...

Прочитал про теорему Дена о разрезании: если прямоугольник можно разрезать на квадраты, то отношение его сторон рационально. Интуитивно это кажется логичным, но доказать не так уж и просто. Обратное утверждение тривиально: если отношение сторон рационально и скажем равно p/q, то увеличив масштаб в q раз, получим прямоугольник с целыми сторонами, который можно разрезать на квадраты 1x1. Линейная алгебра помогает построить простые и красивые доказательства: Отношение длин сторон прямоугольника W,H...

Так-так-так... Разыскиваются сильные команды, способные решить все задачи на JetBrains Math Challenge! Мне кажется, что в этот раз это будет не так просто... До окончания регистрации осталась всего неделя! А до самой олимпиады всего две недели (чуть меньше)! (Кстати, это хороший способ потренироваться перед Колмом...)

набросал вчера относительно длинный черновик поста с примерами того, что хотел бы закодить, но не могу (и почему именно не могу…) но сегодня что-то посмотрел на один из примеров и решил, что глаза боятся, а… короче, код получился недлинный, но унесу все ж в комментарии === интересно считать количество разбиений разных фигур на доминошки про прямоугольники 2×N и числа Фибоначчи и так все знают а вот на картинке ацтекский бриллиант порядка 4 — сколькими способами его можно разбить на доминошки? а ...

Всем привет! Как вы знаете я немного связан с образовательной программой от JetBrains в университете Неаполиса на Кипре. Один из преподавателей этой программы и мой хороший приятель Саша Авдюшенко на грядущей неделе проведет стрим на тему, как эффективно учиться (и учить!) с чатом ЖПТ. Ожидаю, что это будет очень классно! Регистируйтесь по ссылке и приходите! Livestream Alert: How to Study Effectively With ChatGPT 📚 Are you interesed in transforming your study habits with AI? Join our livestrea...

1 и 2 день, решения

Всегда любил каплинги (они же спаривающие меры, они же многозначные отображения, они же полиморфизмы, они же планы перевозок и пр.) Идея в том, что для сравнения вероятностей двух событий надо умно реализовать их на одном вероятностном пространстве. Простой пример: красим каждую грань многогранника с вероятностью p независимо от остальных. Тогда вероятность того, что есть три попарно смежные покрашенные грани, возрастает с ростом p. Доказательство: пусть лучше каждая грань выбирает число от 0 до...

Опубликуем ещё одну задачу с олимпиады «JetBrains Youth Challenge», автор — К. А. Кноп. В лиге младших классов она была 8-й из 8, и её решила всего 1 команда. Коллектив жюри ожидал большего количества решений этой задачи🙂 А оригинальная версия этой задачи была заметно сложнее — причём настолько, что методкомиссия даже не решилась вставлять её в лигу старших классов. Для продвинутых комбинаторов опубликуем и оригинальную формулировку тоже! #мт_задача

Пользуясь случаем, напомню следующую задачу. У Белочки есть бесконечно много орехов: по одному ореху каждой из масс 1 г, 2 г, 3 г, \dots. Она взяла n мешков, положила в каждый по конечному числу орехов, после чего написала на каждом мешке суммарную массу лежащих в нем орехов. а) Докажите, что можно было собрать мешки с такими же массами, использовав не более 4n-3 орехов. б*) Какова точная оценка на число орехов, которого заведомо достаточно? Пункт б) я решать не умею.