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

Всем привет! Как вы знаете я немного связан с образовательной программой от 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!

Прочитал про теорему Дена о разрезании: если прямоугольник можно разрезать на квадраты, то отношение его сторон рационально. Интуитивно это кажется логичным, но доказать не так уж и просто. Обратное утверждение тривиально: если отношение сторон рационально и скажем равно 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", где дается много доказательство похожего, но другого по сути утверждения: что если прямоугольник разрезан на прямоугольники и у каждого внутренного прямоугольника хотя бы одна из сторон - целое число, то и у всего прямоугольника тоже хотя бы одна из сторон целая.

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

А вот и обещанная задача

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

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

(Кстати, это хороший способ потренироваться перед Колмом...)

Пользуясь случаем, напомню следующую задачу.

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

а) Докажите, что можно было собрать мешки с
такими же массами, использовав не более 4n-3 орехов.

б*) Какова точная оценка на число орехов, которого заведомо достаточно?

Пункт б) я решать не умею.

Опубликуем одну из задач нашей сегодняшней олимпиады «JetBrains Youth Challenge», автор — Д. В. Афризонов.

В лиге старших классов она была 4-й из 8, и её решили 8 команд из 50. А вы сможете?

#мт_задача

набросал вчера относительно длинный черновик поста с примерами того, что хотел бы закодить, но не могу (и почему именно не могу…)

но сегодня что-то посмотрел на один из примеров и решил, что глаза боятся, а… короче, код получился недлинный, но унесу все ж в комментарии

===

интересно считать количество разбиений разных фигур на доминошки

про прямоугольники 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

Всегда любил каплинги (они же спаривающие меры, они же многозначные отображения, они же полиморфизмы, они же планы перевозок и пр.) Идея в том, что для сравнения вероятностей двух событий надо умно реализовать их на одном вероятностном пространстве. Простой пример: красим каждую грань многогранника с вероятностью 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, и это имеет ту же вероятность.