fp math – Telegram
fp math
1.61K subscribers
14 photos
1 file
22 links
Math chat by Fedya Petrov
Download Telegram
решение про волейбол (статистику сами видите, честно говоря, я ожидал другого)

В варианте (b) можно считать, что пифагорейцы подают 100 раз, а вольтерьянцы 99 раз (если матч закончился раньше, пусть всё равно доподают). В варианте (а) пифагорейцы к окончанию матча подали не больше чем 100 раз (поскольку когда они подают 101-й раз, это значит, что они уже набрали 100 очков), аналогично, вольтерьянцы - не более 99 раз. Так что пусть они играют после того, как одна из команд набрала 100 очков, до тех пор, пока пифагорейцы не подадут 100 раз, а вольтерьянцы 99, и мы включим в список розыгрышей, по которым подводится итог, ровно упомянутые 100+99=199 розыгрышей.

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


(задачу подглядел в фб)
👍16😱3
Теперь комментарии как во всех нормальных группах, а не с этим ботом! А старые посты уже не перевести в этот режим?
2113🎉6🤯4🖕3👍11
Всегда любил каплинги (они же спаривающие меры, они же многозначные отображения, они же полиморфизмы, они же планы перевозок и пр.) Идея в том, что для сравнения вероятностей двух событий надо умно реализовать их на одном вероятностном пространстве. Простой пример: красим каждую грань многогранника с вероятностью 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, и это имеет ту же вероятность.
👍1914🔥22💋1🖕1🆒11
Дал я Маше и Олегу
жеребёнка да телегу,
чтобы для обеда
пригнали правоведа.
Адвокат невнятный:
суп не ест томатный,
пьёт настой на шишках,
взял под чай коврижку.
Вам не надоело?
Продолжаю смело

(но дальше не продолжить, потому что там 0)

Сочинил десять лет назад, сейчас, поди, роботы лучше справляются.
28🔥19🤮1
Чего-то никого не заинтересовала мнемоническая тематика а я надеялся, что накидаете в комментарии — наверное, у всех и так хорошая память. А у меня очень плохая память. Перечитывал свою не такую уж старую работу, там написано: я умею доказывать то-то так-то. Три дня пытался восстановить — выходит либо не то, либо не так.
😢30118😁3🤮1111
Сегодня Илон Маск выдал премиум-пользователям телеги доступ к нейросети Грок. Работает через пень-колоду, но когда сподобится ответить, это прям свежо.
😁951714136🔥43👍21🖕1
Прочитал на MO интересное доказательство того, что R³ не является квадратом топологического пространства.

На пространстве R³×R³ гомеоморфизм f:(x, y) →(y, x) не является композиционным квадратом никакого гомеоморфизма — потому что меняет ориентацию. С другой стороны, для пространства вида Y=X×X гомеоморфизм f:(x, y) →(y, x) на Y×Y является квадратом: если обозначить x=(a, b), y=(c, d) для a, b, c, d из X, то f есть квадрат отображения (a, b, c, d) → (b, c, d, a).
🔥48👍124
На Всеросе была предложена такая задача (автор Ю. А. Хромин):

куб составлен из n³ единичных кубиков. В них надо написать числа 0,1 так, чтобы сумма восьми чисел в любом кубе со стороной 2 была не больше 4, и при таких ограничениях общая сумма была максимально возможной.

Задача решается, например, по индукции (так почти все участники, решившие задачу, и делали).

Но Артур Абзалилов из Казани предложил гораздо более интересный подход, который позволяет решить любую задачу такого рода, навроде:

в кубиках параллелепипеда 1000×2000×3000 расставляются числа 0,1, 2, 3. Расстановка допустимая, если сумма 343 чисел в любом кубе со стороной 7 не больше 800. Найдите наибольшую сумму чисел в допустимой расстановке.

Далее подход Артура объясняется на этом примере.


Давайте сделаем произвольную допустимую расстановку X 7-периодичной в данном направлении (по вертикали, скажем) — сохраняя допустимость и не уменьшая сумму чисел. Разобьём всё на двумерные горизонтальные слои и выберем 7 подряд идущих слоёв с наибольшей суммой. Пусть общая сумма в выбранных слоях это s. Рассмотрим расстановку Y, которая в выбранных 7 слоях совпадает с X, но 7-периодична по вертикали. Ясно, что она тоже допустима. Докажем, что сумма чисел в Y не меньше, чем в X. Достаточно доказать это отдельно для слоёв ниже выбранных и выше выбранных. Слои ниже выбранных разобьём на семёрки, начиная с нижнего, верхняя семёрка будет, возможно, пересекаться с выбранными слоями. В каждой семёрке сумма в X не больше, чем s, а в Y — ровно s. Значит, сумма в Y ниже выбранных слоёв не больше, чем в X (сумма в части выбранных слоёв сократилась: они одинаковы в X и в Y). То же сверху от выбранных.

Теперь делаем то же последовательно в двух других направлениях и получаем допустимую расстановку с суммой не меньше чем в исходной, но 7-периодическую по каждой переменной.

Среди таких расстановок найти ту, где сумма наибольшая, несложно: надо раскрасить кубики в 343 цвета в зависимости от остатков координат при делении на 7, в 266 самых популярных цветах расставить тройки, в следующем по популярности цвете расставить 2, в остальных кубиках нули. Получается 14013662520, если я не обсчитался.
🔥34👍54🍓3
немного рекламы

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

Call for Postdocs 2025

The Leonhard Euler International Mathematical Institute in St. Petersburg is seeking postdocs in all areas of Mathematics, Theoretical Computer Science, Mathematical and Theoretical Physics.

Applicants should send their applications to apply@eimi.ru

The applications should include:
CV,
List of publications (including preprints, if necessary),
Denoscription of research interests, ideally mentioning possible host or other research contacts in St. Petersburg,
Names, affiliations and contacts of 2-3 people willing to send recommendation letters if asked by the committee,
Any special requirements wrt the dates, etc.

Basic conditions:
Competitive salary starting at 160,000 RUB per month (taxed at 13% for residents and foreigners), which is more than enough for comfort living in St. Petersburg,
The institute partially covers travelling expenses to St. Petersburg of up to 600 Euro,
The institute has some funds for covering participation in conferences that cannot be covered from other sources,
1 or 2 years extendable for another year,
Teaching load is set at 4 academic hours per week,
Flexibility with respect to the starting date, length, specific calendar requirements (such as a leave in the middle).
The Call will remain active throughout the whole year. Preferable starting date is September 1, 2025, earlier or later dates will also be considered.

If you have questions, please do not hesitate to ask them by email.

https://eimi.ru/calls/5883/

2. Позиция постдоков по комбе и около у наших друзей из МФТИ, в целом похоже по условиям

Конкурс академической мобильности: ФПМИ МФТИ предлагает позиции научных сотрудников (постдоков) для молодых исследователей со степенью кандидатов наук!

Конкурс подразумевает трудоустройство на 2 года в одну из лабораторий ФПМИ, например:
- Лабораторию комбинаторных и геометрических структур (CombGeo)
- Лабораторию дискретной и комбинаторной оптимизации

Условия:
- молодой ученый со степенью кандидата наук (до 35 лет) или PhD (до 40 лет)
- не менее трех публикаций за последние 5 лет в рецензируемых журналах, желательно первого и второго квартиля (Q1 и Q2)
- профиль: комбинаторика, геометрия и топология, геометрическая теория групп, дискретная вероятность, а также смежные вопросы теоретической информатики
- готовность взять небольшую преподавательскую нагрузку (1-2 занятия в неделю)

Вознаграждение:
Зарплата состоит из базовой ставки от МФТИ (100к-200к в зависимости от опыта кандидата) + доплата от лаборатории (по результатам собеседования) + доплата за преподавание

Также в случае необходимости предоставляется проживание на кампусе МФТИ в Долгопрудном.

В случае заинтересованности направьте резюме Анастасии: @thesekunda
Дедлайн: 28 мая
72💯111165👎4🔥32👍1🤨1
кто ставит такую реакцию к постам, это вы минусуете?(((
240😁57🤯4🍌21🔥1💋1
Пусть a₁ < ... < aₖ — целые неотрицательные числа, t₁, ..., tₖ — ненулевые целые числа, |tᵢ| ≤ 2^{aᵢ} . Положим sᵢ = t₁ + ... + tᵢ. Предположим, что sₖ = 0, но sᵢ ≠ 0 при i < k. Следует ли из этого, что (k−1) + ν₂(t₁...tₖ) ≤ a₁ + ... + aₖ?

(как обычно, ν₂(x) для целого ненулевого числа x обозначает наибольшее целое m, для которого 2ᵐ делит x)
96🤔5👌3🔥1
Вы, может, думаете, что я такое нелепое спрашиваю про степени двойки? А это, между прочим, решает гипотезу Стенли про биномиальный коэффициент как виртуальный характер на группе нимберов. Можете придумать доказательство получше, чтобы переносилось на q-случай (есть такой критерий в алгебраической комбинаторике: доказательство хорошее, если доказывает и q-версию).
🤔13🤩7🔥53🍾21
Снова много новых подписчиков - это откуда?
50😁64🔥2🐳2😴21
На межнаре предлагалась такая задача (при n=2025):

для какого наименьшего m можно разбить квадрат n×n на m прямоугольников и обобщённую диагональ (=набор из n клеток, по одной в каждой строке и каждом столбце)?

Вопрос не выглядит очень естественным: почему диагональ обобщённая, а прямоугольники обычные? Давайте называть обобщённым прямоугольником a×b множество из ab клеток, лежащих в a строках и b столбцах.

Для какого наименьшего m можно разбить квадрат n×n на m обобщённых прямоугольников и обобщённую диагональ?

Вопрос, правда, довольно стандартный, на олимпиаду не дашь.
212
Разбирая старые бумаги, нашёл тетрадку с задачами, которые придумывал в школе. У всех там написаны и решения, а у этой нет. Никаких воспоминаний о ней.
3316🔥153👍1🎃1
Гипотеза Диница (сейчас теорема Гэлвина) утверждает следующее:

На бал пришли n юношей и n девушек, каждая пара юноша-девушка умеет танцевать n из N>n предлагаемых на балу танцев. Тогда можно организовать танцы так, чтобы каждая пара потанцевала хотя бы раз. (Во время каждого танца можно отдыхать, либо танцевать его ровно с одним партнёром противоположного пола.)

Доказательство (и в такой формулировке это менее удивительно, чем с латинскими квадратами) использует теорему Гейла — Шепли об устойчивом паросочетании: если у каждого юноши есть упорядоченный список предпочтения девушек и наоборот, то их можно всех поженить так, чтобы не нашлось не состоящей в браке пары, предпочитающей друг друга своим супругам.

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

Вот бал начался, объявили вальс. Сейчас, конечно, порядок предпочтений изменился: каждому нравятся в первую очередь те партнёры, с которыми получится станцевать вальс, а они — в базовом порядке. Рассмотрим устойчивое паросочетание для таких порядков предпочтений. В нём некоторые пары могут танцевать вальс, они пусть его танцуют, остальные отдыхают.

Теперь объявили полонез. Порядок предпочтений такой: в первую очередь нравятся партнёры, с которыми пока не танцевали и с кем получится станцевать полонез. В остальном всё как с вальсом.

И так далее для каждого танца.

Докажем, что любая пара, скажем, Саша и Наташа, танцевали друг с другом. Обозначим через m их тайну. Если они не танцуют друг с другом один из танцев, которые умеют, то по условию устойчивости это значит, что либо Саша предпочитает Наташе свою партнёршу, либо наоборот. Первое происходит, когда Саша танцует с девушкой, с которой у него тайна меньше m, и с которой он ещё не танцевал до этого, (таких девушек всего m, так что это может произойти не более m раз). Наоборот бывает у Наташи с юношами, с которыми у неё тайна больше m (таких юношей n-m-1). Итак, они могли пропустить не более m+(n-m-1)=n-1 из своих n танцев, поэтому танцевали друг с другом.
🔥18🤯8👍332
ППКС
2😐1
Forwarded from Ratio et Mysterium
"Один человек из аудитории спросил меня, являются ли математики скорее «изобретателями» — то есть творцами нового мира, созданного их воображением,— или же «первооткрывателями» предсуществующей реальности. Я ответил, что, как и почти все математики, я скорее склоняюсь к платонизму и воспринимаю математику как реальность, независимую от нас, которая существовала в нас, но была сокрыта, укрыта покровом, и наша задача — обнажить её.

Однако, поразмыслив, я прихожу к выводу, что для характеристики деятельности математика (или, в более широком смысле, учёного, ищущего истину) существует слово более точное и куда более глубокое, чем «изобретатель» или «первооткрыватель», слово также полностью библейское, которое появляется в конце длинного отрывка из Гротендика, процитированного мною: математик — это слуга.

Слуга — это тот, кто заботится о чём-то ином, а не о себе: так же и математик, который в моменты погружения в математику теряет даже сознание собственного «я».

Слуга не решает: математик никогда не решает, что является истинным, но постоянно натыкается на сопротивление истины. Он прилагает усилия к истине, но не может её исказить, кроме как немедленно введя себя в заблуждение; он может лишь прилепиться к ней, повиноваться.

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

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

Лоран Лафорг
(перевод с французского)
👍2319🔥8👎5❤‍🔥2
Взаимное расположение корней многочлена и его производной давно интересует математиков, и в целом там всё непросто. В своё время я пытался доказать гипотезу де Брёйна — Шпрингера, что у любой выпуклой функции среднее по корням многочлена не меньше, чем по корням производной, и ничего у меня не вышло — а вскоре после этого вышло у Сени Маламуда, и так умно и коротко, что я до сих пор офигеваю. Потом оказалось, что то же параллельно сделал Раджеш Перейра — вот почему так постоянно происходит, что 55 лет никто не мог доказать, а потом одновременно доказали сразу двое?
41🔥228👍55💯3
Есть невырожденная n×n матрица над полем из 2 элементов. За один ход можно прибавить к одной строке другую. Хочется переставить строки циклически. Это можно сделать за 3n-3 хода (потому что транспозиция двух строк делается за 3 хода). Гипотеза (sic) - что за меньшее число ходов нельзя.
2
https://radcliffe.github.io/01matrixpuzzle/

вместо картинок на выходных в этот раз пусть будет такая игра с матрицами

«This app explores the group of nonsingular n-by-n matrices over the field of two elements. This group is generated by transvections, i.e. adding one row to another row mod 2.

A row swap can be decomposed into three transvections, by the XOR trick. Since any permutation of n elements can be expressed as the product of at most n-1 transpositions, it follows that any permutation matrix can be expressed as the product of at most 3n-3 transvections.

It is conjectured¹ that the cyclic permutation matrix of order n requires no fewer than 3n-3 transvections. This has been verified up to n = 8. Starting from a random invertible matrix, the expected number of steps is Θ(n²/log(n)).»

¹ https://arxiv.org/abs/2503.01467
7