i_eron

Газета "Чикаго Сан-Таймс" опубликовала список рекомендованных к чтению на лето книг. К каждой книге прилагается описание в несколько строчек. Из пятнадцати книг в списке десяти не существует.

Давайте я вам расскажу про задачу номер шесть Международной Математической Олимпиады в 1988 году. Оказывается, эта задача знаменита (в узких кругах математиков, интересующихся олимпиадными задачами) своей сложностью. На последнее, шестое место традиционно ставят самую тяжелую задачу. В том году шестую задачу полностью решило всего 11 участников из многих сотен. Среди них был Никушор Дан, новый румынский президент (так я узнал об этой задаче), а вот например знаменитый математик Теренс Тао не смог ее решить. Ему, правда, было только 13 лет, но это все равно был Теренс Тао.

Немецкий математик Артур Энгель пишет так об этой задаче в своей книге "Стратегии решения задач":

"Следующая задача была подана в 1988 году от ФРГ. Никто из шести членов австралийского комитета по задачам не смог её решить. Двое из членов были Дьёрдь и Эстер Секереш, оба известные решатели и составители задач. Поскольку это была задача по теории чисел, её отправили четырём самым известным австралийским специалистам по теории чисел. Их попросили поработать над ней в течение шести часов. Никто из них не смог решить её за это время. Комитет по задачам представил её жюри XXIX Международной математической олимпиады, отметив двойной звёздочкой, что означало сверхсложную задачу, возможно, слишком сложную для предложения. После долгого обсуждения жюри наконец набралось смелости выбрать её в качестве последней задачи соревнования. Одиннадцать студентов представили идеальные решения."

Вот эта задача. Дано, что a,b положительные целые числа, и a^2+b^2 без остатка делится на a*b+1. Доказать, что результат этого деления - полный квадрат (т.е. число вида x^2).

Ее решение, которое я подсмотрел в википедии, так элегантно и просто, что не могу удержаться от соблазна рассказать его здесь. Как это сочетается с тем, что это супер-тяжелая задача, которую почти никто не решил? Дело в том, что до главной идеи доказательства очень тяжело додуматься самому, и можно лишь позавидовать таланту тех 11, кому это удалось.

Да, перед тем, как рассказать решение, отмечу еще один интересный факт об этой задаче. Ее автор - некий Стефан Бек (Stephan Beck) из Западной Германии. Никто не знает, как она пришла ему в голову, и никто не может его спросить, потому что никто не знает, кто он такой. Математика с таким именем, публикующего научные статьи, не существует (есть генетик, вряд ли это он). В разных книгах и постах в интернете мне попались сожаления о том, что авторы не смогли ничего о нем разузнать. Я перелопатил вчера кучу интернетной руды и единственная кроха, которую нашел - это что этот же человек подавал от Германии две другие задачи, которые вошли в списки кандидатов для Олимпиад-1995 и -2002, но не были в итоге использованы. Это упоминается в книге "IMO Compendium", и там есть условия этих двух задач, они тоже по теории чисел. Если кто-то может разыскать какую-то информацию о нем, поделитесь, это интересно.

Теперь обещанное решение. Докажем от противного. Пусть A,B числа, опровергающие условие: можно записать Α^2+B^2 = k(AB+1), где k какое-то целое положительное число, но не полный квадрат. Если A=B, то неизбежно k=1 и это квадрат, так что мы можем предположить, что одно из них больше другого, например A > B.

Теперь сгруппируем эти числа как квадратное уравнение от "переменной" A:

A^2 - (kB)A + (B^2-k) = 0

Мы знаем, что у этого уравнения есть одно решение: собственно A! Значит, есть еще одно, некое C (при этом гипотетически возможно C=A, хотя потом мы докажем, что нет), и по формулам Виета выполняются два равенства:

A+C = kB
A*C = B^2-k

Из первого равенства мы видим, что C целое число, оно равно kB-A. Из того, что C выполняет уравнение, мы видим - группируя в обратную сторону - что C^2+B^2 = k(CB+1), и поскольку в этом уравнении всё, кроме CB+1, положительно, CB+1 тоже >0, и значит C положительное или 0. Однако C не может быть 0, потому что из второго равенства следовало бы B^2-k = 0, но k не полный квадрат (вот где мы этим воспользовались!). Значит, C > 0.

Наконец, из второго равенства выше мы видим, что A*C = B^2-k < B^2, и поскольку мы предположили A>B, неизбежно C < A, иначе их произведение было бы больше B^2.

Итак, мы пришли к тому, что контрпример к исходному утверждению в виде A,B, где A>B, можно заменить на C,B, где C<A, все еще оба числа положительные и выполняют, что нужно, и это новый контрпример. При этом сумма A+B уменьшается и становится C+B. Но это значит, что мы можем строить контрпримеры неограниченно долго, все время уменьшая сумму A+B - а это абсурдно (скажем, если бы вначале эта сумма была 1000, мы не сможем уменьшать ее больше 1000 раз). Поэтому таких A,B не существует, т.е. из Α^2+B^2 = k(AB+1) следует, что k полный квадрат. Что и требовалось доказать. Эта техника перехода от A к C, где оба - решения одного квадратного уравнения, называется "прыжки Виета", Vieta jumping.

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

P.S. Про самолет надо все-таки пояснить; то, что это "личный подарок Трампу", разумеется оспаривается трампистами. Сделка еще не завершена и возможно не будет. То, что попало в прессу - это слив намерений заключить сделку так, что формально самолет передается в подарок министерству обороны США для использования в качестве президентского борта, но с условием, что до января 2029 года, когда должен заступить следующий президент, его передадут в подарок "президентской библиотеке" Трампа (нон-профит организации, не ему лично, но для того, чтобы он на нем летал, разумеется).

==========================
Про катарский самолет решил написать.

Когда я 6 лет назад начинал писать заметки про американскую политику, моей целью было восполнить недостаток качественной информации на русском языке. Мне казалось, что для людей, интересующихся политикой в России, происходяшее в Америке важно и на идейном, и на практическом уровне, так что будет полезно, если больше людей будет об этом знать.

В последние месяцы мне такая постановка кажется довольно-таки бесполезной: при новой администрации американская политика добровольно-принудительно пришла, кажется, ко всем и следят за ней в результете тоже все, так что не очень понятно, какая от меня может быть информационная польза. Но вот сейчас, кажется, есть что сказать.

Трамп-2 производит такое количество новостей, что приходится отбирать, за чем следить: за демонтажом послевоенного международного порядка, за вялотекущей сдачей Украины, за торговыми войнами, за Маском, за нападками на судей, сми, университеты и т.д, и т.п. Между тем, есть одна тема, которая на общем фоне привлекает меньше внимания и совершенно напрасно. Речь об ошеломляющем, совершенно циклопический уровне коррупции в новой администрации.

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

Администрация отказывается применять закон, запрещающий американским гражданам и компаниям давать и принимать взятки в зарубежных странах, и закон, требующий регистрировать конечных бенефициаров подставных кампаний. Остановлена работа ведомства по надзоры за правами потребителей в финансовой сфере. Радикально сокращены штаты органа, проверяющих налоговые декларации богатых американцев.
С другой, Трамп и его семья обогащаются с какой-то совершенно космической скоростью. Им несут множеством способов. Это и огромные выплаты в несудебном порядке по разным сомнительным и откровенно нелепым судебным искам, которые Трамп многие годы предъявляет всем, кто чем-либо его обидел, и пожертвования в иннагурационный фонд, и 40 миллионов долларов, выплаченные Мелании Трамп за право снять о ней документальное кино. Это спонсирование гольф-турнира, патронируемого Трампом, саудовским госфондов и ТикТоком. Это огромные новые контракты, заключаемые Trump Organization с инвесторами, аффилированными с иностранными правительствами. Это подаренный катарцами лично Трампу летающий дворец за 400 млн долларов. Но, видимо, самое главное - это мемкоин $TRUMP, через который совершенно непрозрачно прокачиваются огромные суммы с единственной целью - заплатить Трампу и его семье взятку в виде комиссионных. Всё это производит впечатление огромной прорвы, похожей на полностью нудовлетворенного кадавра профессора Выбегалло. Трудно точно оценить масштабы происходящего, но средние оценки, кажется, в районе 2-3 млрд долларов за 4 месяца. То есть этот трампосос заглатывает бабло со скоростью примерно 1 млн. долларов в час. Очень похоже, что по скорости поглощения денег это самый большой коррупционный проект в истории человечества.

За что Трампу платят, тоже кажется более-менее очевидным:

- медиа- и интернет-гиганты откпаются от возможной травли и преследования со стороны администрации;
- ТикТок должен был быть запрещен в Америке по решению суда, но к большой удаче его владельцев, Трамп приостановил это решение;
- Трамп вполне открыто обешаяет крупнейшим вкладчикам $TRUMP прямой доступ к нему лично;
- есть информация, что иностранные фирмы проводят в отчетности деньги, потраченные на $TRUMP как "расходы на лоббирование против таможенных пошлин";
- вообще вся эта бурная торговая война Трампа с самим собой (вчера внезапно поднял пошлины без всякой причины, сегодня так же внезапно опустил в обмен на ничего), кажется совершенно бессмысленной, если только не делается ради insider trading и торговли индивидуальными исключениями.

Естественно, происходящее настолько незаконно, насколько это вообще может быть: в конституции США битым словом написано
No Person holding any Office of Profit or Trust under [United States], shall, without the Consent of the Congress, accept of any present, Emolument, Office, or Title, of any kind whatever, from any King, Prince, or foreign State.

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

Недавно у старшего ребенка был багрут (общеизраильский выпускной экзамен) по математике. Я помогал ей готовиться.

Структура там устоявшаяся (это 11-й класс, предпоследний, наиболее полная программа из трех вариантов):

- 8 задач
- одна блиц-раунд: четыре мини-задачи по разным темам, надо сделать любые две
- одна на арифметические/геометрические прогрессии
- одна на теорию вероятностей (включая понятие условной вероятности, но не доходя до теоремы Байеса)
- две на геометрию: треугольники, круги, трапеции. Одна из двух обычно с использованием тригонометрии.
- три на исследование функций: область определения, асимптоты, экстремальные значения, точки перегиба, нарисовать график, найти площадь, все это возможно с каким-то параметром, оптимизировать его значение каким-то образом. Обычно одна задача функция с корнями, другая тригонометрическая, третья геометрическая, где функцию надо определить самому из условий, данных словами.
- всего надо решить 5 задач, из них не меньше 2 по функциям, не меньше 1 по геометрии, не меньше 1 из отдела "мини"/прогрессии/вероятности.

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

1. Что биссектриса делит сторону, на которую падает, в той же пропорции, что две остальные стороны треугольника
2. Что угол между касательной к окружности и хордой равен вписанному углу с вершинами этой хорды.

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

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