4290
Рассказы про разную математику. Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/
https://mccme.ru/nir/seminar/
в четверг (19.10) на семинаре учителей математики Наталья Нетрусова будет рассказывать про семейный турнир головоломок в Тбилиси, Иван Яковлев — про телеграм-канал «Кроссворд Тьюринга»
19:00Msk, zoom, подробности на сайте
Если вдруг меня читает кто-то из Америки — помните, что у вас сегодня (вот прямо буквально через пару часов) кольцевое солнечное затмение:
https://www.timeanddate.com/eclipse/solar/2023-october-14
Скажем, если вы в Лос-Анджелесе — кольцевое, конечно, не покажут, но Луна закроет довольно заметную часть Солнца. Так что стандартная техника камеры-обскуры, «сделать несколько дырочек в листе бумаги/картона и смотреть на отбрасываемую им тень», вполне покажет сильно покусанные полумесяцы.
(Images credit: https://www.timeanddate.com/ )
И напоминаю: на Солнце нельзя!! смотреть без защиты! И даже солнечных очков недостаточно: они тоже на взгляд прямо на Солнце не рассчитаны!!
Из двух чисел, отличающихся только старшим битом (a_4) двоичной записи, на каждой карточке присутствует ровно одно. Так что, когда мы голосованием выяснили четыре младших бита и нашли соответствующее число — смотрим, на каких карточках оно встречается. Если видим, что плюс-минус на тех же, которые указал отгадывающий (отклонение не больше разрешённого количества неверных ответов), то мы угадали. Если практически «всё наоборот», то нужно прибавить 16. А если ни то, ни то, то вообще-то так быть не должно, так что фокуснику нужно перепроверить себя.
Несколько сложно, да — но получается очень устойчивый код. И почти такой же код — только R(1,5), а не R(1,4), то есть код типа [32,6,16] — реально применялся в космосе для связи с Маринером-9!
Если у линейной функции по модулю 2 коэффициент при каком-то x_i равен 0, то на каждом ребре гиперкуба этого направления значения совпадают; а если 1, то различаются.
Соответственно, так можно узнать последние 4 бита двоичной записи. Для каждого из направлений смотрим на все 8 рёбер (пар ответов) этого направления. Берём те из них, где известны оба ответа (выкидываем, если один из результатов неизвестен). У оставшихся проводим голосование простым большинством: если больше различающихся, то соответствующий бит равен 1, если больше одинаковых, то 0. И записываем этот результат (например: если различаются, то кладём монетку в соответствующий квадратик сверху).
На примере выше — ответы без вранья и без отказа от ответов. Видно, что на всех парах рёбер « направления 1 » значения различаются, а на всех парах рёбер « направления 2 » они совпадают. Значит, бит единиц равен 1, а бит двоек равен 0.
Ну и последний сюжет. Код Адамара — он же код Рида-Мюллера RM(1,4).
Это код типа [16,5,8] — то есть в 16 битах сообщения мы передаём 5 бит информации, а кодовое расстояние равно 8.
Соответственно — загадывающему можно разрешить соврать 3 раза, или 2 раза соврать, а ещё про 3 карточки отказаться отвечать. И всё равно можно будет угадать загаданное число!
На этот раз карточки нужно не разрезать, а оставить одним большим квадратом 4x4. И запастись 20 «жетончиками» (монетками, или ещё чем-нибудь) — чтобы зафиксировать ответы и вести промежуточные вычисления. Можно, конечно, и ручкой отмечать, но тогда карточки одноразовыми будут, а это жалко.
Начало обычное — фокусник спрашивает, на каких из 16 « карточек » (квадратов 4x4) присутствует загаданное число. И загадывающий или фокусник как-то это отмечают: скажем, раскладывают монетки на те квадраты, где ответ « да » (и пустые бумажки на те, где загадывающий промолчал).
А вот дальше — интересное.
Опять же, можно показывать фокус в двух вариантах:
(а) загадывающий может соврать один или два раза. Если он соврал один раз — фокусник угадывает, если два — просто говорит «не верю».
(б) загадывающий может соврать один раз, и дополнительно — про одну карточку может отказаться отвечать.
Для случая (а) — опять же, раскладываем карточки в зависимости от ответов на две кучки, берём ту, которая меньше (считать проще), и считаем XOR синих кодов (уже четырёхбитовых).
- Если получилось 0000 — загадывающий не соврал ни одного раза (для контроля: так бывает только если ответов «да» — 0, 4 или 8; причём не все наборы с 4 «да» подойдут).
- Если получился код с одной или тремя единицами — это код той карточки, где он соврал; находим её и (комментируя) перекладываем в другую стопку.
- Если получилось что-то ещё — загадывающий соврал два раза, говорим «не верю»
А имея правильные ответы — первые 4 карточки это двоичная запись, так что складываем красные числа (первые на карточках с тремя единицами в коде), попавшие в стопку «да».
Вот тут Ксавье Карузо реализовал это в виде Java-апплета, угадывающего смайлик по семи ответам на вопросы (я перевёл по строчкам) :
- Ваш смайлик жёлтый? - У него есть галстук-бабочка?
- Он носит очки? - Он показывает язык?
- Он носит шляпу? - Его руки видны?
- Есть ли у него усы?
Третий набор более интересный. Число опять от 1 до 15 (на самом деле, от 0 до 15), и 7 карточек. В этот раз загадывающий может (но не обязан) один раз соврать — а фокусник всё равно число должен отгадать!
Математика — эти карточки реализуют код Хэмминга [7,4,3], позволяющий исправлять одну ошибку при передаче 4-битового сообщения в 7 битах.
Второй набор (тут — для чисел от 1 до 15 или для чисел от 1 до 31) можно применять двумя разными способами:
а) загадывающего фокусник опять спрашивает про каждую из карточек, есть ли на ней загаданное число — но про любую одну из них загадывающий может отказаться отвечать.
б) отвечая, загадывающий имеет право один раз (но не больше) соврать. Но фокусник, в свою очередь, угадывает число, если все ответы были честными, а если отгадывающий соврал, то фокусник просто говорит «не верю».
Ответ на загадку: это посох Якова, древний прибор для измерения углов — в частности, для измерения высоты звёзд над горизонтом. Только тут на нём сразу все поперечные палочки надеты.
Так и представляется картина — становится человек на качающуюся палубу, и двигает поперечную палочку, пока не найдёт расстояние, на котором один конец указывает на звезду, другой на горизонт, причём вертикально: если чуть-чуть дальше, то уже не достанет, как ни крути. Сам посох при этом будет направлен по биссектрисе; желательно при этом также не выбить себе глаз.
После этого угол находится: если палочка длиной 2a, а зафиксировали мы её на расстоянии h, то
tg(\alpha/2) = a/h,
так что
\alpha = 2 arctg (a/h).
(image credit: Fantagu & Majo statt Senf, Wikipedia)
докажите, что любое число, представимое в виде A²+AB+B² представимо и в виде C²-CD+D² (все числа целые неотрицательные)
(задача со вчерашней олимпиады учителей)
предлагается придумать три разных решения: элементарная алгебра, классическая планиметрия, детские картинки по клеточкам
https://youtu.be/tC3oz6sFdic?t=647
В.А.Зорич на заседании МатОбщества в честь его 80-летия
Владимир Антонович Зорич (16.12.1937–14.08.2023)
Анна Николаевна Андреева (12.01.1941–27.07.2023)
https://youtu.be/zm6so51Xka8
/channel/EtudesRu/112
Трансляция началась — https://www.youtube.com/watch?v=y2JB_l8-8Ho
Читать полностью…
https://arxiv.org/abs/2307.01912 (Doron Zeilberger et al.)
«In this case study, we hope to show why Sheldon Axler was not just wrong, but wrong, when he urged, in 1995: ”Down with Determinants!”. We first recall how determinants are useful in enumerative combinatorics, and then illustrate three versatile tools (Dodgson's condensation, the holonomic ansatz and constant term evaluations) to operate in tandem to prove a certain intriguing determinantal formula conjectured by the first author. (…)»
P.S. Про наблюдение — скопирую из поста 2021 года:
==
Оптимальный способ наблюдения — делается дырочка (или несколько) в листе картона или плотной бумаги, и смотрится на тень от этого листа:
https://www.timeanddate.com/eclipse/make-pinhole-projector.html
Плюс такого наблюдения — безопасность: при таком наблюдении нет нужды смотреть даже вообще в сторону Солнца.
(Вот тут фотография тени дерева — где таких просветов в листве оказалось много: http://www.astronet.ru/db/msg/1162946 )
в 2005 году на ММО предлагалось разрезать круг на равные части так, чтобы центр не лежал на границе хотя бы одной из них (С.Маркелов)
на картинке — решение 1502 года от Дионисия и мастерской (via Н.Андреев)
¹ №35 на http://www.dionisy.com/museum/447/
В «направлении 4» значения пар опять совпадают, а в «направлении 8» — все отличаются. Значит, бит четвёрок равен 0, а бит восьмёрок — 1. Итого, наше число это *1001, то есть либо это 9, либо это 16+9.
Читать полностью…
Давайте для начала посмотрим, как устроен сам этот код. Загадано число от 0 до 31 — то есть его 5 бит двоичной записи,
a_4 a_3 a_2 a_1 a_0.
Сопоставим нашим карточкам 16 вершин 4-мерного булевского куба {0,1}^4. И превратим наши 5 бит в 5 коэффициентов аффинной (линейной неоднородной) функции на этом кубе:
L (x_0,x_1,x_2,x_3) = a_0 x_0 + a_1 x_1 + a_2 x_2 + a_3 x_3 + a_4.
Её 16 значений во всех вершинах — это и есть наш код.
И то, что кодовое расстояние равно 8, проверяется мгновенно: ведь ненулевая аффинная функция на булевском гиперкубе ненулевая по меньшей мере в половине его вершин (или во всех, если она константа).
Правда, изящно?
Осталось научиться восстанавливать исходное число!
Для случая (б) — откладываем карточку C, про которую мы не знаем ответа, в сторону, и смотрим XOR в какой-нибудь (меньшей по размеру) из кучек К.
- Если получилось 0000 — нам не соврали, а C нужно положить в другую кучку K’.
- Если получился код C — нам не соврали, а C нужно положить в ту же кучку K.
- Если ни то, ни другое, но в сумме одна или три единицы, то нам соврали, и эта сумма это код соответствующей карточки. Перекладываем её из одной кучки в другую, и кладём С в K’.
- И наконец, иначе добавляем ещё и код C; должен получиться код карточки, которую нужно переложить из одной кучки в другую. А карточку C кладём в K.
Всё, враньё поймали, разложили ответы правильно, и опять складываем красные числа в стопке «да».
Теперь можно скрестить код Хэмминга с идеей бита контроля чётности: раньше, честные ответы для любых двух чисел отличались минимум в трёх местах. Именно поэтому мы в принципе могли исправить один ошибочный ответ: если бы нашлись числа, для которых честные ответы отличаются только на двух карточках (А и Б), то получив ответ «на полпути», мы не смогли бы сказать, это первое число, и нам соврали на карточке А, или второе, а нам соврали на карточке Б.
Так вот — давайте добавим восьмую карточку, сумму первых семи ответов по модулю 2 («нечётное ли число ответов «да» среди первых семи?»). Тогда при честных ответах число ответов «да» всегда будет чётным. Поэтому любые два набора честных ответов отличаются в чётном числе мест — так что наименьшее возможное число отличий увеличивается с 3 до 4. И это — пополненный ход Хэмминга [8,4,4]: в серии из 8 бит передаются 4 бита информации, а любые два правильных набора отличаются минимум в 4 местах.
И алгоритм для фокусника такой:
- раскладывать карточки на две стопки в зависимости от ответа, «да» или «нет»
- взять ту стопку, которая меньше (можно любую, но так проще)
- сложить побитово (XOR) трёхбитовые коды (синие, мелким шрифтом внизу) карточек. На самом деле — это применение к коду проверочной матрицы.
- - если получилось 000, то загадывающий не соврал (и можно похвалить!).
- - если получилась какая-то другая строчка, то это и есть код карточки, на которой загадывающий соврал. Находим её, перекладываем её в другую стопку (комментируя, что-де вот в этот ответ не верится!).
- теперь все ответы про карточки правильные
- и задача сведена к первой: первые четыре карточки это обычное двоичное кодирование. Чтобы их выделить, можно или складывать, красные числа в стопке «да», или — если цвет не виден — выделить те карточки, у которых по меньшей мере две единицы в коде.
Готово!
Опять же, фокус достаточно простой — к двоичному кодированию добавили бит контроля чётности, сумму цифр двоичной записи по модулю 2, и именно его и «спрашивает» последняя карточка.
Соответственно, в варианте а) фокусник смотрит, сколько он уже получил ответов «да», и если их нечётное число, то в карточке, про которую загадывающий отказался отвечать, ответ «да», а если чётное, то «нет». Восстанавливаем ответ на этой карточке (разумеется, проговаривая, «а вот туут ответ должен быть…»), и задача сведена к предыдущей.
А в варианте б) ещё проще — смотрим, сколько карточек в куче «да». Если нечётное число, то говорим «не верю», если чётное, то применяем навыки предыдущего фокуса (главное — не забыть, что бит контроля чётности в двоичную запись не входит; чтобы не путать — степени двойки, которые надо складывать, выделены красным, а на последней карточке красного нет).
Давайте я выложу сюда один сюжет — фокусы с карточками с угадыванием числа. Которые можно показывать — а потом обсуждать с детьми, что происходит.
Набор первый: загадайте число от 1 до 15 (или от 1 до 31, например, день рождения). Дальше фокусник задаёт 4 (или 5) одинаковых вопросов: есть ли это число на данной карточке. И более-менее мгновенно это число называет.
Понятно, как это устроено математически — карточки это вопросы о цифрах двоичной записи. А инструкция фокуснику — показывая карточки, сразу раскладывать их в две стопки, те, где ответы « да » и где ответы «нет». После чего сложить на тех карточках, что в стопке «да», первые числа — это как раз и есть соответствующие степени двойки (ибо первое число, у которого есть единица в разряде «2^n» в двоичной записи, это и есть это самое 2^n). И понятно, что это делается очень быстро.
(Кстати — в Квантике в 2012 году был «Супергалактический определитель возраста» — см. с. 5; а на Мат. Этюдах есть рассказ с набором для распечатки для чисел от 1 до 100)
На кофейном столике Женевского университета нашел прикольную книгу: Do not erase. Сделана она так. На каждом развороте коротенькое интервью с математиком (почти все американские, кажется) слева, а справа — доска. Доски красивые, фото прикладываю.
UPD: в комментах книгу выложили целиком.
Фотография из музея (с убранной подписью). Как вы думете, что это?
Читать полностью…
https://old.kvantik.com/art/files/pdf/2023-01.12-14.pdf
https://old.kvantik.com/art/files/pdf/2023-02.19-23.pdf
Гаянэ Панина. Про Лёлю и Миньку, а также про лемму Шпернера и два её доказательства – одно сказочное, а другое резиновое (Квантик №№1-2 за 2023 год)
Трансляция лекции Д. В. Орлова про гипотезу Бёрча—Свинертона-Дайера:
https://www.youtube.com/watch?v=rCdOtybBAK0
https://www.youtube.com/live/rSgg_OWlYRA
https://mccme.ru/dubna/2023/raspis.htm
утром в среду Г.Ю.Панина будет рассказывать на ЛШСМ-2023 (и планируется прямая трансляция) про гипотезу Банаха
«Гипотеза звучит так:
Пусть K — n-мерное центрально-симметричное выпуклое тело. Для некоторого 1<k<n известно, что любые два сечения тела K k–мерными плоскостями, содержащими центр симметрии, линейно эквивалентны. Тогда K — эллипсоид.
Эта гипотеза сформулирована в 1932 году польским математиком Стефаном Банахом, и до сих пор не решена полностью. Мы посмотрим на методы, работающие в разных стучаях: несложная топология (теорема о причесывании ежа), теорема Дворецкого, проективная геометрия. В конце мы упомянем последний результат петербургских математиков: Sergei Ivanov, Daniil Mamaev, Anya Nordskova «Banach’s isometric subspace problem in dimension four» Invent. math. (2023).
В качестве подготовки предлагается подумать над следующими задачами:
1. Пусть у трёхмерного центрально-симметричного тела K все центральные двумерные сечения (то есть, сечения, содержащие центр симметрии) — эллипсы. Тогда тело K — эллипсоид.
2. Пусть у трёхмерного центрально-симметричного тела K все центральные двумерные сечения конгруэнтны, то есть отличаются поворотом пространства. Тогда тело K — шар.»
4-я задача, кажется, довольно простая — и, главное, решается « естественным образом ». (Disclaimer : я не смотрел написанные решения, так что не исключено, что в тексте ниже есть какой-то мой глюк. Но на вид вроде всё работает…)
Если бы не было условия различности x_i, то наименьшее значение у произведения под корнем было бы при всех x_i=1, равнялось бы n^2, и это даёт оценку a_n >= n. (Впрочем, требование, что все a_n целые, тоже это гарантирует — просто за счёт того, что a_{n+1}>a_n.)
Но из условия явно видно, что требуется в полтора раза больше.
Дальше — очень естественно, что поскольку x_i>0 просто вещественные числа, про них больше ничего не , когда x_1,…,x_{k-1} квадратный корень можно « подкручивать вверх », меняя x_k от того значения, когда произведение наименьшее, к 0 или к бесконечности. И тогда получающееся значение a_k « пробежит » все возможные значения от наименьшего возможного до бесконечности.
Значит, нужно посмотреть, какое именно это наименьшее значение.
Если мы уже знаем a_{k-1}, то под корнем у нас произведение двух сомножителей, которые нам дальше важны только сами по себе: мы к ним будем добавлять новые слагаемые, но не разбивать их на составляющие. Поэтому пусть эти скобки равны aS и a/S, где a:=a_{k-1}.
Следующее произведение это
(aS+x)(a/S + 1/x) = a^2+ a (S/x + x/S) +1,
где x=x_k
В скобках не меньше 2, поэтому само произведение не меньше (a+1)^2.
А минимальное значение тут такое, когда x=S. (И тогда новое S’ будет тем же самым S).
Поэтому никакие два последовательных увеличения a_{k+1}-a_k не могут оказаться равны 1 (потому что тогда два последовательных x_k совпадали бы). То есть каждое второе увеличение — хотя бы 2.
И вот и получаем ту самую оценку с коэффициентом (3/2).
