кружочек
в 2018-19 учебном году Кружочек проходит по вторникам с 15:00 до 16:30.
14 мая 2019
Тимофей Приходько рассказал, как построить шифр, который не смогут разгадать никакие \(k-1\) игроков по данным им кодам, а любые \(k\) смогут (для любого наперёд заданного числа игроков и любого \(k\)).
7 мая 2019
собрались в каникулы, Андрей Андрей рассказал про аукционы второй цены. это когда выигрывает тот кто назвал наибольшую цену, но платит он не её, а цену названную следующей по величине. легко показать, что если у каждого из игроков есть максимальная цена которую он готов заплатить, то назовёт он именно её. более того, оказывается, что при разумных ограничениях на правила аукциона, такая стратегия игроков является оптимальной. также мы поговорили про обобщения этой конструкции на несколько игроков, торгующихся за несколько продуктов, и пр.
23 апреля 2019
мы продолжили с равновесием Нэша в смешанных стратегиях, Тимофей разобрал пример с тюремным покером. в конце мы немного поговорили о доказательстве теоремы существования равновесия — согласно некоторой картинке, если игроки будут изменять свои (смешанные) стратегии по градиенту выгоды, система будет двигаться по эллипсу, центр которого и есть точка равновесия. как-то так.
9 апреля 2019
Тимофей Мосенков прочитал вводную лекцию про теорию игр. подробно разобрали понятие доминирующих стратегий и равновесие Нэша, было много примеров. в конце мы посмотрели на определение равновесия в смешанных стратегиях, это когда игрок не делает какой-то один ход, а выбирает каждый ход с определённой вероятностью.
26 марта 2019
я рассказал про задачу о разрезании выпуклого подмножества плоскости на \(n\) частей, имеющих одинаковую площадь и одинаковый периметр. мы нащупали как это можно было бы сделать для \(n=2^k\). трюки, требующие непрерывности (в т.ч. непрерывности функции периметр на — бесконечномерном — пространстве выпуклых фигур). аккуратнее с ними.
19 марта 2019
я рассказал продолжение доклада Сани про \(q\)-биномиальные коэффициенты. мы доказали несколько их свойств, аналогичных свойствам обыкновенных биномиальных коэффициентов; последние получаются из первых подстановкой \(q=1\), переход же в обратную сторону более изощрён. для этого мы ввели \(q\)-факториал \([n]!\), положив его равным \(1\cdot(1+q)\cdot(1+q+q^2)\cdot\ldots\cdot(1+\ldots+q^{n-1})\). после этого аналогии стали куда очевиднее. более того, продолжила раскрываться и комбинаторная подоплёка всего этого дела — связанная с числом диаграмм Юнга заданного веса.
"Поразмысли когда-нибудь. Быть может, ты догадаешься. Хорошо бы кто-то был, кто понимает такие вещи"
12 марта 2019
Саня Кудрявцев рассказал про квантование биномиальных коэффициентов (оно известно как \(q\)-биномиальные коэффициенты). а именно, был определён многочлен \(\left[n \atop k\right]\) от переменной \(q\), значение которого в единице равно \(C_n^k\). мы немного поговорили про свойства \(\left[n \atop k\right]\), основная часть времени ушла на то чтобы доказать равенства \(\sum\limits_k (-1)^k\left[2n+1 \atop k\right]=0\) и \(\sum\limits_k (-1)^k\left[2n \atop k\right]=(1-q)(1-q^3)\ldots(1-q^{2n-1})\).
5 марта 2019
Тимофей Приходько рассказал про теорию чисел, применяемую для шифрования. пользуясь несколькими недоказанными фактами (про невозможность за время, полиномиальное от количества цифр, разложить число на простые множители) и теоремами из арифметики остатков, мы показали, как два игрока открыто обмениваясь числами могут передавать друг другу числа, которые третий не сможет (полиномиально) вычислить.
26 февраля 2019
Лёня Вигдорчик из 10В рассказал доказательство теоремы о том, что \(\cos(\pi/n)\notin\mathbb Q\) при \(n\ne1,2,3,4,6\). для этого мы рассматривали многочлен Чебышёва \(T_n\), определяемый соотношением \(T_n(\cos x)=\cos(nx)\), и из подсчёта его старшего и младшего коэффициентов вывели, что при чётных \(n\) он не может иметь рациональных корней на отрезке \([0;1]\).
19 февраля 2019
Антон Порфирьев попытался рассказать про пределы функций. мы что-то поняли, но далеко не продвинулись. место для новых попыток.
22 января 2019
Митя Сутый рассказал про полярное соответствие. а именно, пусть на плоскости отмечена окружность. тогда каждой прямой, не содержащей центр, ставится в соответствие точка, отличная от центра. прямая называется полярой точки, а точка — полюсом прямой. мы обсудили ряд свойств этого соответствия и несколько примеров задач, которые оно помогает решить. (продолжение — 29 января и 5 февраля)
15 января 2019
Даня Кириллов прочитал обзорную лекцию про старославянскую письменность. мы обсудили происхождение азбуки, эволюцию в начертании и в произношении, а также связь старославянского и церковнославянского языков.
25 декабря 2018
Андрей Овчинников рассказал про полиномиальную стратегию игры в ним. оказалось, выигрывает тот игрок, который может своим ходом сделать \(xor\) двоичных записей количеств камней в кучках нулевым — а это можно сделать если и только если он нам достался ненулевым. в конце мы поговорили про модификации нима и вообще про игры с конечным числом ходов.
18 декабря 2018
Надя Рощина прочитала первую лекцию про вполне упорядоченные множества. мы долго разбирались с определениями частично упорядоченных множеств, вполне упорядоченных множеств и начальных отрезков. в конце мы доказали важную теорему, что для любых двух вполне упорядоченных множеств одно из них изоморфно начальному отрезку другого.
4 декабря 2018
Саня Кудрявцев из 10В рассказал про рождественскую теорему Ферма. она утверждает, что натуральное число \(n\) представимо в виде суммы двух квадратов тогда и только тогда, когда каждое простое вида \(4k+3\) входит в разложение \(n\) в чётной степени.
сначала мы, пользуясь мтф, вывели необходимость этого условия.
затем были даны два доказательства следующей редукции: если два числа представимы в виде суммы двух квадратов, то представимо также и их произведение. первое доказательство было чисто алгебраическим и заключалось в раскрытии скобок; второе — более концептуальное — использовало квадратные целочисленные решётки (т.е. идеалы в гауссовых целых числах).
наконец, доклад увенчался двумя доказательствами представимости простого \(p=4k+1\) в виде суммы двух квадратов. первое заключалось в подборе решений уравнения \(x^2=-y^2\) по модулю \(p\) и затем выборе их достаточно близкими к нулю; второе рассматривало инволюции на множестве решений уравнения \(4xy+z^2=p\), с помощью которых доказывалось существование решения с \(x=y\) (см. Прасолов, Рассказы о числах, многочленах и фигурах).
в общем, огонь как есть огонь.
27 ноября 2018
Антон Порфирьев рассказал про числа Мерсенна. это просто \(2^n-1\), и только. оказалось, что чётное число является совершенным (т.е. сумма его натуральных делителей в два раза больше его самого) тогда и только тогда, когда оно равно \(2^{n-1}(2^n-1)\).
мы доказали этот факт, и затем проверили что все чётные совершенные числа а) являются треугольными и б) являются суммами кубов последовательных нечётных чисел начиная с единицы.
20 ноября 2018
Даня Кириллов сделал обзорный доклад по теории чисел. мы доказали теорему Вильсона и китайскую теорему об остатках, а также вспомнили как малая теорема Ферма (и вроде ещё даже обобщающая её теорема Эйлера) выводится из теоремы Фробениуса.
13 ноября 2018
Митя Сутый рассказал несколько доказательств теоремы Сильвестра. она говорит, что если на плоскости отмечен конечный набор точек, не лежащих на одной прямой, то найдётся прямая, содержащая ровно две отмеченные точки. первая идея — рассмотреть кратчайший перпендикуляр из отмеченной точки до отмеченной прямой. вторая идея — сделать проективное преобразование, чтобы несколько прямых стали параллельны, и найти прямые с минимальным углом к этим нескольким. в обоих случаях удаётся прийти к противоречию. третья идея — спроектировать конфигурацию на сферу и воспользоваться формулой Эйлера. фантастика!
6 ноября 2018
Антон Порфирьев рассказал про великую теорему Ферма. мы начали с того, что вспомнили классификацию пифагоровых троек. после этого была сформулирована \(abc\)-гипотеза, из которой теорема Ферма следует для степеней больше 5. случай 3 и 5 степени доказывается отдельно (мы не разбирались, как), зато случай 4 степени был полностью доказан (без использования \(abc\)-гипотезы). в конце Антон рассказал про гипотезу Била и как теорема Ферма следует из неё.
30 октября 2018
я рассказал доказательство того, что вероятность взаимной простоты двух случайных целых чисел равняется \(6/\pi^2\). при этом использовалась нездоровая эвристика в суммировании рядов (превращение бесконечного произведения обратных степеней простых в ряд дзета-функции), а также геометрический подход к суммированию обратных квадратов.
23 октября 2018
Антон Порфирьев рассказал про гипотезу Борсука. она заключается в том, что любое тело в \(n\)-мерном пространстве можно разбить на \(n+1\) часть меньшего диаметра. мы обсудили определение диаметра множества на плоскости, как его посчитать для разных многоугольников и что он не меняется при переходе к выпуклой оболочке. после этого Антон (почти) доказал гипотезу Борсука в размерностях 1 и 2.
16 октября 2018
Тимофей Приходько собирается рассказать про функцию Эйлера \(\varphi(n)\). будет дано её определение, мы разберёмся как вычислять функцию Эйлера и изучим некоторые её свойства. будет доказана теорема, связывающая \(\varphi(n)\) и остатки по модулю \(n\). если останется время, мы поговорим про функцию Мёбиуса и конечные поля.
для понимания доклада полезно (но необязательно) вспомнить арифметику остатков.
9 октября 2018
Андрей Овчинников закончит чтение миникурса "Введение в линейную алгебру". планируется доразобраться со свойствами определителя: как определитель меняется при прибавлении к строке матрицы другой строки или при умножении строки на число, и то же самое для столбцов. после этого, если останется время, мы проговорим про миноры и обсудим план доказательства формулы Крамера для решения системы линейных уравнений.
2 октября 2018
планируется третья лекция миникурса Андрея Овчинникова. будут даны определения минора и алгебраического дополнения. после этого мы вспомним определение определителя и обсудим некоторые его свойства, а именно: как определитель матрицы меняется при перестановках строк или столбцов, их сложении, умножении на число, транспонировании матрицы и пр.
25 сентября 2018
Андрей Овчинников продолжил свой миникурс "Введение в линейную алгебру". в начале были введены определители матриц третьего порядка и была доказана формула для решений совместной системы трёх линейных уравнений с тремя неизвестными. затем мы вспомнили про подстановки, их композицию и их свойства. в конце дано определение определителя матриц порядка \(n\), которое мы разберём в следующий раз.
19 сентября 2018
в связи с временной отменой миникурса А.Овчинникова я рассказал про кольца, поля и их примеры, а именно \(\mathbb Z/(n)\) и \(\mathbb R[x]/(f)\) для неприводимого многочлена \(f\).
12 сентября 2018
Андрей Овчинников начал свой миникурс "Введение в линейную алгебру". на первом занятии был разобран метод Гаусса и определители матриц второго порядка. с помощь них была выведена формула для решений совместной системы двух линейных уравнений с двумя неизвестными.