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

Всегда любил каплинги (они же спаривающие меры, они же многозначные отображения, они же полиморфизмы, они же планы перевозок и пр.) Идея в том, что для сравнения вероятностей двух событий надо умно реализовать их на одном вероятностном пространстве. Простой пример: красим каждую грань многогранника с вероятностью p независимо от остальных. Тогда вероятность того, что есть три попарно смежные покрашенные грани, возрастает с ростом p. Доказательство: пусть лучше каждая грань выбирает число от 0 до 1, и мы красим её, если число меньше p. Тогда наши события при разных p просто вложены друг в друга, и монотонность очевидна. Лёша Куликов обратил внимание на свежую работу на эту тему. Пусть n человек рассаживаются по k автобусам, выбирая, в который автобус сесть, равномерно и независимо. Рассмотрим вероятность p(k) того, что кто-то окажется единственным в своём автобусе (n считаем постоянным, а k переменным). Теорема. p(k) возрастает по k при данном n. Доказательство. Сравним p(k+1) и p(k). Можно считать, что дело обстоит так: сначала люди рассаживаются по k+1 автобусу, потом автобус семёрка ломается и люди оттуда рассаживаются по остальным. Нас интересуют вероятности двух событий: A - что до поломки был одинокий пассажир, B - что он есть после поломки и пересаживания. Сравним события A\B и B\A. Как могло произойти событие B\A? Скажем, Вася пересел из семёрки в пустую тройку, причём до поломки одиноких не было. Но до поломки могло быть так, что Вася - единственный в семёрке, потому что остальные, выбравшие семёрку, выбирали бы тройку (а всё остальное как было), а потом Вася пересел в тройку. В этом случае происходит A\B, и это имеет ту же вероятность.

набросал вчера относительно длинный черновик поста с примерами того, что хотел бы закодить, но не могу (и почему именно не могу…) но сегодня что-то посмотрел на один из примеров и решил, что глаза боятся, а… короче, код получился недлинный, но унесу все ж в комментарии === интересно считать количество разбиений разных фигур на доминошки про прямоугольники 2×N и числа Фибоначчи и так все знают а вот на картинке ацтекский бриллиант порядка 4 — сколькими способами его можно разбить на доминошки? а бриллиант порядка N? тут общий ответ можно угадать по ответам для небольших N, но перебирать руками тяжеловато (для N=4 вариантов уже больше тысячи), компьютерный эксперимент действительно полезен про разные способы этот ответ доказывать есть интересная брошюра Е.Смирнова «Три взгляда на ацтекский бриллиант», https://mccme.ru/free-books/dubna/smirnov-aztec.pdf *** более естественная, казалось бы, идея — считать замощения обычного квадрата N×N… но там по ответам для маленьких N ничего угадать не возможно все же перебрал на компутере и замощения квадрата 8×8 — в качестве ответа получилось название лекции С.Смирнова https://www.mathnet.ru/present18250

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

Пост благодарности! Я бы хотел поблагодарить всех участников олимпиады за то, что они не поленились потратить свое воскресное время на решение задач, борьбу с лингвистическими и, порой, техническими трудностями, и это при том, что олимпиада эта не дает практически никаких бенефитов — без вас эта олимпиада была бы неполноценной. Я бы хотел поблагодарить членов жюри, которые присоединились слушать задачи. Тоже ведь трудно заставить себя поучастовать в воскресном мероприятии, которое ничего кроме радости общения с единомышленниками тебе не принесет. Членам жюри тоже пришлось решать лингвистические и технические задачи, которые ставили перед ними участники. Спасибо вам! Хотелось бы, чтобы нас становилось больше и прослушка проходила в более спокойном режиме! Я бы очень хотел поблагодарить авторов задач, которые не пожалели потратить свои творения на в общем-то никому пока неизвестную олимпиаду. В этом году, на мой взгляд, вариант получился значительно более интересным именно благодаря вам. Спасибо и тем, кто прислал свои задачи, но задачи нам почему-то не подошли. Я очень надеюсь, что вы не перестанете придумывать задачи и будете столь же отзывчивы на наши просьбы о помощи! Я бы, конечно, хотел поблагодарить организаторов, потому что без их инициативы это мероприятие уж точно не состоялось бы. Организаторам всегда приходится не сладко, а работу их почти никто не видит. Ну и конечно, я хотел бы поблагодарить своих коллег по методической комиссии! Надеюсь олимпиада будет расти! И мы проведем ее еще лучше в следующем году. Пока что все задачи можно найти на аопсе. Но очень скоро мы доделаем и официальный файлик с условиями и решениями.

Опубликуем одну из задач нашей сегодняшней олимпиады «JetBrains Youth Challenge», автор — Д. В. Афризонов. В лиге старших классов она была 4-й из 8, и её решили 8 команд из 50. А вы сможете? #мт_задача

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

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

А вот и обещанная задача Есть гирьки массами 2⁰, 2¹, …, 2ⁿ грамм и чашечные весы, изначально находящиеся в равновесии. Нужно последовательно выставлять по одной гирьке на весы в некотором порядке так, чтобы в каждый момент времени правая чаша весов не перевешивала. Сколькими способами это можно сделать?

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

Прочитал про теорему Дена о разрезании: если прямоугольник можно разрезать на квадраты, то отношение его сторон рационально. Интуитивно это кажется логичным, но доказать не так уж и просто. Обратное утверждение тривиально: если отношение сторон рационально и скажем равно p/q, то увеличив масштаб в q раз, получим прямоугольник с целыми сторонами, который можно разрезать на квадраты 1x1. Линейная алгебра помогает построить простые и красивые доказательства: Отношение длин сторон прямоугольника W,H иррационально - это то же, что "W,H линейно независимы как векторы в пространстве R над Q". Это в свою очередь значит, что существует Q-линейная функция f:R->R, так, что f(W) и f(H) - любые удобные нам значения. Для любой Q-линейной функции f определим f-площадь прямоугольника со сторонами A,B как f(A)*f(B). Тогда легко увидеть, что при разрезании прямоугольника на другие прямоугольники f-площадь целого равна сумме f-площади частей (это очевидно при разрезании одного прямоугольника на два, и к повторению этого можно свести любое разрезание, если сделать из него "сетку", продлив все внутренние линии до краев). Как ни странно, доказательство почти закончено. f-площадь любого квадрата равна f(A)*f(A), то есть неотрицательна. Отсюда f-площадь любого прямоугольника размером W:H, разрезанного на квадраты, неотрицательна. Но если W/H не рационально, то мы можем выбрать такую f, что f(W)=1, f(H)=-1, и его f-площадь равна -1, это противоречие. Другое доказательство с помощью линейной алгебры вместо f-площади пользуется тензорным произведением R@R. Если стороны прямоугольника w,h линейно независимы, то {w,h} можно продлить до базиса, и поэтому ясно, что в R@R линейно независимы также векторы w@w, w@h, h@w, h@h. С другой стороны, если прямоугольник разбит на квадраты, то w@h является суммой членов вида a@a (доказательство аналогично примеру с площадью). Это значит, что изоморфизм в R@R, который меняет координаты местами, одновременно переводит w@h в h@w и оставляет неизменным, т.е. w@h = h@w, а это противоречит их независимости. Еще есть красивое доказательство с помощью гармонических функций на конечных графах (второе в этой заметке). А в древней книжке Яглома "Как разрезать квадрат?" (1968) есть элементарное доказательство через систему уравнений, связывающих длины сторон. P.S. Вспоминается также замечательная статья "Fourteen proofs of a result about tiling a rectangle", где дается много доказательство похожего, но другого по сути утверждения: что если прямоугольник разрезан на прямоугольники и у каждого внутренного прямоугольника хотя бы одна из сторон - целое число, то и у всего прямоугольника тоже хотя бы одна из сторон целая.

Всем привет! Как вы знаете я немного связан с образовательной программой от JetBrains в университете Неаполиса на Кипре. Один из преподавателей этой программы и мой хороший приятель Саша Авдюшенко на грядущей неделе проведет стрим на тему, как эффективно учиться (и учить!) с чатом ЖПТ. Ожидаю, что это будет очень классно! Регистируйтесь по ссылке и приходите! Livestream Alert: How to Study Effectively With ChatGPT 📚 Are you interesed in transforming your study habits with AI? Join our livestream on May 22 at 4:00 pm UTC as we explore the potential of AI in education, including ChatGPT and other cutting-edge tools. What we'll cover: 🚀 The latest AI tools: Explore the latest advancements, such as GPT-4, Google Gemini, and Anthropic Claude 3, and learn how they can boost your learning. 🎓 AI's impact on education: Discover how AI is changing how we study, from solving complex geometry problems to enhancing exam prep and coding skills. 💫 Balancing AI and learning: Learn to integrate AI effectively while fostering critical thinking and independent learning. See you there!

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