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

Лекция 1 (394) 17.09.2016

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

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

Метод Ньютона

Как извлечь квадратный корень из данного положительного числа a? Можно рассмотреть любое положительное число x и вычислить среднее арифметическое между и частным a/x. Неравенство о среднем арифметическом и среднем геометрическом утверждает, что результат не меньше искомого корня. Затем вновь рассмотрим среднее арифметическое между только что вычисленным числом и частным от деления числа a на него, и так далее. Нетрудно доказать, что построенная последовательность стремится к корню из a, причём стремится быстро.

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

Метод Ньютона можно применять не только для поиска действительных корней уравнений, но и для решения сравнений по модулю, являющемуся степенью простого числа.

Есть видеозапись.

Лекция 2 (395) 1.10.2016

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

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

Почему не уменьшается сопротивление?

При увеличении сопротивления любого провода электрической цепи постоянного тока (например, при перерезании провода) сопротивление цепи не может уменьшиться. Эта очевидная для любого физика теорема нуждается в математическом доказательстве. Доказательство основано на рассмотрении квадратичной функции многих переменных: энергии, выделяемой при протекании тока по цепи. Прочитать его можно в первом номере журнала «Квант» 1985 года.

О том, как задача о разрезании прямоугольника на квадраты связана с задачей о вычислении сопротивления, рассказано в статье «Разрезания металлического прямоугольника» третьего номера «Кванта» 2011 года. Есть и чуть более подробная её версия.

Есть видеозапись:
1. «Потенциалы, закон Кирхгофа, альтернатива Фредгольма»;
2. «Мощность и точка минимума квадратичной функции»;
3. «Разрезания металлического прямоугольника».

Лекция 3 (396) 8.10.2016

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

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

Латинские квадраты и устойчивые браки

Представьте квадрат со стороной n, в каждой клетке которого задано некоторое множество, состоящее из n элементов. В 1978 году Джефф Диниц спросил, всегда ли можно выбрать в каждом из этих множеств по одному элементу так, чтобы во всех строках и во всех столбцах выбранные элементы были разными? В 1994 году Фред Галвин дал утвердительный ответ. Доказательство удивительно короткое и неожиданное. Оно использует идею устойчивых паросочетаний. Лекция общедоступна, хотя придумать такое доказательство мог только очень талантливый математик.

Вершины полного двудольного графа, в левой доле которого две вершины, а в правой четыре, можно покрасить в два цвета: левую долю в один цвет, а правую в другой. Но если задать в левой доле {a, b} и {1, 2}, а в правой {a, 1}, {a, 2} и {b, 1}, {b, 2}, то правильная окраска невозможна.

Есть видеозапись:
1. «Латинские квадраты и устойчивые браки»;
2. «Гипотеза о хроматических числах ребёрного графа»;
3. «Алгоритм Форда-Фалкерсона»;
4. «Система различных представителей, или теорема Холла о свадьбе»;
5. «Теорема Кёнига».

Лекция 4 (397) 15.10.2016

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

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

Леса с данным числом деревьев и пронумерованными вершинами

Три доказательства формулы Кэли для числа помеченных деревьев

Есть видеозапись:
1. «Нумерованных деревьев с отмеченными на них началом и концом столько же, сколько отображаний множества вершин в себя»;
2. «Леса с пронумерованными вершинами и бином Ньютона»;
3. «Количество лесов с данным числом деревьев и нумерованными вершинами»;
4. «Удаляем или добавляем рёбра по одному»;
5. «Максимальная антицепь решётки подмножеств».

Лекция 5 (398) 22.10.2016

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

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

Справедливый делёж

Всем известно, как по-честному поделить пирог на две части: один делит, другой выбирает. А что делать, если делящих больше двух? При этом у них разные вкусы и, возможно, внутри пирога есть неделимые объекты. Эту задачу мы рассмотрим с трёх сторон: математической, алгоритмической и игровой. На математическом уровне вопрос только в существовании: можно ли найти делёж, удовлетворяющий определённым свойствам? Например, можно ли добиться, чтобы каждый из участников считал, что получил не менее полагающейся ему части пирога? А можно ли сделать, чтобы никто никому не завидовал? На алгоритмическом уровне вопрос заключается в построении протокола, ищущего подходящий делёж. Желательно, чтобы этот протокол работал достаточно быстро. На игровом уровне возникает такой вопрос: что будет, если участники начнут отклоняться от протокола? Может ли участник получить больше, соврав о своих предпочтениях?

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

Лекция 6 (399) 29.10.2016

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

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

Числа Рамсея

Многие знают утверждение: «Среди любых шести человек некоторые трое попарно знакомы или некоторые трое попарно не знакомы.» Аналогичные утверждения можно доказывать и в случаях, когда, скажем, трое попарно знакомы или семеро попарно не знакомы, либо пятеро попарно знакомы или четверо попарно не знакомы, и так далее. Разумеется, в общем случае потребуется больше, чем 6 человек. Сколько? Это одна из задач теории Рамсея.

Есть видеозапись:
1. «Пятиугольник с красными сторонами и синими диагоналями»;
2. «Число Рамсея R(3,4) больше числа 8»;
3. «Числа Рамсея»;
4. «Число R(3,3,3) не больше числа 17»;
5. «Оценка сверху чисел Рамсея»;
6. «Применяем формулу Стирлинга»;
7. «Оценка снизу числа Рамсея»;
8. «Теорема Рамсея о гиперграфах».

Лекция 7 (400) 12.11.2016

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

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

Двудольные числа Рамсея

Знание материала предыдущей лекции необходимо для понимания этой. Двудольные числа Рамсея отличаются от обычных тем, что полные графы K_n, K_s и K_t заменены на полные двудольные графы K_n,n, K_s,s и K_t,t.

Есть видеозапись:
9. «Числа Рамсея (повторение)»;
10. «Двудольные числа Рамсея»;
11. «Оценка снизу двудольного числа Рамсея»;
12. «Оценка сверху двудольного числа Рамсея».

Лекция 8 (401) 19.11.2016

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

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

Числа Рамсея и поле из 16 элементов

Доказали, что число Рамсея от 3, 3 и 3 равно 17, от 3 и 5 равно 14, а от 4 и 4 равно 18.

Есть видеозапись:
13. «Неравенство Бернулли»;
14. «Выпуклые функции, или Неравенство Йенсена»;
15. «Число Рамсея от 3 и 4 равно 9 (напоминание)»;
16. «R(3,5) = 14 и R(4,4) = 18»;
17. «Напоминание: число R(3,3,3) не больше числа 17. Поле из 4 элементов»;
18. «Поле из 16 элементов. Малая теорема Ферма. Пятые степени. Раскраска в три цвета».

Лекция 9 (402) 26.11.2016

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

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

Огибающая

Нашли уравнение параболы, являющейся огибающей отрезка непостоянной длины, один конец которого с постоянной скоростью движется по вертикали, а второй с такой же скоростью — по горизонтали.

Завершили лекцию 15 октября: исправили ошибку в доказательстве теоремы Визинга, на которой тогда запнулись.

Есть видеозапись:
«Огибающая при равномерном движении концов отрезка по вертикали и горизонтали».

Лекция 10 (403) 3.12.2016

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

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

Уравнения второй и третьей степени. Косинус тройного угла

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

Есть видеозапись:
1. «Квадратное уравнение»;
2. «Уравнение третьей степени. Когда корней три, когда два, а когда один?»;
3. «Уравнение с тремя решениями и косинус тройного угла».

Лекция 11 (404) 10.12.2016

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

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

Метод Феррари решения уравнения четвёртой степени. Дискриминант и симметрические функции

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

Есть видеозапись:
4. «Метод Феррари решения уравнения четвёртой степени»;
5. «Симметрические функции, чётные перестановки, дискриминант»;
6. «Выражаем дискриминант через элементарные симметрические функции»;
7. «Кубические корни из 1, алгебраические числа, поля, резольвенты Лагранжа»;
8. «Основная теорема о симметрических многочленах».

Лекция 12 (405) 17.12.2016

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

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

Случайные числа и алгоритмы

Зачем нужен генератор случайных чисел?

Есть видеозапись:
1. «Для чего нужен генератор случайных чисел?»;
2. «Социологические опросы»;
3. «Метод Монте-Карло»;
4. «Поиск числа в массиве»;
5. «Методы сортировки»;
6. «Хранение паролей»;
7. «Случайные и псевдослучайные числа»;
8. «Односторонние функции».

Лекция 13 (406) 17.12.2016

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

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

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

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

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

Есть видеозапись:
0. «Лингвистика и традиционная олимпиада»;
1. «Арабский язык»;
2. «Латинские уменьшительные»;
3. «Саидский и бохейрский диалекты коптского языка»;
4. «Числительные бариаи»;
5. «Казахские предки и потомки»;
6. «Ударения и суффикс -ищ»;
7. «Бессермянское наречие удмуртского языка».

Лекция 14 (407) 11.02.2017

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

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

Векторные пространства. Интерполяционные формулы Ньютона, Лагранжа. Задача о манной каше

Разобрали несколько примеров векторных пространств.

Есть видеозапись:
9. «Векторные пространства. Формула Ньютона»;
10. «Интерполяционная формула Лагранжа»;
11. «Манная каша и корни из единицы»;
12. «Постановка задачи о размерности векторного пространства».

Лекция 15 (408) 18.02.2017

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

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

Устойчивость

Явление устойчивости и неустойчивости было показано на физических моделях вместе с их математическом описанием.

Есть видеозапись:
9. «Центр масс. Устойчивость и неустойчивость»;
10. «Ворот. Момент силы и энергия».

Лекция 16 (409) 25.02.2017

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

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

Размерность векторного пространства. Алгебраические числа

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

Советую курс Высшей школы экономики о теории Галуа.

Есть видеозапись:
13. «Размерность векторного пространства»;
14. «Алгебраическое число. Счётность множества алгебраических чисел. Несчётность континуума: диагональный метод Кантора»;
15. «Расширения полей, факторкольца и идеалы, главные идеалы и деление с остатком»;
16. «Идея другого доказательства обратимости»;
17. «Нормальные расширения, автоморфизмы».

Лекция 17 (410) 4.03.2017

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

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

Группы

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

Есть видеозапись:
18. «Что такое группа?»;
19. «Гомоморфизм. Ядро гомоморфизма»;
20. «Разложение на смежные классы. Малая теорема Ферма»;
21. «Четверная группа Клейна»;
22. «Нормальная подгруппа. Сопряжение»;
23. «Группа самосовмещений правильного многоугольника»;
24. «Самосовмещения прямоугольника и ромба, икосаэдра и додекаэдра»;
25. «Ассоциативность композиции отображений»;
26. «Обратные элементы»;
27. «Циклические группы и порядки их элементов. Функция Эйлера»;
28. «Автоморфизмы циклических групп»;
29. «Китайская теорема об остатках»;
30. «Абелева 12-элементная группа и китайская теорема об остатках»;
31. «Основная теорема об абелевых группах».

Лекция 18 (411) 11.03.2017

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

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

Группы перестановок. Неразрешимость группы перестановок 5 элементов

Нормальные подгруппы. Внутренний автоморфизм. Внешний автоморфизм группы перестановок 6 элементов и уникальность этого явления.

Есть видеозапись:
32. «Любая группа вложима в группу перестановок»;
33. «Группа кватернионов»;
34. «Внутренний автоморфизм»;
35. «Элемент, обратный к произведению»;
36. «Центр группы перестановок»;
37. «Сопряжённые перестановки»;
38. «Внешний автоморфизм группы перестановок шести элементов».

Лекция 19 (412) 18.03.2017

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

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

Группы и поля

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

Есть видеозапись:
39. «Образующие симметрической группы и соотношения между ними»;
40. «Ещё о внешнем автоморфизме группы перестановок шести элементов»;
41. «Простые группы, чётные перестановки»;
42. «Четверная группа Клейна»;
43. «Простота группы чётных перестановок более чем четырёх элементов»;
44. «Пятиэлементные циклы и внешний автоморфизм».

Лекция 20 (413) 25.03.2017

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

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

Нормальные расширения и их группы автоморфизмов

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

Есть видеозапись:
45. «Автоморфизмы расширения третьей степени»;
46. «Дискриминант, норма, сопряжённые числа»;
47. «Нормальное расширение»;
48. «Группа Галуа поля рациональных функций»;
49. «Степень расширения расширения»;
50. «Несепарабельное расширение»;
51. «Основная теорема теории Галуа».

Лекция 21 (414) 1.04.2017

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

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

Графы расстояний и числа Рамсея

Для понимания лекции полезно посмотреть предыдущие лекции о числах Рамсея.

Есть видеозапись:
19. «Многомерные пространства, двудольные и многодольные графы, дистанционные графы»;
20. «Дистанционные числа Рамсея».

Лекция 22 (415) 8.04.2017

Михаил Юрьевич ПОПЕЛЕНСКИЙ,

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

Теория оценивания и её приложения

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

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

Есть видеозапись:
«Метод наименьших квадратов».

Лекция 23 (416) 15.04.2017

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

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

Математические игры и сюрреальные числа Конвея

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

Есть видеозапись:
0. «Даниил Владимирович Мусатов»;
1. «Игры Баше»;
2. «Игра ним»;
3. «Функция Гранди»;
4. «Функция Гранди суммы игр»;
5. «Неравноценные игры»;
6. «Berlekapm, Conway, Guy».

Лекция 24 (417) 22.04.2017

Михаил Юрьевич ПОПЕЛЕНСКИЙ,

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

Гравиметрия: измерение силы тяжести

Гравиметрия (от латинского gravis — «тяжёлый» и греческого «измеряю») — геофизический и геодезический метод, заключающийся в измерении поля силы тяжести. Мы будем изучать поле силы тяжести Земли. При решении первых задач по физике в школе иногда берут значение ускорения свободного падения, вызванного силой тяжести Земли, равным 10 м/с², а потом уточняют, что оно равно 9,81 м/с².

А какова на самом деле сила тяжести, отчего она зависит, как её измерять и зачем? Чем отличаются наземная, морская и авиационная гравиметрии?

Есть видеозапись:
«Гравиметрия: измерение силы тяжести».

Лекция 25 (418) 29.04.2017

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

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

Группа Галуа многочлена деления круга и извлечение корней

Доказали неразложимость многочлена деления круга. Нашли группу Галуа соответствующего расширения.

Есть видеозапись:
52. «Комплексные числа и корни из единицы»;
53. «Дифференцирование многочлена»;
54. «Лемма Гаусса»;
55. «Неразложимость многочлена деления круга»;
56. «Группа Галуа поля корней 12-й степени из единицы».

Лекция 26 (419) 13.05.2017

Андрей Леонидович КАНУННИКОВ,

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

Построение правильного 17-угольника циркулем и линейкой

Какие правильные n-угольники можно построить с помощью циркуля и линейки? Этот вопрос интересовал ещё древнегреческих геометров. Они знали положительный ответ лишь в простых случаях: 3, 4, 5, 15 и, конечно, умели удваивать число сторон. Спустя два тысячелетия, в 1796 году 18-летний Карл Гаусс открыл построение правильного 17-угольника, а вскоре решил проблему окончательно. Это было первое большое открытие будущего «короля математиков», как называли Гаусса, и он им очень дорожил.

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

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