![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
green_frВ математической рубрике рассматривают задачу: найти набор n различных целых чисел, из которых можно составить максимальное количество пар, сумма которых равнялась бы степени двойки. Например, для 4 чисел это {-3, −1, 3, 5} — итого 4 пары. Задача, конечно же, не столько решить для конкретного n, сколько найти общий принцип, ну или хотя бы формулу для оценки количества пар, которое можно получить. Очевидно, что самая оптимистическая оценка — это n(n-1)/2, если все без исключения пары образуют степень двойки. Очевидно, это не так.
Можно представить себе решение задачи в виде графа: точка — число из набора, точки связаны, если их сумма даёт степень двойки. «Оптимистическому» решению соответствует граф, где каждая точка связана с каждой. Но в какой-то момент поняли, что граф реальных решений не может иметь «квадратов», то есть колец длиной в 4 ребра. Доказать это достаточно просто, но как оценить количество графов без «квадратов»?
Мне очень понравился вывод (István Reiman, 1958). Пусть наш граф G состоит из n вершин s1, ... sn и m рёбер. Назовём d(si) — количество рёбер, соединяющих вершину i с другими вершинами. Очевидно сумма d(si) равняется 2m. Рассмотрим граф без «квадратов». Посчитаем количество структур a-b-c (3 связанные точки). Оно равно d(b)(d(b)-1)/2. Поскольку граф без квадратов, то каждой паре a-c соответствует максимум одна соединяющая их вершина b. То есть пар точек должно быть не больше, чем соединённых троек. Пар точек у нас n(n-1)/2, соединённых троек = сумма по всем точкам d(b)(d(b)-1)/2. Итого:
По неравенству Коши-Буняковского:
То есть:
А это квадратное уравнение относительно суммы d, про которую мы с самого начала говорили, что она равняется 2m, то есть: 4m²≤n²(n-1)+2nm => m²-mn/2-n²(n-1)/4≤0
Решая квадратное уравнение, получаем: m≤(n/4)(1+(4n-3)1/2) — отличная оценка сверху для количества рёбер в графе без квадратов!
Потом в статье рассказывают, какие ещё нашлись «запрещённые» фигуры, как ещё можно улучшить оценку сверху. Но до чего же красивое доказательство! Наконец-то пригодилось не только квадратное уравнение, но и знакомое с института словосочетание Коши-Буняковского (во французском варианте вместо Буняковского был Шварц). Автор пишет, что это доказательство включили в книгу Raisonnements divines — опять же, французский вариант звучит совершенно по-другому («Божественно красивые доказательства»), чем русский перевод книги («Доказательства из Книги»), буквально следующий английскому оригиналу («Proofs from THE BOOK»). Которое в свою очередь ссылается на шутку Эрдоша о том, что бог хранит самые красивые математические доказательства в отдельной книжечке.
Можно представить себе решение задачи в виде графа: точка — число из набора, точки связаны, если их сумма даёт степень двойки. «Оптимистическому» решению соответствует граф, где каждая точка связана с каждой. Но в какой-то момент поняли, что граф реальных решений не может иметь «квадратов», то есть колец длиной в 4 ребра. Доказать это достаточно просто, но как оценить количество графов без «квадратов»?
Мне очень понравился вывод (István Reiman, 1958). Пусть наш граф G состоит из n вершин s1, ... sn и m рёбер. Назовём d(si) — количество рёбер, соединяющих вершину i с другими вершинами. Очевидно сумма d(si) равняется 2m. Рассмотрим граф без «квадратов». Посчитаем количество структур a-b-c (3 связанные точки). Оно равно d(b)(d(b)-1)/2. Поскольку граф без квадратов, то каждой паре a-c соответствует максимум одна соединяющая их вершина b. То есть пар точек должно быть не больше, чем соединённых троек. Пар точек у нас n(n-1)/2, соединённых троек = сумма по всем точкам d(b)(d(b)-1)/2. Итого:
По неравенству Коши-Буняковского:
То есть:
А это квадратное уравнение относительно суммы d, про которую мы с самого начала говорили, что она равняется 2m, то есть: 4m²≤n²(n-1)+2nm => m²-mn/2-n²(n-1)/4≤0
Решая квадратное уравнение, получаем: m≤(n/4)(1+(4n-3)1/2) — отличная оценка сверху для количества рёбер в графе без квадратов!
Потом в статье рассказывают, какие ещё нашлись «запрещённые» фигуры, как ещё можно улучшить оценку сверху. Но до чего же красивое доказательство! Наконец-то пригодилось не только квадратное уравнение, но и знакомое с института словосочетание Коши-Буняковского (во французском варианте вместо Буняковского был Шварц). Автор пишет, что это доказательство включили в книгу Raisonnements divines — опять же, французский вариант звучит совершенно по-другому («Божественно красивые доказательства»), чем русский перевод книги («Доказательства из Книги»), буквально следующий английскому оригиналу («Proofs from THE BOOK»). Которое в свою очередь ссылается на шутку Эрдоша о том, что бог хранит самые красивые математические доказательства в отдельной книжечке.
no subject
Date: 2025-12-05 02:48 pm (UTC)Часто приходится слышать риторический вопрос "зачем мне в жизни пригодится умение решать квадратное уравнение". Если подумать, то оказывается что действительно редко, и непонятно, почему в школе всех заставляют зазубривать эту формулу.
Как раз то самое исключение, которое подтверждает правило.
no subject
Date: 2025-12-05 03:10 pm (UTC)Потому что иначе вам придётся отвечать на вопрос: ок, квадратные уравнения нужны для вот этого всего, но зачем нам нужно было всё вот это? :-)
no subject
Date: 2025-12-05 03:32 pm (UTC)Мне всегда такой ответ казался неубедительным, потому что его применяли для всего. Учись играть в шахматы, это развивает мозг и умение думать. Учи стихотворение наизусть, это развивает память. Запоминай дату Куликовской битвы, кто не учит историю, тот будет её повторять.
Задним умом понятно, что хотя бы некоторая часть таких утверждений голословна. Прокачивать мозги лучше на том, что потом пригодится. Метод Ньютона, Монте Карло и бутстрап гораздо полезнее и вполне по силам среднему школьнику, но их в школьной программе нет.
no subject
Date: 2025-12-05 04:30 pm (UTC)То есть, мне кажется, что логика школьного обучения именно в этом. Прокачивать "мышцу" мозга, учить какие-то методики обучения (та же история не столько про "иначе будешь повторять", сколько про умение работать с документами, анализировать текст, резюмировать события). Прикладное обучение тоже бывает (у нас в школе был токарный станок - пока не пригодилось), но это же совсем маргинально. Типа научиться считать в уме, чтобы в магазине не обманули.
no subject
Date: 2025-12-05 04:57 pm (UTC)Как раз среднему программисту для работы не нужны ни Монте Карло, ни бутстрап.
Они нужны среднему человеку для того, чтоб делать грубые прикидки неопределённости. А это нужно для принятия решений. Вакцинироваться или нет? Ну вот клиническое исследование, количество пациентов, количество заболевших, есть разница или нет? В формулах не разобраться, там непонятные греческие буквы, ну так и не надо. Можно самостоятельно прикинуть, примерно.
Программировать для этого необязательно, можно обойтись экселем, гуглшитсом или любой подручной электронной таблицей. Мне когда в первый раз показали, чётко помню свою реакцию — "а что, разве так можно было?"