МАЛЫЙ МЕХМАТ МГУ

Лекция 1 (420) 16.09.2017

Александр Васильевич СПИВАК,

автор книг «1001 задача по математике», «Математический кружок», «Математический праздник», «Турниры математических боёв имени А.П. Савина», «Арифметика» и «Арифметика—2».

Композиции булевых функций, полные и предполные классы функций

Монотонные, самодвойственные, линейные, сохраняющие ноль, сохраняющие единицу — таковы пять предполных классов булевых функций. Узнали, что такое многочлен Жегалкина, дизъюнктивная нормальная форма, стрелка Пирса и штрих Шеффера. Доказали теорему Поста: любой набор, не содержащийся ни в одном из этих пяти классов, порождает всё множество булевых функций. Лекция не требует никаких предварительных знаний, кроме умения следить за математическими рассуждениями.

Есть видеозапись:
1. «Булевы функции, стрелка Пирса и штрих Шеффера»;
2. «Дизъюнктивная нормальная форма, многочлены Жегалкина»;
3. «Предполные классы Эмиля Поста»;
4. «Штрих Шеффера и стрелка Пирса»;
5. «Формулировка теоремы Поста о предполных классах»;
6. «Доказательство теоремы Поста о пяти предполных классах»;
7. «Иллюстрация к теореме Поста (ноль, единица, конъюнкция и сумма трёх переменных)».

Лекция 2 (421) 23.09.2017

Сергей Борисович ГАШКОВ,

профессор кафедры дискретной математики мехмата МГУ, автор книг «Арифметика. Алгоритмы. Сложность вычислений», «Элементарное введение в эллиптическую криптографию», «Криптографические методы защиты информации», «Современная элементарная алгебра в задачах и упражнениях», «Системы счисления и их применения».

Два отрицания, конъюнкции и дизъюнкции. Четырёхмерный куб

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

Что такое двоичный многомерный куб? Как его рисовать, как на нём наглядно изображать булевы функции (то же, что функции алгебры логики)? Как это применять в комбинаторике?

Советую посмотреть рассказ о двоичном сумматоре.

Есть видеозапись:
1. «Два отрицания, конъюнкции и дизъюнкции»;
2. «Четырёхмерный куб»;
3. «Кратчайшая дизъюнктивная нормальная форма».

Лекция 3 (422) 30.09.2017

Александр Васильевич СПИВАК,

автор книг «1001 задача по математике», «Математический кружок», «Математический праздник», «Турниры математических боёв имени А.П. Савина», «Арифметика» и «Арифметика—2».

Комплексные числа и кватернионы

Что такое модуль и аргумент комплексного числа, как использовать умножение и сложение комплексных чисел для описания поворотной гомотетии плоскости?

Как выразить произведение кватернионов через скалярное и векторное произведение векторов?

Как произведение кватернионов помогает в доказательстве теоремы Лагранжа о представимости любого натурального числа в виде суммы четырёх квадратов целых чисел?

Есть видеозапись:
1. «Комплексные числа (алгебраическое и геометрическое определения)»;
2. «Поворот вокруг точки и умножение на комплексное число»;
3. «Таблица умножения кватернионов и векторное произведение»;
4. «Векторное умножение суммы на вектор»;
5. «Тождество Якоби»;
6. «Скалярное произведение векторов»;
7. «Сумма квадратов синуса и косинуса. Объём параллелепипеда»;
8. «Любое натуральное число — сумма четырёх квадратов».

Лекция 4 (423) 7.10.2017

Александр Васильевич СПИВАК,

автор книг «1001 задача по математике», «Математический кружок», «Математический праздник», «Турниры математических боёв имени А.П. Савина», «Арифметика» и «Арифметика—2».

Комплексные числа и кватернионы, а также о причёсывании ёжа

Поворот пространства вокруг данной оси, проходящей через начало координат, легко записать при помощи умножения кватернионов.

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

Есть видеозапись:
9. «Напоминание: комплексные числа, кватернионы»;
10. «Причёсывание ежа и несуществование 3-мерной алгебры без делителей нуля»;
11. «Двумерная сфера в 3-мерном пространстве, трёхмерная в 4-мерном»;
12. «Поворот плоскости и умножение на комплексное число»;
13. «Углы Эйлера и умножение матриц»;
14. «Композиция поворотов»;
15. «Кватернионы и вращения двумерной сферы»;
16. «Спин. Группа вращений четырёхмерного пространства».

Лекция 5 (424) 14.10.2017

Илья Дмитриевич ШКРЕДОВ,

ведущий научный сотрудник Математического института имени В.А. Стеклова, профессор кафедры динамических систем мехмата МГУ.

Суммы и произведения

Суммой A + A (соответственно, произведением A · A) множества A с самим собойназовём множество сумм a + b (соответственно, попарных произведений ab), где a и b пробегают множество A. Насколько сильно вырастает количество элементов множества при взятии суммы или произведения? С одной стороны, существуют множества с относительно малой суммой: сумма арифметической прогрессии, состоящей из n элементов (например, из первых n натуральных чисел), с собой состоит из 2n – 1 элементов. С другой стороны, произведение геометрической прогрессии, состоящей из n разных чисел (например, из последовательных степеней двойки) тоже состоит из 2n – 1 элементов (и здесь перемножаем прогрессию саму на себя). Гипотеза сумм и произведений утверждает: не существует множеств, имеющих одновременно и малую сумму, и малое произведение, точнее, сумма количеств элементов суммы и произведения n-элементного конечного множества не может быть слишком маленькой. (Более точную формулировку найдёте в лекции.)

Гипотеза сумм и произведений до сих пор не доказана, но даже частичный прогресс в данной области уже привёл к интересным продвижениям в арифметике, теории графов, геометрии.

Есть видеозапись:
1. «Сумма множеств»;
2. «Сколько произведений в таблице умножения?»;
3. «Суммы и произведения»;
4. «Неравенство Семериди-Троттера и его применение к суммам-произведениям»;
5. «Теорема Семериди—Троттера для декартова произведения»;
6. «Теорема Шоймоши, теорема Конягина и Шкредова»;
7. «Идея доказательства теоремы Шоймоши»;
8. «Доказательство теоремы Шоймоши для сумм и частных»;
9. «Доказательство теоремы Шоймоши для сумм и произведений».

Лекция 6 (425) 21.10.2017

Александр Ханиевич ШЕНЬ,

кандидат физико-математических наук, научный сотрудник Института проблем передачи информации РАН и LIRMM (Монпелье, Франция), автор многих брошюр и книг для школьников и студентов: «Геометрия в задачах», «Программирование: теоремы и задачи», «Вероятность: примеры и задачи», «Игры и стратегии с точки зрения математики», «Математическая индукция», «Простые и составные числа», «О «математической строгости» и школьном курсе математики», «Космография».

Непостроимость середины отрезка одной линейкой

На плоскости нарисована окружность. Можно ли одной линейкой построить её центр? Давид Гильберт думал, что нельзя. Доказал он это при помощи центральной (стереографической) проекции, которая переводит окружность в себя, а центр переводит не в центр, а в другую точку. Почему такая центральная проекция существует, понять нетрудно. Но нет ли в рассуждениях Гильберта ошибки?

Другими словами, можно ли при помощи одной только линейки разделить отрезок пополам? Что такое построение одной линейкой? (Или одним циркулем, или циркулем и линейкой?) Как доказать невозможность деления отрезка пополам одной линейкой?

Есть видеозапись:
1. «Простейшие построения циркулем и линейкой»;
2. «Удвоение отрезка одним циркулем»;
3. «Замечательное свойство трапеции»;
4. «Непостроимость середины отрезка одной линейкой (идея доказательства)»;
5. «Критика доказательства непостроимости, или Что такое произвольная точка?»;
6. «Непостроимость середины отрезка одной линейкой (доказательство)»;
7. «Гильберт, две окружности, Акопян и Фёдоров».

Лекция 7 (426) 28.10.2017

Александр Васильевич СПИВАК,

автор книг «1001 задача по математике», «Математический кружок», «Математический праздник», «Турниры математических боёв имени А.П. Савина», «Арифметика» и «Арифметика—2».

Количество пересечений, или Вероятности и графы

Для любого натурального числа V, отличного от 1 и 2, легко нарисовать на плоскости граф, в котором V вершин и 3V – 6 рёбер.

При помощи формулы Эйлера доказали, что количество пересечений (позволяем в каждой точке пересекаться не более чем двум рёбрам), которые образуются при изображении графа с E рёбрами и V вершинами, не может быть меньше числа E – 3V + 6.

Затем доказали, что если E ≥ 4V, то количество пересечений не меньше величины E³/(64V²). Доказательство использует вероятности, точнее, среднее значение числа пересечений.

Из неравенства для количества пересечений вывели неравенство Семериди—Троттера о количестве инциденций (то есть пар (точка, прямая), в которых точка принадлежит прямой), которое было использовано в лекции И.Д. Шкредова.

Есть видеозапись:
10. «Точки и прямые, или Теорема Семериди-Троттера»;
11. «Полный граф на 6 вершинах можно нарисовать с тремя пересечениями»;
12. «Формула Эйлера»;
13. «Добавляем пересечения в качестве вершин»;
14. «Попытка применения формулы Эйлера»;
15. «Максимальное количество рёбер планарного графа с данным числом вершин»;
16. «Полный граф на 6 вершинах нельзя изобразить менее чем с 3 пересечениями»;
17. «Неравенство для графов с 2, 1, 0 вершинами»;
18. «Эрдёш и «Доказательства из Книги» Айгнера и Циглера»;
19. «Граф и вероятности»;
20. «Среднее значение суммы равно сумме средних значений»;
21. «Два доказательства неравенства о числе пересечений»;
22. «Можно ли улучшить оценку, например, заменить 64 на 29?»;
23. «Точки, прямые, количество пар «точка и проходящая через неё прямая»»;
24. «Сумма степеней вершин графа вдвое больше количества его рёбер»;
25. «Вывод неравенства Семериди-Троттера из неравенства о количестве пересечений»;
26. «Количество прямых, проходящих не менее чем через данное число точек».

Лекция 8 (427) 11.11.2017

Сергей Борисович ГАШКОВ,

профессор кафедры дискретной математики мехмата МГУ, автор книг «Арифметика. Алгоритмы. Сложность вычислений», «Элементарное введение в эллиптическую криптографию», «Криптографические методы защиты информации», «Современная элементарная алгебра в задачах и упражнениях», «Системы счисления и их применения».

Знакомые и незнакомые

В 1960 году на Московской математической олимпиаде была такая задача. Собрались n человек. Некоторые из них знакомы между собой, причём каждые два знакомых не имеют общих знакомых, а каждые два незнакомых имеют ровно двух общих знакомых. Докажите, что каждый из них знаком с одним и тем же числом человек. Она широко известна и несложно решается, но при этом остаётся невыясненным, при каких n существуют такие компании? Очевидно, при n = 4 существуют. А при каких ещё? Может быть их больше нет? Есть!

В 2012 году на той же Московской олимпиаде была предложена похожая задача. Собрались n человек. Каждые два имеют ровно двух общих знакомых. Докажите, что каждый из них знаком с одним и тем же числом человек.

Вот ещё одна похожая задача. Собрались n человек. Некоторые из них знакомы между собой, причём каждые два знакомых не имеют общих знакомых, а у каждых двух незнакомых есть ровно один общий знакомый. Докажите, что каждый из них знаком с одним и тем же числом человек.

И в этих задачах вопрос о том, при каких n существуют такие компании, тоже оказался непростым.

Есть видеозапись:
1. «Московская олимпиада 1960 года»;
2. «Московская олимпиада 2012 года»;
3. «Граф Клебша, или 4-мерный куб с диагоналями»;
4. «Три графа Клебша и число Рамсея R(3,3,3)»;
5. «Графы Мура»;
6. «Граф Петерсена»;
7. «У любых двух вершин две соседки»;
8. «Квадрат матрицы, собственные значения и след»;
9. «Эрдёш, Реньи и Сос о графе, в котором у любых двух вершин одна общая соседка».

Лекция 9 (428) 18.11.2017

Даниил Владимирович МУСАТОВ,

доцент кафедры дискретной математики Московского физико-технического института.

Сюрреальные числа Конвея

Рассказ о книге Конвея «On numders and games». Советую книгу «Комбинаторная теория игр» Пьера Деорнуа и статью А. Кириллова, И. Клумовой и А. Сосинского «Сюрреальные числа Конвея».

Есть видеозапись:
0. «Даниил Владимирович Мусатов»;
1. «Игра «Жизнь». Конвей»;
2. «Кусторезка Конвея»;
3. «Числа для игр»;
4. «Фигурные скобки и разделитель, или Что такое игра?»;
5. «Игры положительные, отрицательные, равные нулю, не сравнимые с нулём»;
6. «Сумма игр»;
7. «Три вторых»;
8. «Три вторых в картинках»;
9. «Красно-синяя цепочка»;
10. «Порядок возникновения сюрреальных чисел»;
11. «Одна треть. Бесконечно большие и бесконечно малые сюрреальные числа».

Лекция 10 (429) 25.11.2017

Александр Васильевич СПИВАК,

автор книг «1001 задача по математике», «Математический кружок», «Математический праздник», «Турниры математических боёв имени А.П. Савина», «Арифметика» и «Арифметика—2».

Формула Эйлера

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

Есть видеозапись:
1. «Точки внутри прямоугольника»;
2. «Формула Эйлера и сумма углов многоугольника»;
3. «Остовное дерево и два доказательства теоремы Эйлера»;
4. «Задача М320»;
5. «Теорема Сильвестра»;
6. «Точки двух цветов»;
7. «Раскраска в 5 цветов»;
8. «Идея списков красок»;
9. «Списочная раскраска».

Лекция 11 (430) 2.12.2017

Александр Ханиевич ШЕНЬ,

кандидат физико-математических наук, научный сотрудник Института проблем передачи информации РАН и LIRMM (Монпелье, Франция), автор многих брошюр и книг для школьников и студентов: «Геометрия в задачах», «Программирование: теоремы и задачи», «Вероятность: примеры и задачи», «Игры и стратегии с точки зрения математики», «Математическая индукция», «Простые и составные числа», «О «математической строгости» и школьном курсе математики», «Космография».

Теорема о промежуточном значении и количество оборотов кривой вокруг точки

Непрерывная функция, принимающая на концах отрезка длиной 1 равные значения, принимает равные значения и в некоторых двух точках, отличающихся на 1/2.Любая непрерывная на окружности функция в некоторых двух диаметрально противоположных точках принимает равные значения.

Есть видеозапись:
1. «Непрерывная функция принимает все промежуточные значения»;
2. «Альпинист»;
3. «Футбольный матч»;
4. «Уравнения»;
5. «Гора вдоль экватора»;
6. «Количество оборотов кривой вокруг точки»;
7. «Кол, верёвка, нулевое число оборотов»;
8. «Нулевое число оборотов и гомотопия»;
9. «Муравьи на отрезке»;
10. «Непрерывное отображение круга на граничную окружность»;
11. «Невозможно ретрагировать круг на его границу»;
12. «Ещё раз о количестве оборотов и неретрагируемости круга на его границу»;
13. «Теорема Борсука-Улама».

Лекция 12 (431) 9.12.2017

Александр Васильевич СПИВАК,

автор книг «1001 задача по математике», «Математический кружок», «Математический праздник», «Турниры математических боёв имени А.П. Савина», «Арифметика» и «Арифметика—2».

Формула Эйлера (окончание)

Из формулы Эйлера о количестве вершин, рёбер и граней выпуклого многогранника вывели, что

если граф можно нарисовать на плоскости так, чтобы рёбра пересекались только в случаях, когда они выходят из одной вершины, то его можно распрямить, то есть так непрерывно продеформировать рёбра, непрерывно передвигая при необходимости и вершины, чтобы у полученного в результате графа все рёбра были бы отрезками (теорема Фари);

для любых двух непересекающихся конечных множеств точек плоскости, объединение которых не лежит на одной прямой, существует хотя бы одна прямая, проходящая хотя бы через две точки одного из множеств и не проходящая ни через одну точку другого;

выпуклый многогранник недеформируем, то есть полностью определяется своими гранями;

ежа нельзя причесать (то есть не существует непрерывное касательное к двумерной сфере векторное поле, ни один из векторов которого не равен нулю).

Есть видеозапись:
10. «Теорема Фари о выпрямлении рёбер планарного графа»;
11. «Рёбра двух цветов и лемма Коши о переменах цвета»;
12. «Доказательство леммы Коши о переменах цвета»;
13. «Жёсткость выпуклого многогранника»;
14. «Теорема косинусов для трёхгранного угла»;
15. «Двойственная к теореме Сильвестра»;
16. «Красные и синие прямые»;
17. «Векторные поля и количества оборотов»;
18. «Векторное поле, сумма индексов особых точек которого равно эйлеровой характеристике»;
19. «Сумма индексов не зависит от поля».

Лекция 13 (432) 16.12.2017

Светлана Анатольевна БУРЛАК,

доктор филологических наук, профессор Российской академии наук, ведущий научный сотрудник Института востоковедения РАН, старший научный сотрудник кафедры теоретической и прикладной лингвистики филологического факультета МГУ имени М.В. Ломоносова.

Самодостаточные лингвистические задачи

Лингвистику не проходят в школе, поэтому многие думают, что занимается она прежде всего теми правилами, которые в школе учат не нарушать. На самом деле главная задача лингвистики куда интереснее — описывать, как устроены самые разные языки. Даже самый неграмотный человек никогда не скажет «большая стол стоит в комнату», если русский язык для него родной. Почему? А, например, в английском языке прилагательные не изменяются, а существительные — только по числам. И таких законов много, для каждого языка — свои.

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

Лекция 14 (433) 10.02.2018

Александр Чедович ПИПЕРСКИ,

германист, научный сотрудник и преподаватель Высшей школы экономики, доцент Института лингвистики РГГУ, кандидат филологических наук, автор книги «Конструирование языков: от эсперанто до дотракийского», один из редакторов-составителей книги «Лингвистика для всех. Летние лингвистические школы 2009—2011», лауреат премии «Просветитель».

Измерение расстояний между текстами

Что значит фраза «тексты похожи»? Скорее всего, имеется в виду, что в этих текстах встречаются одни и те же слова с примерно одинаковыми частотами. Мы обсудили:
— какие бывают меры расстояния между текстами и что вообще значит «расстояние» в бытовом и математическом смысле?
— как узнать, насколько хорошо эти меры работают и какая мера самая правильная?
— правда ли, что надо смотреть на слова или лучше взять что-нибудь другое, например частоту отдельных букв?
— как с помощью этих мер обрабатывать поисковые запросы, изучать историю литературы, объединять новости в тематические сюжеты и определять авторство текста?

Есть pdf-конспект лекции и такого же содержания pptx-файл.

Есть видеозапись:
0. «Расстояния между словами, текстами»;
1. «Из мухи делаем слона»;
2. «Расстояния Хэмминга и Левенштейна»;
3. «Расстояния между текстами. Частоты»;
4. «Евклид и Манхэттен»;
5. «Расстояния Минковского. Максимум модуля. Косинус»;
6. «Статистические меры похожести текстов»;
7. «Какая из систем самая хорошая? Манхэттенская!»;
8. «Частоты пар букв. Язык программирования Python».

Лекция 15 (434) 17.02.2018

Павел Александрович КОЖЕВНИКОВ,

доцент Московского физико-технического института, сотрудник Лаборатории популяризации и пропаганды математики Математического института имени В.А. Стеклова, заместитель главного редактора журнала «Квант».

Счётчики и расстояния в графах

Рассказ об одноимённой статье «Кванта».

Есть видеозапись:
1. «Сумма координат меняется на 1 при изменении одной из них на 1»;
2. «Количество компонент связности: убираем спички и ломаем шоколадку на дольки»;
3. «Рёбер у дерева на 1 меньше, чем вершин»;
4. «Перекрашивание полоски»;
5. «Наименьшее количество количество перекрашиваний»;
6. «Меняя за одну операцию соседние крестик и нолик, собрать крестики справа (вариант: вместе)»;
7. «Две задачи»;
8. «Ромбы трёх типов, кубики, высота»;
9. «Журнал «Квант»»;
10. «Расстояния между вершинами графа»;
11. «Перестановки и «метод пузырька»»;
12. «Количество беспорядков (инверсий). Чётность перестановки»;
13. «Меняем местами за одну операцию не обязательно соседние, а любые две книги»;
14. «Разложение перестановки на непересекающиеся циклы. Декремент — разность между количествами книг и циклов».

Лекция 16 (435) 24.02.2018

Александр Васильевич СПИВАК,

автор книг «1001 задача по математике», «Математический кружок», «Математический праздник», «Турниры математических боёв имени А.П. Савина», «Арифметика» и «Арифметика—2».

Пари для простаков

В пятом номере «Кванта» 1987 года в статье П.А. Певзнера «Лучшее пари для простаков» рассказано о формуле Конвея, которая для любых двух разных слов A и B одинаковой длины, состоящих из букв О (орёл) и Р (решка), даёт вероятность выигрыша в придуманной в 1969 году Вальтером Пеннеем игре. Игра вот какая: бросают монетку и записывают результаты. Как только оказывается выписано слово A, победителем объявляют первого игрока, а если до этого успевает появиться слово B, то победителем объявляют второго игрока.

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

Есть видеозапись:
1. «Walter Penney. Двухбуквенные слова»;
2. «Самого выгодного трёхбуквенного слова нет»;
3. «Уравнения на вероятности: ОРО и ООР»;
4. «Начала моих выигрышей, начала Ваших, все неоконченные. РРО и РОО»;
5. «Марковские цепи (РРО и РОО)»;
6. «ООР и РОО по Конвею»;
7. «Марковская цепь для ООР и РОО»;
8. «Любое слово рано или поздно появится»;
9. «РООРОО и ООРООР»;
10. «Многочлены и формула Конвея»;
11. «Как выбрать наилучшее слово, побеждающее данное слово?»

Лекция 17 (436) 3.03.2018

Сергей Владимирович КОНЯГИН,

академик Российской академии наук, заведующий отделом теории чисел Математического института имени В.А. Стеклова.

Суммы и произведения (по модулю)

Лекция является продолжением лекции Ильи Дмитриевича Шкредова, прочитанной 14.10.2017.

Есть видеозапись:
27. «Сумма множеств»;
28. «Наименьшее возможное количество элементов суммы — у арифметической прогрессии»;
29. «Наименьшее возможное количество элементов произведения»;
30. «Гипотеза Эрдёша-Семериди»;
31. «Недистрибутивность»;
32. «Теорема о количестве элементов»;
33. «Количество элементов суммы, делённой на сумму»;
34. «Остатки от деления на данное число»;
35. «Гипотеза Эрдёша-Семериди для остатков»;
36. «Количество элементов множества A(A - A + A - A) + A(A - A)»;
37. «Сумма четырёх произведений элемента на разность двух элементов».

Лекция 18 (437) 10.03.2018

Александр Игоревич БУФЕТОВ,

ведущий научный сотрудник Математического института имени В.А. Стеклова и Института проблем передачи информации имени А.А. Харкевича, профессор Российской академии наук, исследователь Национального центра научных исследований во Франции (CNRS), лауреат премии имени С.В. Ковалевской.

Интерполяционная формула Лагранжа. Теорема Виета

Как найти многочлен, принимающий в данных точках данные значения? Как найти коэффициенты многочлена, зная его корни и старший коэффициент?

Есть видеозапись:
1. «Интерполяционная формула Лагранжа»;
2. «Теорема Виета».

Лекция 19 (438) 17.03.2018

Юрий Михайлович БУРМАН,

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

Перестановки и графы на поверхностях

Есть неожиданная связь между кратчайшими способами расставлять книги на книжной полке и кругами с деревьями. Точнее, «на более математическом языке» — между циклическими перестановками и деревьями, вложенными в круг. Лекция объясняет эту связь. К концу лекции графы перестают быть деревьями, а круг превращается в «сферу с ручками».

Есть видеозапись:
15. «Перестановки. Разложение на циклы»;
16. «Транспозиция. Композиция перестановок. Некоммутативность»;
17. «Дерево, вписанное в окружность»;
18. «Деревья транспозиций. Циклы. Изолированные вершины»;
19. «Склеивание вписанных в окружности деревьев».

Лекция 20 (439) 24.03.2018

Сергей Борисович ГАШКОВ,

профессор кафедры дискретной математики мехмата МГУ, автор книг «Арифметика. Алгоритмы. Сложность вычислений», «Элементарное введение в эллиптическую криптографию», «Криптографические методы защиты информации», «Современная элементарная алгебра в задачах и упражнениях», «Системы счисления и их применения».

Числа Стирлинга. Числа Белла. Треугольник Пирса

В терминах размещений шаров по ящикам легко сформулировать 12 разных комбинаторных задач. Самые важные из них приводят к простейшим комбинаторным числам: размещениям, перестановкам и сочетаниям. А другие задачи ведут к более сложным и менее известным комбинаторным задачам, например, к числам Стирлинга.

Узнали, как треугольник Пирса помогает вычислять числа Белла.

Есть видеозапись:
1. «Шары и ящики»;
2. «Числа Стирлинга (количества разбиений на подмножества)»;
3. «Рекуррентные формулы для биномиальных коэффициентов и чисел Стирлинга»;
4. «Треугольники Паскаля и Стирлинга. Числа Белла»;
5. «Рекуррентная формула для чисел Белла»;
6. «Треугольник Пирса»;
7. «Джеймс Стирлинг»;
8. «Бенджамин Пирс и его сын Чарльз Сандерс»;
9. «Выражение степеней через убывающие степени и числа Стирлинга»;
10. «От комбинаторного определения к алгебраическому»;
11. «Многомерный куб и числа Стирлинга».

Лекция 21 (440) 31.03.2018

Станислав Валерьевич ШАПОШНИКОВ,

профессор кафедры математического анализа мехмата МГУ и Высшей школы экономики, лектор Независимого московского университета, лауреат премии правительства Москвы для молодых учёных.

Монета и равномерное распределение

Случайность и вероятность. Моделирование бросания правильной монеты. Равномерно распределенные последовательности.

Есть видеозапись:
1. «Случайность как непредсказуемость»;
2. «Случайность как сложность»;
3. «Вероятности»;
4. «Два независимых броска монеты»;
5. «Многократное бросание монеты. Числа сочетаний и бином Ньютона»;
6. «Маловероятные события не невозможны»;
7. «Изготовление честной монеты»;
8. «Точки отрезка и двоичная система счисления»;
9. «Двоичная система счисления и равномерно распределённая случай»;
10. «Явно определённая и случайно распределённая на отрезке последовательность»;
11. «Случайная величина. Среднее значение»;
12. «Среднее значение и его линейность»;
13. «Сто писем и сто ящиков»;
14. «Дисперсия. Чебышёв»;
15. «Неравенство Чебышёва»;
16. «Отклонение частоты от вероятности, или Закон больших чисел как следствие неравенства Чебышёва»;
17. «Заяц и ручей».

Лекция 22 (441) 7.04.2018

Андрей Михайлович РАЙГОРОДСКИЙ,

доктор физико-математических наук.

Остроугольные треугольники

Дмитрий Захаров, будучи учеником 10-го класса, построил пример множества точек в n-мерном пространстве, в котором не менее 2^n/2 остроугольных треугольников.

Советую популярную статью.

Есть видеозапись:
1. «Три на плоскости, пять в пространстве»;
2. «Теорема косинусов. Скалярное произведение»;
3. «Остроугольные треугольники в многомерном пространстве»;
4. «Эрдёш, Данцер и Грюнбаум, Фюреди»;
5. «Невероятностный метод: Захаров, Геренчер и Харанги»;
6. «Удвоение количества точек».

Лекция 23 (442) 14.04.2018

Станислав Валерьевич ШАПОШНИКОВ,

профессор кафедры математического анализа мехмата МГУ и Высшей школы экономики, лектор Независимого московского университета, лауреат премии правительства Москвы для молодых учёных.

Равномерное распределение и непрерывные функции

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

Для понимания необходимо знать лекцию 440 (31 марта 2018 года), в частности, что такое среднее значение и дисперсия случайной величины, а также закон больших чисел Чебышёва.

Есть видеозапись:
18. «Начальные цифры десятичной записи степеней числа 2»;
19. «Биллиард. Равномерно распределённая последовательность»;
20. «Индикатор»;
21. «Сумма геометрической прогрессии»;
22. «Сумма синусов, сумма косинусов»;
23. «Приближаем индикатор непрерывной функцией, а её — синусами и косинусами»;
24. «Площадь под графиком (интегралы от синуса и косинуса)»;
25. «Критерий Вейля равномерного распределения»;
26. «Применяем критерий Вейля к последовательности дробных частей кратных данного иррационального числа»;
27. «Герман Вейль (1885-1955)»;
28. «Карл Вейерштрасс и Сергей Натанович Бернштейн»;
29. «Теорема Вейерштрасса о приближении непрерывной функции многочленами. Многочлены Бернштейна»;
30. «Приближение непрерывной периодической функции тригонометрическими многочленами».

Лекция 24 (443) 21.04.2018

Сергей Владимирович ДВОРЯНИНОВ,

кандидат физико-математических наук, доцент, автор статей журналов «Квант», «Потенциал», «Фрактал», «Математическое образование», «Математика в школе», «Математика для школьников», «Физика для школьников», «Математика», «Квантик».

Фазовый портрет маятника. Перевалы. Эллипсоиды и сферы. Эффект Джанибекова. Вселенная Фридмана

Рассказ о книге В.И. Арнольда «Математическое понимание природы». Показаны опыты с движущимися и летающими моделями и дано математическое толкование наблюдаемых явлений. Советую прочитать статью в первом номере «Кванта» 2017 года.

Есть видеозапись:
11. «Фазовый портрет математического маятника»;
12. «Вращаем и бросаем кирпичи, или Эффект Джанибекова»;
13. «Вращаем и бросаем (вторая камера)»;
14. «Эллипсоиды и сферы.Эффект Джанибекова»;
15. «Потенциальный барьер, или Чайная ложечка в дрожащем блюдце»;
16. «Вселенная Фридмана—Леметра—Робертсона—Уокера».

Лекция 25 (444) 12.05.2018

Александр Чедович ПИПЕРСКИ,

германист, научный сотрудник и преподаватель Высшей школы экономики, доцент Института лингвистики РГГУ, кандидат филологических наук, автор книги «Конструирование языков: от эсперанто до дотракийского», один из редакторов-составителей книги «Лингвистика для всех. Летние лингвистические школы 2009—2011», лауреат премии «Просветитель».

Как и зачем считать частотность слов в текстах?

Каждый из нас интуитивно понимает, что бывают слова частые и редкие. Это знание вполне можно применить на практике — например, составить частотный словарь и использовать его в преподавании иностранного языка. Правда, оценивать частотность, просто посчитав количество тех или иных слов в тексте, опасно: отдельные тексты, в которых часто встречается какое-нибудь слово, могут искажать картину. Рассказан математический метод, которые позволяет бороться с такими перекосами. За рамками лекции осталось обсуждение того, как эти перекосы можно интерпретировать и автоматически составить список ключевых слов текста.

Есть pdf-конспект лекции и такого же содержания pptx-файл.

Есть видеозапись:
1. «Случай с Оливером»;
2. «Я Вас любил...»;
3. «Частотный словарь Ляшевской и Шарова: и, в, не, на, я, быть, он, с, что, а»;
4. «Распределение Ципфа (1902—1950)»;
5. «Меняем показатель степени»;
6. «Уникальность половины слов»;
7. «Метан»;
8. «Среднее время ожидания автобуса»;
9. «Применения частотных словарей».

Лекция 26 (445) 19.05.2018

Даниил Владимирович МУСАТОВ,

кафедра дискретной математики Московского физико-технического института.

Пропорциональные правила представительства

Пусть некоторые группы должны быть представлены в парламенте пропорционально некоторым величинам. Это могут быть, например, партии и голоса на выборах, или регионы и население. Обычно число мест в парламенте фиксировано, так что доли неизбежно придётся округлять. Но каким образом? На этот счёт есть несколько неэквивалентных правил, каждое из которых имеет свои недостатки. Мы подробно изучим эти правила и возникающие при их использовании парадоксы, а также докажем теорему о том, что идеального правила не бывает.

Есть видеозапись:
0. «Даниил Владимирович Мусатов и комбинаторные школы в Берендеевых полянах»;
1. «Первое вето первого президента США Джорджа Вашингтона. Правило Джефферсона»;
2. «Каталония и Мадрид»;
3. «Правило Уэбстера и возврат к правилу Гамильтона»;
4. «Парадокс Алабамы»;
5. «Парадокс населения»;
6. «Парадокс нового штата — парадокс Оклахомы»;
7. «Правило Хилла»;
8. «Теорема Балинского-Янга»;
9. «Принятие решений. Нетранзитивность»;
10. «Теорема Эрроу»;
11. «Идея доказательства теоремы Эрроу».

Советую статью Валерия Фёдоровича Пахомова «Демократия с точки зрения математики» («Квант», 9 и 10 номера 1992 года).