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

Лекция 1 (446) 15.09.2018

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

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

Инварианты узлов. Суммы Кауффмана и инвариант Джонса

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

Есть видеозапись:
1. «Узлы и зацепления. Преобразования Рейдемейстера»;
2. «Инварианты зацеплений»;
3. «Сумма Кауффмана»;
4. «Второе преобразование Рейдемейстера и сумма Кауффмана»;
5. «Первое преобразование Рейдемейстера и сумма Кауффмана»;
6. «Алексей Брониславович Сосинский»;
7. «Из закрученности зацепления и суммы Кауффмана создаём инвариант Джонса»;
8. «Инвариант Джонса трилистника»;
9. «Распутывающее соотношение для инварианта Джонса»;
10. «Распутывающее соотношение Конвея»;
11. «Третье преобразование Рейдемейстера и сумма Кауффмана».

Лекция 2 (447) 22.09.2018

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

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

Количества целых точек в многоугольниках и многогранниках, или Формулы Пика. Теорема Эрхарта-Макдональда

Сколько точек с целыми координатами лежит внутри многоугольника (или многогранника), координаты всех вершин которого — целые числа? А сколько на границе? Как эти количества связаны с площадью (объёмом)? А.Г. Кушниренко в статье «Целые точки в многоугольниках и многогранниках» объяснил, как выглядят всевозможные формулы такого типа.

Количество внутренних точек инвариантно, но не аддитивно, поскольку в формуле включений-исключений для этой функции должен бы стоять знак сложения вместо знака вычитания. Но если мы домножим количество внутренних точек на минус единицу, возведённую в степень, равную размерности, в которой мы эти самые внутренние точки рассматриваем, то функция становится аддитивной! Таким образом мы получаем крайне короткое и прозрачное доказательство теоремы Эрхарта-Макдональда о количестве внутренних точек.

Есть видеозапись:
1. «Формула Пика для площади многоугольника»;
2. «Точка, отрезок и треугольник. Аддитивные инвариантные функции»;
3. «Выражаем стандартный базис через 1, N и S»;
4. «Формулы Пика и теорема Эрхарта-Маклорена для плоскости»;
5. «Формула Пика для трёхмерного пространства»;
6. «Функция B в трёхмерном случае»;
7. «Неаддитивность функции I»;
8. «Теоремы Эрхарта-Макдональда доказательство»;
9. «Теорема Эрхарта-Макдональда и системы неравенств»;
10. «Обсуждение короткого доказательства теоремы Эрхарта-Макдональда»;
11. «Идея Стивена Сэма доказательства теоремы Эрхарта-Макдональда»;
12. «Парадоксальное сложение, или Целые точки и бесконечные ряды»;
13. «Количество целых точек в сумме Минковского».

Лекция 3 (448) 29.09.2018

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

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

Вычислимое и невычислимое

Все ли математические задачи можно решить? Например, можно ли узнать, разрешимо ли данное уравнение в целых числах или у него нет ни одного такого решения? Можно ли по тексту программы узнать, остановится её работа или будет продолжаться вечно? Что такое перечислимое множество? А что такое разрешимое множество? Логики XIX и XX века нашли ответы на эти казавшиеся несколько философскими вопросы. Вопросы оказались вполне математическими, и столь же чёткими и математическими оказались ответы.

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

Существует перечислимое неразрешимое множество. Более того, существует бесконечный набор перечислимых множеств, не пересекающих друг друга и не отделимых друг от друга.

Есть видеозапись:
1. «Вычислимое и невычислимое»;
2. «Вычислимые функции и перечислимые множества»;
3. «Разрешимые и перечислимые множества»;
4. «Универсальная вычислимая функция»;
5. «Алгоритмическая неразрешимость проблемы остановки»;
6. «Неразрешимое перечислимое множество»;
7. «Во всяком бесконечном перечислимом множестве есть бесконечное разрешимое подмножество»;
8. «Множество нижних точек».

Лекция 4 (449) 6.10.2018

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

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

Тождество Гаусса-Якоби

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

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

Есть видеозапись:
1. «Разбиений на нечётные слагаемые столько же, сколько на попарно различные»;
2. «Пентагональное тождество Эйлера»;
3. «Количество разбиений числа на слагаемые»;
4. «Комбинаторное доказательство пентагонального тождества Эйлера»;
5. «Тождество Гаусса-Якоби»;
6. «Комбинаторное доказательство тождества Гаусса-Якоби».

Лекция 5 (450) 13.10.2018

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

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

Что такое доказательство? Теорема Гёделя о неполноте

Это вторая лекция из цикла лекций по математичеcкой логике. Советую сначала послушать прочитанную 29 сентября 2018 года первую лекцию, особенно с учётом того, что они обе являются подготовительными к лекциям В.Е. Плиско (20 и 27 октября 2018 года) и к лекциям Л.Д. Беклемишева (2 и 23 марта 2019 года) и С.Л. Кузнецова (20 апреля 2019 года).

Советую брошюру В.А. Успенского «Теорема Гёделя о неполноте» и трёхтомник Н.К. Верещегина и А.Х. Шеня «Лекции по математической логике и теории алгоритмов».

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

Лекция 6 (451) 20.10.2018

Валерий Егорович ПЛИСКО,

кандидат физико-математических наук, доцент мехмата МГУ, автор учебных пособий «Вводный курс математической логики», «Теория алгоритмов», «Интуиционистская логика», «Математическая логика и теория алгоритмов».

Конструктивная логика

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

Есть видеозапись:
1. «Возведение иррационального числа в иррациональную степень»;
2. «Основания математики: множества»;
3. «Парадокс Рассела»;
4. «Интуиционизм»;
5. «Вещественные числа и интуиционизм»;
6. «Аксиомы и правило вывода классической логики высказываний»;
7. «Исчисление Колмогорова. Интуиционистское исчисление. Не высказывания, а задачи!»;
8. «Модель интуиционистского исчисления высказываний»;
9. «"Интуиционистская логика" В.Е. Плиско и В.Х. Хаханяна».

Лекция 7 (452) 27.10.2018

Валерий Егорович ПЛИСКО,

кандидат физико-математических наук, доцент мехмата МГУ, автор учебных пособий «Вводный курс математической логики», «Теория алгоритмов», «Интуиционистская логика», «Математическая логика и теория алгоритмов».

Конструктивная логика

Вторая часть лекции.

Есть видеозапись:
10. «Интуиционистское исчисление высказываний (напоминание и пример вывода)»;
11. «Вывод из гипотез и другие способы построения выводов»;
12. «Модели Крипке»;
13. «Доказательства невыводимости при помощи моделей Крипке»;
14. «Теорема Гливенко»;
15. «Интуиционистское исчисление предикатов»;
16. «Модели Крипке и предикаты»;
17. «Конструктивная семантика».

Лекция 8 (453) 3.11.2018

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

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

Малая теорема Ферма и символ Лежандра

Предварительная лекция к рассказу Ильи Дмитриевича Шкредова о методе тригонометрических сумм.

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

Есть видеозапись:
0. «Илья Дмитриевич Шкредов и его лекции о тригонометрических суммах»;
1. «Таблица умножения и малая теорема Ферма»;
2. «Цикличность мультипликативной группы вычетов по простому модулю, или Первообразный корень»;
3. «Порядок ненулевого остатка по простому модулю»;
4. «Простые делители значений многочлена деления круга на 5 частей»;
5. «Если степень числа 2 в сумме с числом 1 делится на показатель степени, то он делится на 3»;
6. «Делители произведения двух последовательных натуральных чисел, увеличенного на 1»;
7. «Функция Эйлера»;
8. «Доказательство существования первообразного корня индукцией по делителям количества элементов мультипликативной группы вычетов по простому модулю»;
9. «Символ Лежандра. Формула Эйлера. Квадратичные вычеты и невычеты»;
10. «Пояснение к выводу мультипликативности символа Лежандра из формулы Эйлера»;
11. «Первое дополнение к квадратичному закону взаимности»;
12. «Второе дополнение к квадратичному закону взаимности».

Лекция 9 (454) 10.11.2017

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

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

Тригонометрические суммы

Рассказ об очень мощном методе теории чисел — методе тригонометрических сумм. С его помощью было доказано, например, что любое нечётное число, начиная с 7, есть сумма трёх простых, любое число, большее 13792, есть сумма 16 четвёртых степеней, а также решены многие другие аддитивные задачи.

Было введено дискретное преобразование Фурье на кольце вычетов по простому модулю. На следующей лекции будут рассмотрены некоторые несложные тернарные аддитивные задачи в конечном поле и будет доказан результат И.М. Виноградова о минимальном квадратичном невычете.

Для понимания лекции необходимо знать, что такое малая теорема Ферма, символ Лежандра, комплексное число.

Есть видеозапись:
13. «Интересные теоремы, доказанные при помощи тригонометрических сумм»;
14. «Квадратичные вычеты и невычеты, символ Лежандра»;
15. «Формула Эйлера и мультипликативность символа Лежандра»;
16. «Граф Пэли»;
17. «Количество общих соседей двух вершин графа Пэли»;
18. «Максимальный полный подграф графа Пэли»;
19. «Экспонента чисто мнимого числа. Сумма степеней корня из 1»;
20. «Дискретное преобразование Фурье»;
21. «Равенство Планшереля»;
22. «Свёртка»;
23. «Начало доказательства теоремы о количестве элементов полного подграфа графа Пэли: свёртка при преобразовании Фурье соответствует произведению»;
24. «Преобразование Фурье символа Лежандра — сумма Гаусса»;
25. «Завершение доказательства оценки сверху количества вершин полного подграфа графа Пэли».

Лекция 10 (455) 17.11.2018

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

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

Задача Наполеона, интерполяционная формула Лагранжа и преобразование Фурье, или Где Сатурн?

Предварительная лекция к второй части рассказа Ильи Дмитриевича Шкредова о методе тригонометрических сумм. Повторили — с гораздо более «школьной» точки зрения — определение и свойства дискретного преобразования Фурье.

Есть видеозапись:
26. «Земля и Сатурн, задача Наполеона, манная каша»;
27. «Комплексные числа и задача Наполеона»;
28. «Постановка задачи о пиближении треугольника правильным треугольником»;
29. «Обсуждение приближения данного треугольника правильным»;
30. «Интерполяционная формула Лагранжа, или Где Сатурн?»;
31. «Корни из 1. Обратное и прямое дискретные преобразования Фурье»;
32. «Произведений расстояний от вершины правильного многоугольника до других вершин»;
33. «Пример: преобразование Фурье для 3»;
34. «Манная каша»;
35. «Равенство Планшереля».

Лекция 11 (456) 24.11.2018

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

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

Тригонометрические суммы

Продолжение лекции 10.11.2018. Напомнив, что такое модуль гауссовой суммы и формула обращения, поняли, как оценивать величину минимального квадратичного невычета (это почти то же, что было 10.11.2018, но повторили для ясности), и доказали, рассматривая суммы Якобсталя, что любое простое, дающее остаток 1 по модулю 4, есть сумма квадратов двух целых чисел.

Можете познакомиться с вопросами аналогичного курса 2015 года. (Разумеется, в этом году не всё в точности так, как было тогда.)

Есть видеозапись:
36. «Минимальный квадратичный невычет. Теорема Бёрджесса»;
37. «Напоминания»;
38. «Свёртка символа Лежандра с 1 и с самим собой. Модуль суммы Гаусса»;
39. «Наименьший квадратичный невычет»;
40. «Сумма значений символа Лежандра от многочлена второй степени»;
41. «Суммы Якобсталя и теорема Ферма-Эйлера о представимости простого числа, дающего остаток 1 при делении на 4, в виде суммы двух квадратов»;
42. «Идея доказательства теоремы Шура».

Лекция 12 (457) 24.11.2018

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

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

Замощения плоскости

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

Есть видеозапись:
1. «Квадратные плитки с окрашенными сторонами. Период замощения»;
2. «Периодическое и непериодическое замощения»;
3. «Набор из 4 плиток»;
4. «Формулировка теоремы о существовании системы плиток, копиями которых можно покрыть плоскость, но только непериодически. Одномерный случай»;
5. «Если для некоторой системы плиток существует замощение, выдерживающее перенос на ненулевой невертикальный вектор, то существует и замощение, выдерживающее переносы на тот же вектор и на некоторый вертикальный (а тогда и горизонтальный) вектор»;
6. «Умножение на 3 или деление на 2»;
7. «Идея системы плиток, которыми можно только непериодически покрыть плоскость»;
8. «Плитки, копиями которых можно покрыть плоскость, но только непериодически»;
9. «Плитки Аммана. 13, 12 и 11 плиток. Машины Тьюринга».

Лекция 13 (458) 1.12.2018

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

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

Тождество Гаусса-Якоби

Разобрали алгебраическое доказательства тождества Якоби. Вывели из него тождество Гаусса. Узнали, как крестики-нолики позволяют закодировать диаграмму Юнга и как связаны доказательства Лейбензона и Титенко.

Есть видеозапись:
7. «Алгебраическое доказательство тождества Якоби»;
8. «Тождество Гаусса»;
9. «Новый вид тождества Якоби, или Задача М1065»;
10. «Крестики и нолики»;
11. «Как по крестикам-ноликам построить диаграмму Юнга? А диаграмму с треугольным носом?»;
12. «Задача М737».

Лекция 14 (459) 8.12.2018

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

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

Суммы Гаусса. Приближение произвольного треугольника равносторонним

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

Есть видеозапись:
43. «Задача М50»;
44. «Разложение на простейшие дроби»;
45. «Оценка сверху суммы значений символа Лежандра от подряд идущих чисел»;
46. «Сумма Якобсталя, малая теорема Ферма и бином Ньютона»;
47. «Квадратичный закон взаимности и гауссовы суммы»;
48. «Квадрат гауссовой суммы»;
49. «q-я степень гауссовой суммы и квадратичный закон взаимности»;
50. «Приближаем произвольный треугольник равносторонним».

Лекция 15 (460) 15.12.2018

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

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

Тождество Гаусса-Якоби

Ещё раз посмотрели на крестики-нолики и узнали, насколько тесно связаны они с диаграммами Юнга. Вывели следствие из тождества Гаусса-Якоби. Разобрали комбинаторное доказательство тождества Гаусса-Якоби, связанное с параболами и векторами, то есть решили задачу М1086.

Есть видеозапись:
13. «Повторение: крестики-нолики и диаграммы Юнга, умножение рядов и комбинаторное доказательство»;
14. «Отражение относительно диагонали соответствует замене крестиков на нолики, ноликов на крестики и изменению направления чтения»;
15. «Подставляем u = v»;
16. «Суммы векторов и раскрытие скобок, или Переформулировка задачи М1065»;
17. «Разбиения числа на слагаемые и системы векторов»;
18. «Биекция между системами векторов, или Завершение решения задачи М1065».

Лекция 16 (461) 15.12.2018

Сергей Валерьевич МАРКЕЛОВ,

учитель школы № 57.

Открытые проблемы элементарной геометрии

Вот несколько примеров неподдающихся задач.

• Каково минимальное число цветов, в которые можно так раскрасить плоскость, чтобы концы любого отрезка длины 1 были покрашены в разные цвета?
• Существует ли раскраска точек пространства в 14 цветов, при которой концы любого отрезка длины 1 одного цвета?
• Сколько точек общего положения должно быть отмечено на плоскости, чтобы среди них непременно нашлись вершины выпуклого шестиугольника?
• В любом ли многоугольнике с зеркальными изнутри сторонами можно так разместить лампочку, чтобы он был освещён весь?
• Можно ли несколькими кругами, зеркальными снаружи, не пересекающими друг друга и даже не касающимися, загородить горящую лампочку?
• В любом ли многоугольнике с зеркальными сторонами существует хотя бы один замкнутый путь светового луча?
• Существует ли многоугольник, копиями которого плоскость можно покрыть, но только непериодическим образом?
• Может ли выпуклый многогранник, которым можно замостить всё пространство, иметь больше 38 граней?
• Какова фигура минимальной площади, которой можно покрыть любой многоугольник диаметра 1?
• Какова фигура минимальной площади, которой можно покрыть любую фигуру периметра 1?
• Сколь велика может быть площадь n-угольника диаметра 1 при данном n?
• У любого ли выпуклого многогранника существует развёртка без самопересечений?
• Рассмотрим n точек, не лежащих на одной прямой. Обязательно ли среди них найдётся точка, через которую проходит не менее ⁿ/₃ прямых, соединяющих её с остальными n – 1 точками?

Лекция 17 (462) 9.02.2019

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

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

P и NP

Что такое сложность вычисления? Полиномиальные алгоритмы. Существуют ли задачи, которые нельзя решить за полиномиальное время, но ответ которых проверить за полиномиальное время можно?

Есть видеозапись:
0. «Даниил Владимирович Мусатов»;
1. «Эйлеровы пути»;
2. «Критерий существования эйлерова пути»;
3. «Полиномиальное время работы»;
4. «Гамильтоновы пути и перебор»;
5. «Раскраски»;
6. «Составление расписания»;
7. «Разложения чисел на множители и криптография»;
8. «P и NP».

Лекция 18 (463) 9.02.2019

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

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

Целые и дробные части

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

Предварительно рассмотрели многие другие задачи о целых и дробных частях, например, нашли явную формулу для последовательности 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ... , в которой каждое натуральное число встречается столько раз, каково оно само.

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

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

Есть видеозапись:
1. «Целая часть числа, или Пол (floor) и потолок (ceiling)»;
2. «Последовательность 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, ..., в которой каждое число встречается столько раз, каково оно»;
3. «Теорема лорда Рэлея»;
4. «Два примера: целые части кратных корня из 2 и целые части кратных золотого сечения (игра цзяньшицзы)»;
5. «Одна из подготовительных задач "Сборника задач московских математических олимпиад"»;
6. «Предметы по колонкам, или Деление с остатком»;
7. «Закон взаимности»;
8. «Несколько примеров»;
9. «Замкнутая ломаная из хорд одной длины»;
10. «Закон взаимности доказываем, вычисляя сумму явным образом»;
11. «Числа Кнута (определение)»;
12. «Каждое число Кнута больше своего номера»;
13. «Расстояние до ближайшего целого числа и сумма ряда».

Лекция 19 (464) 16.02.2019

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

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

Автостоянки, перестановки и деревья

Автомобильная стоянка — это ряд из n мест, занумерованных числами от 1 до n; въехав на стоянку, автомобиль может двигаться только вперёд. При въезде на стоянку скопилась очередь из n машин. У каждой машины есть «любимое место». Вначале машина подъезжает к любимому месту. Если оно свободно, то машина там и стоит; если занято — едет вперёд до ближайшего свободного места. Возможна ситуация, когда не всем удастся встать на стоянку: очередная машина обнаружит своё любимое место занятым, а свободных мест впереди уже не останется. Задача о количестве последовательностей любимых мест, для которых конфликт не возникает, связана с замечательным разделом математики — комбинаторикой деревьев.

С содержанием лекции можно познакомиться по статье Ю.М. Бурмана и А.В. Спивака «Автостоянки, перестановки и деревья» в четвёртом номере журнала «Квант» за 2004 год.

Есть видеозапись:
1. «Бесконфликтные очереди»;
2. «Количество бесконфликтных очередей, или Кольцевая автостоянка»;
3. «Перестановки»;
4. «Количество инверсий в перестановке. Производящая функция»;
5. «Числа Каталана и бесконфликтные очереди»;
6. «Дерево Каталана»;
7. «Монотонные деревья и перестановки»;
8. «Код Прюфера»;
9. «Деревья и бесконфликтные очереди».

Лекция 20 (465) 2.03.2019

Лев Дмитриевич БЕКЛЕМИШЕВ,

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

Теорема Гёделя о неполноте

Формулировка и начало доказательства теоремы Гёделя о неполноте. Очень полезно перед лекцией прочитать брошюру В.А. Успенского «Теорема Гёделя о неполноте» и посмотреть записи лекций 29.09.2018 и 10.10.2018.

Советую посмотреть статью «Теоремы Гёделя о неполноте и границы их применимости».

Есть видеозапись:
1. «Формальные аксиоматические теории»;
2. «Арифметика Пеано»;
3. «Гёделева нумерация и парадокс лжеца»;
4. «Идея Гёделя»;
5. «Первая теорема Гёделя о неполноте»;
6. «Парадокс Греллинга-Нельсона: рефлексивно ли слово НЕРЕФЛЕКСИВНЫЙ?»

Лекция 21 (466) 16.03.2019

Виктор Эдуардович МАТИЗЕН,

кинообозреватель газеты «Новые Известия», глава гильдии киноведов и кинокритиков России, выпускник ФМШ при НГУ, мехмата НГУ и ВГИКа, автор более 1000 публикаций о кино. В 1986 году выпустил книгу «Жизнь шкрабов», во многом основанную на опыте учительской работы. Автор статей «Найдём ошибку» (1980 год, 10 номер журнала «Квант»), «Равногранные и каркасные тетраэдры» (1983 год, 7 номер), «О пользе скатывания шариков» (1980 год, 5 номер), «Перекатывание многогранников» (1989 год, 5 номер), соавтор (с В.Н. Дубровским) статьи «Из геометрии тетраэдра» (1988 год, 9 номер), автор задач 549, 833, 1039, 1067, 1139 «Задачника "Кванта"».

Перекатывания многогранника

Как-то раз лектор со своими учениками кантовал тяжёлые каменные обломки. Другой повод — строгая надпись на таре для стеклянных изделий: «НЕ КАНТОВАТЬ!». Лекция посвящена следующим вопросам:

1. что представляет собой множество следов вершин (рёбер, граней) выпуклого многогранника при всевозможных его перекатываниях по плоскости через ребра (из некоторого начального положения)?
2. что такое бесконечно продолженная развёртка выпуклого многогранника?
3. в частности, для каких многогранников множество следов вершин дискретное, а для каких оно заполняет плоскость всюду плотно?

Есть брошюра и видеозапись:
1. «Кантуем камни»;
2. «Проворачиваем многогранник вокруг его вершины»;
3. «Параллельные переносы. Повороты на 60, 90, 120 градусов»;
4. «Рациональность тангенсов углов треугольника»;
5. «Верёвки и жёсткость».

Лекция 22 (467) 16.03.2019

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

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

Внешние и внутренние касательные к двум кривым. Теорема Фабрициуса-Бьерре

Количество внешних касательных двух гладких кривых общего положения равно сумме количества внутренних касательных и количества точек пересечения этих кривых. Следствие — формула Фабрициуса-Бьерре: количество внешних касательных гладкой замкнутой кривой общего положения равно сумме количества её внутренних касательных, числа точек самопересечения и половины числа точек перегиба.

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

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

Есть видеозапись:
1. «Внешние и внутренние касательные. Число точек пересечения двух кривых»;
2. «Фабрициуса-Бьерре формула»;
3. «Кривые с остриями (точками возврата)»;
4. «Кривые на сфере».

Лекция 23 (468) 16.03.2019

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

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

Гауссовы биномиальные коэффициенты

Диаграммы Юнга дают обобщение треугольника Паскаля — гауссовы биномиальные коэффициенты.

Есть видеозапись:
19. «Гауссовы биномиальные коэффициенты»;
20. «Возвратность и унимодальность»;
21. «Рекуррентная формула для гауссовых биномиальных коэффициентов»;
22. «Перестановки и инверсии. Гауссов факториал. Формула для гауссова биномиального коэффициента»;
23. «Тождество Чжу (1303) и Вандермонда (1772)»;
24. «Очевидное доказательство тождества Чжу и Вандермонда»;
25. «Переходим в формуле для гауссова числа сочетаний к пределу»;
26. «Алгебраическое доказательство коммутативного гауссова бинома»;
27. «Комбинаторное доказательство коммутативного гауссова бинома»;
28. «Вывод тождества Гаусса-Якоби из коммутативного гауссова бинома»;
29. «Пентагональное тождество Эйлера»;
30. «Ещё одно следствие и два упражнения».

Продолжение рассказа о теореме Гёделя о неполноте. Советую прочитать брошюру В.А. Успенского «Теорема Гёделя о неполноте».

Есть видеозапись:
7. «Напоминание (план доказательства первой теоремы Гёделя о неполноте)»;
8. «Ограниченные кванторы. Сигма- и дельта-формулы, перечислимые и разрешимые множества»;
9. «Нумерация пар натуральных чисел»;
10. «Конечные подмножества натурального ряда и двоичная система счисления»;
11. «Кодирование последовательностей, формул, выводов».

Лекция 25 (470) 30.03.2019

Сергей Константинович ЛАНДО,

автор книги «Лекции о производящих функциях», профессор Высшей школы экономики.

Каустика

Что такое каустики, знает всякий, кто когда-либо выжигал по дереву, собирая солнечные лучи с помощью линзы, видел световые блики на дне неглубокого водоёма от ряби на поверхности воды или наблюдал игру света, отражающегося от дна чашки. Латинское слово «каустик» означает «жгучий», и им называют множество тех точек в пространстве, в которых собирается больше лучей какого-либо светового потока, чем в соседних точках.

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

Есть видеозапись:
1. «Каустики»;
2. «Окружность, соприкасающаяся с параболой в вершине параболы»;
3. «Эволюта параболы»;
4. «Эволюта эллипса»;
5. «Огибающая перпендикуляров»;
6. «Множество центров кривизны для эллипсоида».

Лекция 26 (471) 6.04.2019

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

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

Вероятности

Задача о разделе ставки, проверка натурального числа на простоту, универсальная хэш-функция, несжимаемость случайно выбранного слова, парадокс Байеса о диагностике редких заболеваний, тест Фишера, критерий Манна-Уитни, критерий знаков.

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

Лекция 27 (472) 13.04.2019

Виктор Матвеевич БУХШТАБЕР,

профессор кафедры высшей геометрии и топологии мехмата МГУ, член-корреспондент Российской академии наук.

Многогранники и фуллерены

Есть слайды лекции и видеозапись:
1. «Фуллерены»;
2. «Правильные и полуправильные многограннники»;
3. «Выпуклые многогранники и фуллерены»;
4. «Нанотрубки»;
5. «Каирский коврик»;
6. «Статьи и книги».

Лекция 28 (473) 20.04.2019

Степан Львович КУЗНЕЦОВ,

кандидат физико-математических наук, старший научный сотрудник Математического института имени В.А. Стеклова.

Парадоксы и неполнота

Эта лекция продолжает серию лекций по математической логике. Узнаем, как семантические парадоксы — парадокс лжеца, парадокс Карри, парадоксы Берри и Ришара — при их аккуратном прочтении и формализации приводят к разным версиям теоремы Гёделя о неполноте (и в некотором смысле «перестают быть парадоксами»).

Есть видеозапись:
12. «Парадокс лжеца и теорема Тарского о неарифметичности множества истинных высказываний»;
13. «Теоремы Гёделя о неполноте»;
14. «Парадокс Карри и теорема Лёба»;
15. «Теорема о неподвижной точке»;
16. «Парадокс Берри и сложность описания»;
17. «Невычислимость сложности. Парадокс Берри и доказательство Чейтина первой теоремы Гёделя о неполноте»;
18. «Всюду определённые вычислимые функции».

Лекция 29 (474) 27.04.2019

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

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

Разрезания квадрата на n конгруэнтных квадратов и другие задачи на разрезание

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

Есть видеозапись:
1. «Разрезания многоугольников на части»;
2. «Прямоугольник превращаем в квадрат»;
3. «Превращаем несколько конгруэнтных квадратов в квадрат»;
4. «Правильный шестиугольник в квадрат»;
5. «Абуль-Вафа и перекраивание квадрата в несколько конгруэнтных квадратов»;
6. «Любые два многоугольника одной площади равносоставлены»;
7. «Разбиения на непересекающиеся части: Банах и Тарский»;
8. «Поворот, разрезания и параллельные переносы»;
9. «Квадрат в прямоугольник и теорема Банга-Тарского о покрытиях полосками».

Лекция 30 (475) 11.05.2019

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

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

NP-полные задачи

Алгоритмическая задача с ответом «да» или «нет» лежит в классе NP, если для ответа «да» есть короткое и быстро проверяемое доказательство. Примерами служат поиск большого полного подграфа в графе, гамильтонова пути, решение судоку и тому подобное. Будет рассказано, как такие задачи можно сводить одну к другой, и показано существование NP-полных задач, то есть таких, к которым можно свести любую другую.

Продолжение лекции, прочитанной 9 февраля 2019 года.

Есть видеозапись:
9. «Массовые задачи. Распознавание связности графа как пример»;
10. «NP-задачи»;
11. «Сводимость»;
12. «Полный подграф, независимое множество вершин и вершинное покрытие»;
13. «NP-полнота»;
14. «Конъюнктивная и дизъюнктивная формы»;
15. «Сведение задачи о раскраске вершин графа в 3 цвета к задаче о конъюнктивной форме»;
16. «NP-полнота задачи о конъюнктивной форме»;
17. «Сведение любой КНФ к 3-КНФ»;
18. «Формула как дерево. Сведение задачи о выполнимости формулы к задаче о 3-КНФ»;
19. «Сведение задачи о выполнимости 3-КНФ к задаче о независимом подмножестве графа»;
20. «Сведение задачи выполнимости 3-КНФ к задаче о раскраске вершин графа в 3 цвета»;
21. «Сведение задачи о выполнимости 3-КНФ к задаче о рюкзаке»;
22. «Сведение задачи о выполнимости 3-КНФ к поиску ориентированного гамильтонова пути»;
23. «Расщепление каждой вершины графа на вход, тело и выход сводит задачу о гамильтоновом ориентированном пути к задаче о гамильтоновом неориентированном пути».

Лекция 31 (476) 18.05.2019

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

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

Задачник «Кванта»

Разобрали несколько красивых задач журнала «Квант».