Задачки

Забавно, Мишустин задал задачу, которую я когда-то упоминал в моём блоге. Задача слишком хорошая для импровизации --- думаю не обошлось без предварительной подготовки.

Услышал вчера неплохую задачу на логику.

Есть три друга: Илья, Лёша и Стас. Илья всегда говорит правду, Лёша всегда врёт, а Стас выбирает ответ случайно.

Повстречав эту троицу и задав три вопроса типа да-нет (каждый вопрос задаётся одному человеку), как определить кто из них кто?

Задача простая, конечно.

Задача с Форт Боярд Математиков

На выходных наткнулся на Ютьюбе на Форт Боярд Математиков. Ничего особенно интересного я от него не ждал, поскольку хорошие задачи, всё-же, за пять минут не решаются. Ну и да, там в основном были задачи на троечку (кстати вот здесь Савватеев умудрился неправильно решить задачу про бикфордовы шнуры --- а ведущий её зачёл), да ещё и почти все я знал, в той или иной редакции. Например, задачу со шкафчиками мне в немного другом оформлении (про бесконечный ряд лампочек) рассказали во время одного из моих визитов в Карлсруэ --- даже помню кто. Задача со взвешиванием 8-ми монет --- это вообще баян, да ещё и упрощенный вариант. Задачу с круглым озером я тоже знал, только там была девушка на матрасе и хулиган. Задача про девочек и мальчиков --- первая задача из сборника задач Дж. Кронин, Д. Гринберг, В.Телегди. Теоретическая физика. Сборник задач с решениями, (только там мальчиков ждали). В общем, из всех задач, которые там предлагались, я не знал только самую сложную --- про кооперативную игру с монетами. Вот скриншот условия

Два популяризатора науки оказались перед этой задачей беспомощны, по-крайней мере, в пределах отведенных им на размышление пяти минут. Честно признаюсь, что я сразу подумал, что в условии неточность, тем более, что в другой задаче неточность уже была. Я решил, что имеется в виду, что популяризаторы говорят номера по-очереди, и что второй слышит ответ первого. Тогда, конечно, задача решается тривиально (кстати, вероятность в этом случае получается равна 1). Но потом я понял, что в такой постановке задача слишком тупая даже для пяти минут, так что стал решать, считая, что они называют номера одновременно. И, пусть не после пяти минут, а после 10-15 я придумал решение с вероятностью выигрыша 2/3. Я был почти уверен, что это решение оптимально и что сделать вероятность больше 2/3 невозможно, но это не так. Я знаю решение с вероятностью 7/10, но вот является ли оно оптимальным --- вопрос для меня открытый.

Гёмбёц

Недавно пытался придумать несколько задач для курса мат. анализа, которые не выглядели бы надуманными. То есть, я искал задачу, которая возникает время от времени в реальной жизни, но её решение требует знаний мат. анализа. Оказалось, что это совсем непросто. Либо задачи выглядят надуманными, либо не требуют для решения неэлементарных методов. Так что, должен признаться, ничего у меня толком не получилось. Но в процессе размышления придумал такую задачу

Доказать, что любая плоская выпуклая фигура с постоянной плотностью массы и гладкой границей имеет как минимум два устойчивых положения равновесия.

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

P.S. Пост был написан, наверное, с год. А с тех пор я пробовал дать эту задачу одному сильному фмшатнику. Он почти решил.

P.P.S. По воспоминаниям похожим образом решается ещё такая задача

Доказать, что фигура с минимальным периметром при фиксированной площади --- круг.

 И вот ещё

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

Эту последнюю задачу я, впрочем, только в предположении цилиндрической симметрии умею решать.

Формула суммирования Пуассона

Давным давно, когда был я чуть ли ещё не школьником, была у меня глупая привычка покупать научные книжки, даже если я и не очень понимал что в них написано. Одной из таких книжек (точнее, это были два тома) была монография “Упаковки шаров, решетки и группы” Конвея и Слоэна. Очень мне понравилась тогда бумага, на которой она напечатана — с одной стороны листа гладкая, а с другой — шершавая. И содержание тоже ничего было, хоть я тогда и много не понимал. И вот что меня поразило: оказывается, ко времени написания книжки не была доказана оптимальность даже гранецентрированной кубической упаковки в трёхмерье. Там, если я помню правильно, про эту оптимальность было написано как-то так: "все математики верят, а физики знают". Ещё я из этой книжки вынес, что размерности 8 и 24 --- какие-то особенные.

Так вот, оказывается, с тех пор многое изменилось. Оптимальность гранецентрированной кубической упаковки доказана в 1998 г. Томасом Халесом (Thomas Hales). А в начале этого года совсем молодая девушка-математик Марина Вязовска доказала оптимальность упаковки $\Lambda_8$ в восьмимерье (arXiv:1603.04246). И буквально через неделю вышла работа arXiv:1603.06518 с доказательством оптимальности упаковки для решётки Лича в 24-мерье, основанная на доказательстве в восьмимерье.

Работа Марины Вязовской концептуально очень ясная и опирается на ограничение на плотность упаковки сверху, полученное в работе arXiv:math/0110009. Это простое и, как оказывается, очень мощное ограничение доказывается с помощью формулы суммирования Пуассона. Если Фурье-преобразование функции $f(\boldsymbol{x})$ определить формулой \[\hat{f}\left(\boldsymbol{t}\right)=\int f\left(\boldsymbol{x}\right)e^{2\pi i\boldsymbol{x}\boldsymbol{t}}d\boldsymbol{x}\,,\]то справедлива следующая формула:\[\sum_{\boldsymbol{x}\in\Lambda}f\left(\boldsymbol{x}\right)=\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}\hat{f}\left(\boldsymbol{t}\right)\,.\]Здесь $\Lambda$ — любая решётка в $\mathbb{R}^{n}$, $\left|\Lambda\right|$— объём её элементарной ячейки, $\Lambda^{*}$ — двойственная к $\Lambda$ решётка. Если не гнаться за строгостью, эту формулу можно доказать так: \[ \frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}\hat{f}\left(\boldsymbol{t}\right)=\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}\int f\left(\boldsymbol{x}\right)e^{2\pi i\boldsymbol{x}\boldsymbol{t}}d\boldsymbol{x}=\int f\left(\boldsymbol{x}\right)\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}e^{2\pi i\boldsymbol{x}\boldsymbol{t}}d\boldsymbol{x}=\int f\left(\boldsymbol{x}\right)\sum_{\boldsymbol{y}\in\Lambda}\delta\left(\boldsymbol{y}-\boldsymbol{x}\right)d\boldsymbol{x}=\sum_{\boldsymbol{x}\in\Lambda}f\left(\boldsymbol{x}\right)\,. \] Ну, естественно, чтобы формула имела смысл, нужно чтобы функция и её Фурье-образ достаточно быстро спадали на бесконечности. Если сдвинуть аргумент в правой части на $\boldsymbol{v}$, то из свойств Фурье-преобразования имеем \[ \sum_{\boldsymbol{x}\in\Lambda}f\left(\boldsymbol{x}+\boldsymbol{v}\right)=\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}e^{-2\pi i\boldsymbol{v}\boldsymbol{t}}\hat{f}\left(\boldsymbol{t}\right)\,. \] Это как раз формула (2.1) из math/0110009. Далее доказывается следующая теорема. Допустим, что мы нашли функцию $f$ со следующими свойствами \begin{align*} 1. & f\left(\boldsymbol{x}\right)\leqslant0\text{ для }\left|\boldsymbol{x}\right|\geqslant1\\ 2. & \hat{f}\left(\boldsymbol{t}\right)\geqslant0\text{ для любого }\boldsymbol{t} \end{align*} Тогда центральная плотность (=число центров единичных шаров на единичный объём) периодических упаковок ограничена сверху величиной $\frac{f\left(0\right)}{2^{n}\hat{f}\left(0\right)}$. Вот такое неожиданное утверждение --- где функция, а где упаковка.
Доказательство совсем не сложное: пусть периодичность упаковки определяется решёткой $\Lambda$, причём в элементарной ячейке находится $N$ шаров. Для дальнейшего удобно считать, что радиус шаров равен $1/2$, так что расстояния между центрами любых двух не меньше единицы. Пусть расположение центров в элементарной ячейке задаётся векторами $\boldsymbol{v}_{1},\ldots,\boldsymbol{v}_{N}$. Запишем формулу суммирования Пуассона в таком виде \begin{equation} \sum_{j,k=1}^{N}\sum_{\boldsymbol{x}\in\Lambda}f\left(\boldsymbol{x}+\boldsymbol{v}_{j}-\boldsymbol{v}_{k}\right)=\sum_{j,k=1}^{N}\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}e^{-2\pi i\left(\boldsymbol{v}_{j}-\boldsymbol{v}_{k}\right)\boldsymbol{t}}\hat{f}\left(\boldsymbol{t}\right)=\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}\left|\sum_{k=1}^{N}e^{2\pi i\boldsymbol{v}_{k}\boldsymbol{t}}\right|^{2}\hat{f}\left(\boldsymbol{t}\right)\,.\label{eq:Poisson1} \end{equation} Аргумент $\boldsymbol{x}+\boldsymbol{v}_{j}-\boldsymbol{v}_{k}$ в левой части можно рассматривать как вектор, соединяющий центры шаров в точках $\boldsymbol{x}+\boldsymbol{v}_{j}$ и $\boldsymbol{v}_{k}$. Поэтому он может быть по модулю меньше единицы только если это один и тот же шар, т.е. $\boldsymbol{x}=0$, $j=k$. А значит, левая часть не больше $Nf\left(0\right)$. В правой части все слагаемые неотрицательны, поэтому она не меньше одного члена суммы с $\boldsymbol{t}=0$, т.е. $N^{2}\hat{f}\left(0\right)/\left|\Lambda\right|$. Поэтому получаем \[ Nf\left(0\right)\geqslant N^{2}\hat{f}\left(0\right)/\left|\Lambda\right| \] Поскольку наши шары имеют радиус $r=1/2$, центральная плотность равна $\delta=\frac{Nr^{n}}{\left|\Lambda\right|}=\frac{N}{\left|\Lambda\right|2^{n}}$ и мы имеем желаемое утверждение \[ \delta\leqslant\frac{f\left(0\right)}{2^{n}\hat{f}\left(0\right)}\,. \] А что же сделала Марина Вязовска? Она построила  для $\mathbb{R}^{8}$ такую функцию $f$, что выведенная оценка сверху оказывается совпадающей с плотностью решётки $\Lambda_8$, которая определяется как \begin{equation}\Lambda_8 = \left\{(x_i) ∈ \mathbb{Z}^8 \cup (\mathbb{Z}+1/2)^8 \bigg|\sum x_i = 0 (\mathrm{mod} 2)\right\}.\end{equation} Ясно, что это сделать ну очень непросто: те члены сумм в обеих частях равенства \eqref{eq:Poisson1}, которыми мы пренебрегали для получения неравенства, должны быть равны нулю чтобы позволить точное равенство. Кстати, уже из определения решётки $\Lambda_8$ видно, чем замечательно 8-мерное пространство. Расстояние между точками решетки $(0,0,0,0,0,0,0,0)$ и $(\frac12,\frac12,\frac12,\frac12,\frac12,\frac12,\frac12,\frac12)$ равно $\sqrt{2}$, как и расстояние между $(0,0,0,0,0,0,0,0)$ и $(1,1,0,0,0,0,0,0)$. Можно посчитать контактное число: \[240=4{8 \choose 2}+2+2{8 \choose 2}+{8\choose 4}\] Как построена требуемая функция напишу как-нибудь в другой раз.

Визуальное решение задач на построение

Для профилактики слабоумия начал опять решать задачи на Diofant.ru. Вчера вот такую задачу увидел

ЗАДАЧА 981 (Diofant.ru). Перпендикуляр к диаметру 'Дана окружность o и прямая линия l, которая проходит через ее центр. На окружности отмечена точка A, не лежащая на прямой. При помощи одной линейки без делений постройте перпендикуляр от точки к прямой.

Для решения таких задач я использую свой скрипт. Решить-то я решил, но поскольку задача проверяется в ручном режиме, надо было еще написать решение. Поэтому вчера я немного допилил скрипт (если кому-то интересно, смотреть как его подключить в коде) и теперь он худо-бедно документирует действия. Вот, можно попробовать решить вышеупомянутую задачу. Точки на пересечениях двух объектов ставятся их последовательным выделением (при включенном инструменте line).

---

Про числа и игры

Что-то стал за собою замечать, что совсем разучился в качестве отдыха и развлечения читать художественную литературу. Вместо этого читаю какие-нибудь книжки по математике, которые поинтереснее и, по возможности, попроще.

Вот, недавно стал читать книгу Конвея "О числах и играх". Много лет назад прочитал вот здесь про комбинаторную теорию в Го. В частности, прочитал про инфинитезимали, и это было круто. Сейчас решил перечитать, и нашел ссылку на Конвея. Вот цитата из первого параграфа:

 "Дедекинд (а до него автор — как считается, Евдокс — пятой книги Евклида) строил вещественные числа из рациональных. Его метод заключался в том, чтобы разделить рациональные числа на два множества L и R так, чтобы ни одно число из L не было больше никакого числа из R, и использовать это "сечение" для определения нового числа {L | R} в случае, если ни L и R не имеют экстремальной точки." 

Фактически, вот это самое дедекиндовское определение и берется далее за основу:

"Если L, R —  два множества чисел, и ни один элемент из L не  ⩾ любого элемента из R, то есть число {L | R}. Все числа строятся таким образом."

Отличие от дедекиндовского определения в том, что никаких чисел adhoc вводить не требуется. Конечно, еще нужно определить отношение ⩾ для таких чисел и операцию сложения (интересующимся смотреть книжку). Последняя позволяет отождествить определяемые числа с нормальными. Например, ноль выглядит как {∅ |∅}={|}. Вообще, одно и то же число можно представить разными способами, но это не страшно, с обыкновенными дробями тоже так.
Но, конечно, самое интересное начинается, если рассматривать пары {L|R}, в которых нет условий на элементы. Получаем определение комбинаторных игр на двоих:

"Если L, R —  два множества игр, то есть игра {L | R}. Все игры строятся таким образом."

Игры тоже можно складывать и вычитать. Числа в этом подходе — частный случай игр. А есть игры, числами не являющиеся, в частности, упомянутые инфинитезималы. Но про это как-нибудь в другой раз.

 Ну, и скрипт, конечно. Кстати, обнаружил, что поддерживается ползунок —   <input type="range" min="0" max="10"... />.

---

Двоичное число		результат
		-1.1

Разложение на простые дроби (профессиональное)

Сегодня вспомнил, общаясь с дочкой, как в школе учат раскладывать на простые дроби. Для правильных дробей с square-free знаменателями от одной переменной рецепт формулируется так. Записываем сумму простых дробей с неопределенными коэффициентами $A,\ B,\ C$: \begin{equation*}\frac{x^2-8x-3}{(x-{\color{red}1})(x-{\color{green}3})(x-{\color{blue}6})}=\frac{A}{x-{\color{red}1}}+\frac{B}{x-{\color{green}3}}+\frac{C}{x-{\color{blue}6}}\end{equation*} Затем приводим к общему знаменателю, собираем в числителе коэффициенты при разных степенях $x$ и получаем линейную систему на $A,\ B,\ C$: \begin{align*}
A+B+C&=1,\\-9 A-7 B-4 C&=-8,\\18 A+6 B+3 C&=-3.
\end{align*}Решая эту  систему, наконец, находим \begin{equation*}
\frac{x^2-8x-3}{(x-{\color{red}1})(x-{\color{green}3})(x-{\color{blue}6})}=-\frac{1}{x-{\color{red}1}}+\frac{3}{x-{\color{green}3}}-\frac{1}{x-{\color{blue}6}}
\end{equation*} И да, я, вроде, тоже так когда-то делал. Пока не знал ТФКП.
А теперь я делаю так:\begin{multline*}
\frac{x^2-8x-3}{(x-{\color{red}1})(x-{\color{green}3})(x-{\color{blue}6})}=\frac{{\color{red}1}^2-8\cdot{\color{red}1}-3}{(x-{\color{red}1})({\color{red}1}-{\color{green}3})({\color{red}1}-{\color{blue}6})}\\
+\frac{{\color{green}3}^2-8\cdot{\color{green}3}-3}{({\color{green}3}-{\color{red}1})(x-{\color{green}3})({\color{green}3}-{\color{blue}6})}
+\frac{{\color{blue}6}^2-8\cdot{\color{blue}6}-3}{({\color{blue}6}-{\color{red}1})({\color{blue}6}-{\color{green}3})(x-{\color{blue}6})}\\
 =-\frac{1}{x-{\color{red}1}}+\frac{3}{x-{\color{green}3}}-\frac{1}{x-{\color{blue}6}}
\end{multline*} Если в знаменателе есть степени, нужно, естественно, итерировать. Кстати, рецепт обобщается и на случай нескольких переменных. Научите ребенка — и он сможет при случае щегольнуть быстрым счетом в школе.

Про идеалы

Идеалов в реальном мире не бывает, но в математике они существуют еще как. Идеалы в  математике бывают разные, но здесь я расскажу про идеалы коммутативных колец.
Вообще, кольцо --- это множество, замкнутое относительно двух операций со свойствами сложения и умножения. Эти операции поэтому часто так и называют: сложение и умножение. Правда, коммутативность умножения не требуется, но нас интересует как раз кольцо с коммутативным умножением --- коммутативное кольцо. Ну еще хотят чтобы был нуль, и был противоположный элемент. Существование противоположного элемента позволяет определить в этом множестве и операцию вычитания по формуле $a-b\equiv a+(-b)$, где $-b$ --- элемент, противоположный $b$. Заметим, что существование единичного элемента и обратного элемента для ненулевого $a$ не требуется, и в этом принципиальное отличие кольца от поля.
Говоря неформально, в кольце деление даже на ненулевой элемент может быть невыполнимо. И, естественно, встает вопрос, а когда же деление все-таки выполнимо? Возьмем элемент кольца $a$ и спросим, какие элементы $b$ на него делятся, для каких $b$ разрешимо уравнение \begin{equation}b=ca.\label{eq1}\end{equation} Множество допустимых значений $b$ является примером идеала.

Возьмем самый простой пример коммутативного кольца — множество целых чисел $\mathbb{Z}$ с обычным сложением и умножением. Тогда, например, множество чисел, кратных числу $a$ является идеалом.

Можно расширить определение идеала так: пусть заданы несколько элементов кольца $a_1,\ldots,a_n$. Тогда идеал определим как множество значений $b$ (из кольца, конечно), для которых уравнение\begin{equation}b=c_1a_1+\ldots+c_na_n\label{eq2}\end{equation} разрешимо относительно $c_1,\ldots,c_n$ (в кольце, конечно). Про такие идеалы говорят, что они порождаются элементами $a_1,\ldots,a_n$. Для кольца целых чисел наше обобщение \eqref{eq2} не добавляет ничего нового. Чтобы это понять, заметим, что, во-первых, достаточно рассматривать идеалы, порожденные натуральными числами. Во-вторых, идеал, порожденный натуральными числами $a_1,\ldots,a_n$, совпадает с идеалом, порожденным  $\mathrm{GCD}(a_1,\ldots,a_n)$. Таким образом, в кольце целых чисел не только каждому натуральному числу соответствует идеал, но и наоборот, что открывает возможность переформулировать утверждения о натуральных числах в утверждения об идеалах. Вот, например, идеал, соответствующий простому числу (по понятным причинам называется простым идеалом), --- это собственный идеал (собственный $\equiv$ не совпадающий со всем кольцом), обладающий следующим свойством: для любого его элемента, имеющего вид произведения, по-крайней мере один из сомножителей также принадлежит идеалу. Теперь, когда у нас есть такое определение, мы можем его использовать для идеалов любых коммутативных колец, и, естественно, надеяться, что у этой и подобных конструкций есть простой смысл и большая польза.

Вот, например, рассмотрим полиномиальное кольцо ---  множество полиномов от $n$ переменных $x_1,\ldots,x_n$ с комплексными, скажем, коэффициентами. Полиномы, как и целые числа, можно складывать и умножать.  Обозначать это множество будем так: $\mathbb{C}[x_1,\ldots,x_n]$. В этом кольце наше обобщение \eqref{eq2} уже не сводится к \eqref{eq1}. Для кольца целых чисел каждый идеал у нас соответствовал натуральному числу, а для кольца полиномов идеалу можно придать гораздо более интересный смысл. А именно, идеалу, порожденному полиномами $p_1,\ldots,p_n$, сопоставим алгебраическое многообразие в $R^n$, заданное полиномиальными уравнениями \begin{align}p_1=0\nonumber\\\vdots\label{eq3}\\p_n=0\nonumber\end{align}Только вот это соответствие неоднозначное. В частности, если мы любой полином в системе \eqref{eq3} заменим на его степень, многообразие, очевидно не поменяется, а идеал, вообще говоря, поменяется. Чтобы соответствие было однозначным, нам нужно рассматривать не все идеалы, а то, что называется радикал-идеалы. Радикал-идеал $\mathcal{I}$ --- это идеал, для которого из условия $a^n\in \mathcal{I}$ следует $a\in \mathcal{I}$. Так вот соответствие между радикал-идеалами и алгебраическими многообразиями однозначно. Это означает, что, исследуя радикал-идеалы, можно исследовать алгебраические многообразия. Кстати, радикал-идеалы в кольце $\mathbb{Z}$ соответствуют натуральным числам, в разложении которых на простые нет степеней. Поэтому радикал-идеалы называются еще полупростыми. Очевидно, что простые идеалы являются также полупростыми, а обратное не всегда верно.

Пример приводимого многообразия,
заданного уравнением
$(x^2+y^2-4)(x^2-y)=0$

Чтобы понять, чему соответствуют простые идеалы, нам нужно ввести понятие неприводимых алгебраических многообразий. Неприводимые алгебраические многообразия ---  алгебраические многообразия, которые нельзя представить в виде объединения нескольких алгебраических многообразий. Так вот, неприводимые алгебраические многообразия играют роль простых чисел --- им соответствуют простые идеалы.

Красота идеальной математики на этом не кончается, но вот пост пора закруглять. Могу только порекомендовать для самообразования книжку Кокс, Литтл, О'Ши Идеалы, многообразия и алгоритмы. 

P.S. Все, можно статьи писать прямо в блоггере. Последний MathJax поддерживает нумерацию уравнений + ссылки через \ref и \eqref. Чтобы узнать как это включить, смотреть в коде поста скрипт с  src="...MathJax.js"

Для вертикальных

Под впечатлением книжки Штейнера.

Задача. На плоскости нарисован прямоугольник и треугольник. Найти с помощью одной линейки (без делений) центр тяжести треугольника.
Как и раньше, можно потренироваться прямо на рисунке: нажатие последовательно на две точки рисует прямую. Чтобы появилась точка пересечения двух прямых, нужно сначала нажать на одну, потом на другую. Чтобы нарисовать произвольную точку на прямой, нужно на нее кликнуть дважды. Когда появится точка, которую считаете центром тяжести, нажмите на нее, а затем на кнопку "Check".

---

---

Ну, раз уж все такие умные.

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

Задача. Найти с помощью одной линейки (без делений) центр тяжести фигуры, изображенной ниже.
Как и раньше, можно потренироваться прямо на рисунке: нажатие последовательно на две точки рисует прямую, появляющиеся точки пересечения тоже можно использовать для построения прямых. Когда появится точка, которую считаете центром тяжести, нажмите на нее, а затем на кнопку "Check".

---

---

P.S. Блин, написал же целый скрипт на такой случай, а кончил тупым копированием поста про прямоугольники и дорабатыванием напильником. Включил только автоматическое удаление линий после нахождения пересечения. Ничего нет более постоянного, чем временное.

Матроиды для чайников

Пишу, в основном, чтобы самому не забыть.
Чтобы определить матроид, определим сначала бинарную группу цепей. Бинарную группу можно наглядно определить так

Бинарная группа цепей --- множество, состоящее из N-значных двоичных чисел (не обязательно всех) и замкнутое относительно групповой операции --- побитного исключающего или. Единицей группы является $\underbrace{0\ldots 0}_{N\text{ нулей}}$ и каждый элемент является себе обратным.

В теоретико-множественном определении нужно заменить N-значные двоичные числа на подмножества N-элементного множества, а исключающее или --- на исключающее объединение $(\#1\backslash\#2)\cup(\#2\backslash\#1)$. Почему интересна такая конструкция, потому что эта группа играет важную роль в теории графов.
Пусть у нас есть граф с N ребрами. Возьмем часть его вершин в левую руку (множество этих вершин назовем $A$), а остальные --- в правую ($B$), растянем и порежем все ребра, идущие из одной руки в другую. Множество ребер, которые оказались разрезанными назовем разрезом. Все разрезы данного графа, как нетрудно сообразить, образуют некоторую бинарную группу цепей, которую мы будем обозначать $C$. Действительно, разрез, соответствующий исключающему объединению двух разрезов получается разбиением множества вершин на \[A^{\prime\prime}=(A\cap A^{\prime})\cup (B\cap B^{\prime})\quad\text{ и }\quad B^{\prime\prime}=(A\cap B^{\prime})\cup (B\cap A^{\prime}).\] Кстати, множество ребер, имеющих общую вершину тоже, очевидно, является разрезом (защипнем эту общую вершину и отрежем все ребра, соединяющие ее с остальным графом).
Есть другая бинарная группа цепей, связанная с множеством ребер графа. Рассмотрим все подграфы графа, для которых в каждой вершине сходится четное число ребер. Ясно, что множества ребер таких подграфов (собственно, цепи) образуют бинарную группу цепей $L$.
Заметим, что задание бинарной группы цепей (и, в частности, групп $C$ и $L$) полным перечислением ее элементов представляется довольно избыточным. Вообще, наиболее экономичный способ описания --- это задать мультипликативный базис группы. Понятие матроида бинарной группы цепей лежит где-то на полдороги между полным множеством элементов группы и ее мультипликативным базисом.
Перед тем, как давать формальное определение, поясним суть дела на примере наших групп $C$ и $L$. Рассмотрим сначала некоторый разрез. Может так оказаться, что после разреза в одной или обоих руках окажется несвязный граф (см. картинку). Такой разрез может быть выполнен в два приема и поэтому уж точно бесполезен для построения базиса. Можно сказать, что такой разрез неэлементарный.
Аналогично, многие цепи являются неэлементарными. Это так, если подграф, им соответствующий, несвязен или содержит вершины со степенью 4 или выше (см. пример справа). Вот если мы исключим из $C$ и $L$ (как множеств) неэлементарные элементы, а заодно и единицу группы --- пустое множество, оставшаяся часть и будет называться матроидом. Итак, на теоретико-групповом языке матроид бинарной группы цепей--- подмножество всех элементарных элементов группового множества, т.е., всех непустых элементов, которые не включают в себя никакого другого элемента в качестве подмножества. Для нашего чайниковского определения бинарной группы

Матроид бинарной группы цепей --- подмножество всех таких ненулевых чисел из группового множества, которые обязательно меняются при побитном ИЛИ с любым элементом группы.

Все, хватит пока. Про алгоритм Татта напишу как-нибудь в другой раз.
P.S. Кстати, картинки рисованы в SVG-edit, не выходя из браузера, а затем скопипасчены прямо в пост.

Выключи ХАЛа

Для меня лучший способ избавиться от идефикса -- воплотить в жизнь. На этот раз пришлось потратить два вечера, чтобы по мотивам клипа из Гришиного Г+ и задачи с Диофанта сваять скрипт под рабочим названием "Выключи ХАЛа". Сделать это можно, нажимая на кнопки и добившись, чтобы все стали темными. Проблема в том, что переключать можно только зеленые и черные кнопки и действовать максимум двумя руками (т.е., можно переключать за один ход кнопки не более, чем из двух рядов). ХАЛ, соответственно, сохранив остатки уважения к человеку, будет тоже переключать кнопки не более, чем в двух рядах, и доступны для него только красные и зеленые кнопки. Когда ход закончен, жмем Done. Пасовать можно только первый раз, а следующие пасы (или переключения, сохраняющие количества красных, зеленых и черных кнопок во всех рядах) приведут к пасам ХАЛа. Если зеленых кнопок не осталось, приходится нажимать на черные (а ХАЛу на красные).

---

>

N rows:
Nmax columns:

---

P.S. Блин, опять мой любимый FF притормаживает (хотя на локальной версии работал отлично). Круче всего эта страничка смотрится Chrome-ом.

Как убивать время.

Планировал вчера добить одну задачу, которую мы делаем с М. Как бы не так. Все утро было незаметно съедено хлопотами с ремонтом и добраться до работы удалось только к 11. На работе начали с обсуждения создавшейся ситуации на ФФ с тем же М., а затем и с подошедшим деканом Б.. В конце концов, я пошел к себе и только собрался заняться делом, как зашли вышеозначенные двое и сказали, что будут на мне ставить опыт. Опыт оказался задачей на построение линейкой, которую нужно было решить за пять минут. Задачу за пять минут мне решить не удалось, т.к. пришел Ч. и предложил другую задачу, которая ему зачем-то нужна была для работы. В конце концов, задачу Б. я решил. Задачу Ч. мы тоже решили с М., но тут наступило время идти встречать подъехавшую плитку и машину для вывоза строительного мусора. Приехал домой и сразу в магазин выбирать мебель и другое для новой квартиры. Час перед сном писал скрипт и этот пост. Так весь день и прошел. Приведу в своей редакции две задачи, которые решал.

Задача 1.(Б.) Найти с помощью одной линейки (без делений) центр тяжести фигуры, состоящей из двух прямоугольников, жестко скрепленных углами (см. рисунок ниже). Можно потренироваться прямо на рисунке: нажатие последовательно на две точки рисует прямую, появляющиеся точки пересечения тоже можно использовать для построения прямых. Когда появится точка, которую считаете центром тяжести, нажмите на нее, а затем на кнопку "Check".

---

---

Задача 2.(Ч.) Пусть $h\ $ --- матрица, так что $h^\dagger h \ $ не имеет нулевых с.з. Пусть теперь $H=h+x\ $, где $x\ $ --- инфинитезимальная матрица. Найти разложение матрицы $\sqrt{H^\dagger H}\ $ по $x\ $ до второго порядка. Под $\sqrt{h^\dagger h}\ $ понимается положительно определенная матрица, а под $\sqrt{H^\dagger H}\ $ --- матрица, близкая к $\sqrt{h^\dagger h}$.

Ступор

Есть у меня такое свойство: когда нужно делать много дел сразу, не делаю ни одного. Вот и сейчас, дел куча: на одну статью пришла рецензия с замечаниями, соавтор прислал драфт новой статьи, нужно вписать свой кусок в отчет по гранту и идти в банк за кредитом. А я что? Сижу и решаю задачки на Диофант.ру. Началось все с того, что утром, проснувшись раньше будильника, я вспомнил задачку, которую в девятом классе не решил на союзной олимпиаде, и решил в уме пока ждал звонка будильника. Странно, неужели я тогда такой глупый был? Или мне по-тупому времени не хватило, не помню. Задача такая:

Есть гора, нарисованная на плоскости. Два альпиниста находятся у подножия с разных сторон и начинают двигаться так, чтобы всегда находиться на одной высоте друг с другом. Задача каждого --- перебраться на другую сторону. Нужно доказать, что это возможно при любой форме горы (пиков может быть несколько, но любая точка горы, конечно, находится выше подножия, на то она и гора).

PS В качестве иллюстрации см. счетчик в правой панели.

Созвучие

Читая последний выпуск ТрВ открыл для себя сайт "Математические этюды" для школьников. За этот сайт (ну и за другие инициативы в области популяризации математики) Николай Андреев, зав. соответствующей лаборатории в стекловском институте, получил большую президентскую премию. Прикольные анимации незаметно съели 2 часа вечернего времени. Жалко только, что они без звука. Узнал попутно, что мой пост под дурацким названием "Продолжая тему" следовало назвать "Задача Томсона". Да, кстати, странно, что для $n=5$ не доказана оптимальность.

Средняя температура по больнице

Вчера в блоге Константина Кнопа неожиданно бурное обсуждение вызвала следующая задача:

Шаровое звездное скопление состоит из 30 тыс. звезд и имеет радиус 30 световых лет. Найти среднее расстояние между звездами этого скопления.

Обсуждалась не задача, конечно, а то, насколько она по зубам школьникам 6-7 классов. Равномерное распределение звезд, насколько я понял, в задаче подразумевалось. Вопрос в том, как понимать среднее расстояние. Если это действительно среднее по всем парам звезд расстояние, то среднее расстояние вычисляется как интеграл\[(4\pi R^3/3)^{-2}\int d\mathbf{r}_1 d\mathbf{r}_2 |\mathbf{r}_1-\mathbf{r}_2|=18R/25,\]если нигде не ошибся. Такая задача, конечно, сложна для школьников.
С другой стороны, как заметила физическая часть аудитории, спрашивалось скорее среднее расстояние между парами соседних звезд. Решение, которое предлагалось - кубический корень из объема, приходящегося в среднем на одну звезду,т.е., $\sqrt[3]{4\pi R^3/3N}$, и это, конечно, вполне по силам семикласснику.Такая оценка среднего расстояния действительно встречается в физических рассуждениях на каждом шагу. По порядку величины, конечно, это правильный ответ. Вопрос, поймет ли школьник, что именно это от него требуется.
В ходе обсуждения обнаружил, что для астрофизиков "примерно" и "по порядку величины" - понятия по порядку величины примерно одинаковые.
Ну, и, ради любви к искусству, посчитаем, насколько это действительно так\[\langle r\rangle=\int d(N r^3/R^3)r\exp(-N r^3/R^3)=\Gamma[4/3]\sqrt[3]{R^3/N},\]т.е., в этом случае, ответ меньше оценки примерно в 1.8 раз.

О вреде азартных игр

Все знают игру "Орел или Решка". Это когда один бросает монетку, а другой угадывает. Мы в эту игру в теор. отделе с Ваней иногда играем. Выигравший спокойно допивает чай, а проигравший бежит по мелкому, но срочному делу, например бумажки за двоих подписывать. Все честно, теория вероятности учит, что в среднем будешь проигрывать столько же, сколько выигрывать. Но это только если действительно бросаешь монетку. А если просто задумываешь число, то может быть и не так. Не каждый ведь может датчиком случайных чисел работать. Человек склонен придерживаться какого-то рецепта даже в таком деле. Какой бы этот рецепт ни был, его можно использовать в свою выгоду.Вот только как?
Ниже скрипт, который делает выводы из предшествующей игры и пытается увеличить вероятность своего выигрыша. Объясню как им пользоваться. Нужно загадать Tails или Heads и дальше нажать на кнопку Guess. Алгоритм покажет свою догадку и нужно сказать ему, угадал он или нет, нажав на одну из появившихся кнопок (только честно). И так много раз. Во втором поле показываются число побед компьютера,ваших побед и ваш выигрыш, а если число с минусом --- то проигрыш. Конечно, чтобы выигрыш компьютера стал заметен на фоне статистического шума, придется, наверное, долго монетку бросать. Следующие два поля и кнопка призваны облегчить задачу. Только если ими пользоваться, вам придется мне поверить, что компьютер сначала выдает догадку, а потом бросает монету, не подглядывает. В первом поле нужно указать паттерн, а во втором --- количество его повторений. Потом нажать на кнопку Iterate. Формат паттерна такой: h-heads,t-tails, ?-честно кинуть монетку, *- кинуть или не кинуть монетку (т.е., звездочка позволяет избежать периодичности). Например, если паттерн ht*, а число итераций 2, то реальная последовательность бросаний при нажатии на Iterate может быть одной из девяти: hthhth,hthhtt,hthht,htthth,htthtt,httht,hthth,hthtt,htht.
Короче, Enjoy. Только не надо сильно много повторений заказывать, а то зависнет браузер.

---

---

P.S. Кстати, можно устраивать бойни между скриптами, так что если кто-нибудь напишет свой скрипт, можно его с моим стравить. Ну, чтобы было понятно, всегда есть нейтральная стратегия: честно бросать монетку. Тогда в среднем никто в проигрыше не останется, так что датчик случайных чисел не предлагать. Исход каждого раунда, естественно, будет передаваться и вашему скрипту. Играть понятно как: оба выкладывают монеты и один выигрывает при совпадении, а другой при несовпадении.
P.P.S. Да, и еще, чтобы не забыть, минизадача: понять закономерность в последовательности
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,...

Продолжая тему (Задача Томсона)

Остановиться на достигнутом не удалось. Во-первых, сразу стало интересно, сколько существует правильных многогранников в четырехмерии и в n-мерии. Интуитивно почему-то казалось, что чем больше размерность, тем больше правильных многогранников. Подключение к всемирному разуму показало, что жестоко ошибался. После просмотра изумительной красоты картинок, естественно, захотелось завращать все и вся, тем более, что всего-то и надо было научиться правильно определять вершины. Но тут я застрял. Поскольку мыслительного процесса хватает на работе, решил схитрить и решить задачу по-физически, а именно, посадить нужное число точек на сферу и организовать между ними отталкивание. Идея была такая, что эта конфигурация сама устаканится в правильный многогранник. Наивный... Долго ждал, но так и не дождался... Потом решил хоть в трехмерии метод опробовать. Бросил 8 точек и понял, что вовсе не куб получился. Родилась задача: Восемь одинаковых точечных зарядов находятся на сфере. Найти минимум кулоновской энергии.

---

---

P.S. Чтобы система устаканивалась, нужно, конечно, не ускорение, а скорость приравнивать силе. В принципе, это тоже довольно физично: частицы плавают в жидкости.