?

Log in

Федор Петров
Я не очень пишу в жж, потому что тут с формулами неудобно. Но тут такой случай, что решение знаменитой задачи можно приложить одной картинкой. Тем более, решается с помощью многочленов, а многочлены наша тема.

Вопрос: какого количества точек в n-мерном пространстве над F_3 достаточно, чтобы в нем заведомо нашлась арифметическая прогрессия длины 3? Знаменитая теорема Рота говорит, что хватает o(3^n) точек. На днях доказали, что хватает c^n точек при некотором c<3 (предыдущие результаты были навроде 3^n/n). Доказали как. Сначала Крут, Пах и Лев выложили короткий препринт, где сделано для поля из 4 элементов, потом быстро несколько людей заметило, что делается ещё короче и для 3 (Тао пишет, что Ellenberg и независимо Gijswijt, подозреваю, что это не полный список.) Я откладывал чтение RGK и поэтому, конечно, опоздал, но не пропадать же добру - читайте. Доказательство улучшено irishoak и, в общем, получается совсем та же оценка, что у Ellenberg и Gijswijt. Правда, можно немного улучшить, и более культурно изложить https://dl.dropboxusercontent.com/u/15433464/f3_eng.pdf

Read more...Collapse )
 
 
Федор Петров
08 February 2016 @ 05:40 pm
Видел, люди считают цитирования, индексы, рейтинги, премии. "О, Вы не знаете Х? Как же, у него премия всеамериканской академии добра, постдок в Йеле и четыре публикации в журналах с импакт-фактором не менее 1.134!"

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

Но есть выход. Если вам недосуг читать чужие работы, - а кому досуг? - но надо по-быстрому узнать, кто самые ценные и лучшие математики года, наиболее уважаемые в сообществе, так узнайте.
 
 
Федор Петров
Многочлен f(x) с комплексными коэффициентами назовем неразложимым, если он не представляется как композиция f(x) = g(h(x)), где g,h - многочлены степени больше 1.

Если f, g - непостоянные неразложимые многочлены с комплексными коэффициентами, то многочлен f(x)-g(y) неприводим кроме тривиального случая g(x)=f(ax+b) и нетривиальных случаев, которые возможны при
попробуйте угадатьCollapse )

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

10 февраля 1996 года я пришёл домой после городской олимпиады 8 класса, дико злой вообще. Смотрите, какую я не решил задачу! Нет, ну надо же таким быть.

В государстве некоторые пары городов соединены беспосадочными (двусторонними) авиарейсами. Новый министр авиации решил раз в месяц перестраивать маршрутную сеть по следующему принципу: в следующем месяце будут соединены рейсами те и только те пары городов, для которых сейчас существует маршрут ровно с одной пересадкой. Через полгода выяснилось, что из любого города можно долететь до любого другого (возможно, с пересадками). Докажите, что если реорганизация будет продолжаться, то и через год можно будет из любого города долететь до любого другого. (А. В. Пастор)
 
 
Федор Петров
Мало кто из коллег был мне так близок - не в смысле математических интересов, и не в смысле тесноты общения, - а в восприятии важных вещей.

-Тут было сказано, - полушепотом сказал мне Сергей Васильевич, - что если A ≥ B, но A ≠ B, то вовсе не обязательно A > B. Я такого переносить не могу и ухожу.

Ну и ушёл. Он часто так поступал. Оставил нам привет, тоже очень в его стиле:

совет ПотапаCollapse )

На следующий день Сергей Васильевич зашёл в Никольский собор:

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

У нас тут такое неправильное, что Сергей Васильевич пошёл домой.
Приими его, Господи, в Своей церкви, с православными.
 
 
 
Федор Петров
Он заваливал евреев на защите диссертаций.

Я ни о чём таком никогда не слышал. Не мог бы кто-нибудь пояснить, какие случаи мог иметь в виду Яков Григорьевич?

На всякий случай: Шафаревич и евреи это очень-очень интересная тема, почти как другие интересные темы, но я призываю оставаться в рамках обсуждения поставленного вопроса.
 
 
 
Федор Петров
У меня по ходу есть крутой читатель, который уже второй шедевр не просто решил, а усилил результат!

Вот третий.

Докажите, что если на окружности выбрать 10^{100} точек, и расставить в них числа от 1 до 10^{100} в каком-то порядке, то можно будет выбрать 100 попарно непересекающихся хорд с концами в выбранных точках, суммы чисел на концах которых равны.

Автор Сергей Львович Берлов, была в шортлисте международной олимпиады 2012 и на олимпиаде 239 школы 2013.
 
 
Федор Петров
В личную почту поступило решение предыдущей задачи, причём оно лучше чем то, которое я знал. Об этом чуть позже, а вот следующий шедевр.

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

Автор Наири Седракян, была на Туймааде в 2008 году.

Авторское решениеCollapse )

Это рассуждение неплохое, но оно по существу евклидово. Ваня Митрофанов предложил более сложный аргумент, который зато работает в любой норме.

Вот такойCollapse )
 
 
Федор Петров
Мне редко нравятся олимпиадные задачи по математике, но бывает что конкретно торкает. Эта среди моих самых фаворитов. Источник - забыл какая именно иранская студенческая олимпиада. Сколько раз где я её ни давал, ни разу ещё никто не решил. Сам тоже не решил в своё время.

На соревновании предложено n заданий и участвует несколько студентов. Каждое задание можно либо выполнить, либо не выполнить. Жюри определяет количество баллов, начисляемое за выполнение каждого задания, случайно выбирая его от 1 до 2n (все 2n возможностей равновероятны; баллы за разные задачи выбираются независимо). Никакие два студента не выполнили одного и того же множества заданий. Докажите, что с вероятностью не менее 1/2 в соревновании будет единственный победитель (участник с наибольшим числом набранных баллов).

РешениеCollapse )

Некоторая проблема этого подхода в том, что если баллы выбираются, скажем, от 1 до n, то получаемая оценка вероятности не удовлетворительна. Ваня Митрофанов предлагает более тонкий аргумент.

Под катомCollapse )

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