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

Лекция 1 (270) 17.09.2011

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

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

Игра Конвея с единицами. Треугольник Паскаля и числа Стирлинга

Удалось полностью разобраться в задаче Дж. Конвея о единицах. Она оказалась связана с треугольником Паскаля. Подбирая правила игры, можно получить как великолепную иллюстрацию бинома Ньютона, так и числа Стирлинга для перестановок.

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

Лекция 2 (271) 24.09.2011

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

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

Числа Стирлинга и формула включений-исключений

Эта лекция — продолжение предыдущей. Было рассказано о связи чисел Стирлинга с алгеброй и формулой включений-исключений. Было дано определение функции Мёбиуса и доказана одна из формул обращения Мёбиуса.

Лекция 3 (272) 1.10.2011

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

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

Доказуемость и недоказуемость в математике

Было рассказано о том, как в математике были обнаружены первые истинные, но не доказуемые утверждения. Как и при каких условиях можно в принципе установить (и даже строго доказать) недоказуемость чего-либо. Были приведены примеры простых комбинаторных недоказуемых утверждений, в том числе найденные сравнительно недавно.

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

Лекция 4 (273) 8.10.2011

Владимир Николаевич ЧУБАРИКОВ,

профессор, исполняющий обязанности декана механико-математического факультета МГУ.

Математика в Московском университете

В рамках «Фестиваля науки» В.Н. Чубариков выступил перед школьниками и их родителями.

Лекция 5 (274) 8.10.2011

Владимир Юрьевич ПРОТАСОВ,

доктор физико-математических наук, профессор механико-математического факультета МГУ.

Геометрия звёздного неба

Во втором номере 2010 года журнала «Квант» опубликована статья «Геометрия звёздного неба». Об этом и было подробно рассказано.

Лекция 6 (275) 15.10.2011

Владимир Георгиевич СУРДИН,

кандидат физико-математических наук, старший научный сотрудник ГАИШ МГУ.

Движение небесных тел: гравитация и приливы

Брошюра «Пятая сила», выпуск 17 серии «Библиотека "Математическое просвещение"».

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

Лекция 7 (276) 22.10.2011

Антон Александрович КЛЯЧКО,

доцент кафедры алгебры МГУ.

Муравьи на мячике

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

Было рассказано об обобщениях и усилениях этой леммы, доказанной когда-то докладчиком. Были упомянуты её применения к абстрактной алгебре, а именно, к решениям уравнений над группами.

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

Лекция 8 (277) 29.10.2011

Юрий Александрович АЛХИМЕНКОВ,

студент III курса геофизического отделения геологического факультета МГУ.

Брахистохрона Иоганна Бернулли

В вертикальной плоскости даны точки A и B. Необходимо определить кривую, спускаясь по которой под действием силы тяжести и начав двигаться из точки А, тело достигнет точки В за кратчайшее время. Такую кривую скорейшего спуска называют брахистохроной. Ещё в XVII веке Иоганн Бернулли поставил эту задачу, которая привлекла внимание многих выдающихся ученых. Всего предложено пять решений: И. Бернулли, Лейбница, Я. Бернулли, Лопиталя и Ньютона. Все они очень содержательны. Наибольшую популярность получило решение самого автора, о котором и пойдёт речь на лекции.

Перед лекцией полезно ознакомиться с книгой Георгия Николаевича Бермана «Циклоида» и двумя статьями журнала «Квант» 1975 года: «Тайна циклоиды» и «Брахистохрона, или ещё одна тайна циклоиды».

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

Лекция 9 (278) 5.11.2011

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

автор ряда статей журнала «Квант», соросовский учитель школ №№ 1018, 1101 и 1543.

Длины биссектрис треугольника

Легко построить треугольник по длинам трёх его медиан. Необходимым и достаточным условием существования треугольника с заданными длинами медиан m_a, m_b и m_c являются неравенства треугольника m_a < m_b + m_c, m_b < m_a + m_c и m_c < m_a + m_b.

Чуть сложнее построить треугольник по длинам его высот. Необходимым и достаточным условием существования такого треугольника являются неравенства треугольника на числа 1/h_a, 1/h_b и 1/h_c.

Задача о восстановлении треугольника по длинам его биссектрис намного труднее и интереснее. Оказывается, никаких ограничений на длины биссектрис нет! Более того, для любых трёх отрезков существует и единственен треугольник именно с такими длинами биссектрис. А вот циркулем и линейкой построить треугольник по длинам его биссектрис нельзя.

На русском языке это впервые опубликовано в первом номере «Кванта» за 2003 год и в энциклопедии «Числа и фигуры» издательства «Росмэн».

Лекция 10 (279) 12.11.2011

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

автор ряда статей журнала «Квант», соросовский учитель школ №№ 1018, 1101 и 1543.

Раскраски графов и системы линейных уравнений

Количество способов окрасить часть вершин графа так, чтобы для любой окрашенной вершины количество окрашенных соседок (вершины называем соседними, если они соединены ребром) было чётно, а для любой неокрашенной количество соседок было нечётно, может равняться только одному из чисел 1, 2, 4, 8, ... В частности, оно не может равняться нулю. Чтобы доказать этот факт, были рассмотрены системы линейных уравнений над полем из двух элементов.

Опубликована статья В.В. Дорофеева и А.В. Спивака в четвёртом номере «Кванта» 2011 года.

Есть видеозапись:
33. «У любой отмеченной вершины чётное число отмеченных соседок, а у неотмеченной нечётное»;
34. «Количество раскрасок — степень двойки»;
35. «Раскраски вершин куба»;
36. «Раскраска треугольной призмы»;
37. «Существование раскраски и граф с нечётным числом вершин нечётных степеней»;
38. «Сумма степеней вершин графа вдвое больше числа его рёбер».

Лекция 11 (280) 19.11.2011

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

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

Лингвистические задачи

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

Если вам понравится разбираться в устройстве языка — добро пожаловать на Традиционную лингвистическую олимпиаду.

Есть видеозапись:
«Лингвистические задачи».

Лекция 12 (281) 26.11.2010

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

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

Пространственные решения планиметрических задач

Было рассказано, как стереометрия помогает решать планиметрические задачи. Советую прочитать статью «Мыльные пузыри и хорды» второго номера журнала «Квант» 2010 года.

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

Лекция 13 (282) 3.12.2011

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

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

Избранные задачи «Заочных математических олимпиад»

Было рассказано о нескольких интересных задачах недавно переизданной книги «Заочные математические олимпиады» Н.Б. Васильева, В.Л. Гутенмахера, Ж.М. Раббота и А.Л. Тоома.

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

Лекция 14 (283) 17.12.2011

Анатолий Александрович ЧАСОВСКИХ,

мехмат МГУ.

Нейросети

Было рассказано о нейросетях.

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

Лекция 15 (284) 11.02.2012

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

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

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

n-я буква слова Туэ — А или Б в зависимости от того, чётно или нечётно количество единиц двоичной записи числа n. Оказывается, в этом слове никакое подслово не появляется три раза подряд. При помощи слова Туэ легко построить слово в трёхбуквенном алфавите, которое не содержит не только трёх, но даже двух одинаковых подряд идущих подслов. Есть и другие — не использующие конструкцию Акселя Туэ — способы построения бесквадратных слов (для алфавитов, состоящих более чем из двух букв).

Прочитать о бесповторных последовательностях можно в энциклопедии «Числа и фигуры» издательства «Росмэн».

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

Лекция 16 (285) 18.02.2012

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

доктор физико-математических наук, профессор кафедры математической статистики механико-математического факультета МГУ, заведующий кафедрой дискретной математики факультета инноваций и высоких технологий МФТИ, руководитель исследовательского отдела в Яндексе, автор брошюр «Вероятность и алгебра в комбинаторике», «Остроугольные треугольники Данцера-Грюнбаума», «Хроматические числа», «Проблема Борсука», «Линейно-алгебраический метод в комбинаторике», «Системы общих представителей в комбинаторике и их приложения в геометрии», «Модели случайных графов» и «Гипотеза Кнезера и топологический метод в комбинаторике».

Системы представителей

Представим себе такую ситуацию. В некоторую организацию одновременно приехали с визитом несколько иностранцев — скажем, англичанин, француз, японец и венгр. Каждый из них умеет говорить только на своем родном языке. Желая должным образом принять гостя, организация стремится послать на встречу с ним одного из своих сотрудников, который бы владел соответствующим языком и, тем самым, помог визитёру сориентироваться в незнакомом городе (на наёмных переводчиков денег жалко). Допустим, нашлись как сотрудники, знающие английский, так и сотрудники, говорящие по-венгерски, и так далее. Однако организация не хочет отрывать слишком много людей от работы и пытается минимизировать количество сотрудников, командируемых на общение с иностранцами. Ведь могут же найтись и такие полиглоты в её рядах, которые одновременно владеют английским и японским или, и того больше, французским, японским и венгерским? Глядишь, приставит организация одного человека сразу к троим посетителям, и проблем станет меньше?

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

Есть видеозапись:
1. «Система представителей: конкретный пример»;
2. «Системы представителей: постановка задачи»;
3. «Числа сочетаний»;
4. «Очевидные оценки сверху количества представителей»;
5. «Очевидные оценки снизу количества представителей»;
6. «Жадный алгоритм и оценка сверху».

Лекция 17 (286) 25.02.2012

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

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

Формула крюков

Явная формула для чисел Каталана является частным случаем открытой в 1954 году формулы крюков. При помощи антисимметрических многочленов можно доказать формулу крюков весьма естественным и простым способом. Ознакомиться с этим доказательством можно в третьем номере «Кванта» 2009 года.

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

Лекция 18 (287) 3.03.2012

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

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

Вероятности. Среднее значение и дисперсия. Бросания несимметричной монеты

Среднее значение случайной величины (математическое ожидание) и дисперсия весьма важны не только для математиков. Что же такое теория вероятностей? На примере нескольких вполне доступных задач рассказано об этой очень важной математической науке.

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

Лекция 19 (288) 10.03.2012

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

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

Закон больших чисел

Это вторая лекция о теории вероятностей. Было рассказано доказательство закона больших чисел Чебышёва.

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

Лекция 20 (289) 17.03.2012

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

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

Вписанные многоугольники

Рассмотрим окружность и точку внутри неё. При каких натуральных n может так быть, что некоторые лучи, выходящие из этой точки под равными углами, дают отрезки, длины которых были все целыми и разными числами? В статье «Вписанные многоугольники» первого номера «Кванта» 1999 года дано полное решение этой задачи. Теорема Птелемея о том, что произведение длин диагоналей вписанного четырёхугольника равно сумме произведений его противоположных сторон и многие другие теоремы геометрии естественным образом возникают при решении этой задачи.

Лекция 21 (290) 24.03.2012

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

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

Марковские цепи и пари для простаков

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

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

Кроме задачи Пеннея, были разобраны знаменитая задача о разорении и другие примеры.

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

Лекция 22 (291) 7.04.2012

Фёдор Константинович НИЛОВ,

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

Обобщённая конструкция Данделена

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

Ключевым моментом в доказательстве теоремы Данделена является то, что на конусе есть семейство прямолинейных образующих. Для произвольной поверхности второго порядка это не так. Для доказательства обобщённой теоремы мы будем использовать обобщённые определения коник. Эти определения отличаются от классических тем, что фокусы в них заменяются на окружности, а расстояние от точки до фокуса — на длину касательной к «фокальной» окружности. Были рассказаны и некоторые другие применения этих определений.

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

Лекция 23 (292) 14.04.2012

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

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

Критерий Куратовского планарности графа

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

Теорема Куратовского утверждает, что этими двумя примерами по сути исчерпывается список препятствий к планарности графа: любой непланарный граф содержит подграф, гомеоморфный одному из этих двух графов. Многие годы доказательство этой теоремы считалось очень трудным. Однако А.Б. Скопенков сумел изложить доказательство настолько просто, что теперь оно стало доступно заинтересованному школьнику.

Есть видеозапись:
1. «Куратовский и Макарычев»;
2. «Непланарность 3 домиков и 3 колодцев, полного графа на 5 вершинах»;
3. «Формула Эйлера и непланарность»;
4. «Метод наименьшего контрпримера»;
5. «Геометрическое доказательство иррациональности корня из 2»;
6. «Стягивание ребра в точку»;
7. «Существование цикла»;
8. «Точку загоняем внутрь цикла»;
9. «Отсутствие внешних рёбер»;
10. «Отсутствие тета-подграфа и схопывание другого ребра»;
11. «Завершение доказательства».

Лекция 24 (293) 21.04.2012

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

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

Перечисление деревьев

Деревья — это связные графы без циклов. Это одно из самых простых, а значит, самых интересных семейств графов. Cчитать деревья с заданным числом вершин трудно из-за того, что деревья могут быть или не быть симметричными. Однако если пронумеровать вершины, то задача перечисления становится простой, и она была решена на лекции при помощи кода Прюфера. Ответ: n^{n – 2}, где n — количество вершин дерева.

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

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

Есть видеозапись:
«Циклические перестановки и код Прюфера».