Feed aggregator
Pour la science № 576 — пары с суммой степени двойки
В математической рубрике рассматривают задачу: найти набор 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»). Которое в свою очередь ссылается на шутку Эрдоша о том, что бог хранит самые красивые математические доказательства в отдельной книжечке.
Categories: Friends
Pour la science № 576 — пары с суммой степени двойки
В математической рубрике рассматривают задачу: найти набор 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»). Которое в свою очередь ссылается на шутку Эрдоша о том, что бог хранит самые красивые математические доказательства в отдельной книжечке.
comments
Можно представить себе решение задачи в виде графа: точка — число из набора, точки связаны, если их сумма даёт степень двойки. «Оптимистическому» решению соответствует граф, где каждая точка связана с каждой. Но в какой-то момент поняли, что граф реальных решений не может иметь «квадратов», то есть колец длиной в 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»). Которое в свою очередь ссылается на шутку Эрдоша о том, что бог хранит самые красивые математические доказательства в отдельной книжечке.
Categories: Friends
State Department to deny visas to fact checkers and others, citing 'censorship'
Categories: Software