в 2019-20 учебном году кружочек проходит по средам с 15:00 до 16:00 в комнате 205.
в апреле 2020 кружочек проходит в зуме. анонсы появляются здесь https://vk.com/botayte_gospoda

18 декабря 2019

Миша Трошкин рассказал про особенности плоских алгебраических кривых и обобщение теоремы о неявной функции. обычная версия этой теоремы говорит, что кривую \(F(x,y)=0\) в окрестности некоторой точки можно задать как график \(y=f(x)\), если \(\frac{\partial F}{\partial y}\ne0)\). обобщённая версия утверждает, что даже если \(\frac{\partial F}{\partial y}=0)\), кривую почти всегда можно задать как график \(y=f(x^{1/n}\). при этом функцию \(f\) можно пытаться искать как формальный степенной ряд с комплексными коэффициентами.

18 декабря 2019

Андрей Овчинников продолжил рассказывать про квантовые алгоритмы. мы разобрали алгоритм Дойча-Йожи, обобщающий алгоритм Дойча для произвольного \(n\).

11 декабря 2019

Андрей Овчинников рассказал про квантовые алгоритмы. введение уже было рассказано на проектной конференции, поэтому мы сразу начали разбирать алгоритмы, а именно алгоритм Дойча, решающий следующую задачу (для \(n=2\)). функция \(f\) присваивает каждой строке из нулей и единиц длины \(n\) значение \(0\) или \(1\); известно, что \(f\) либо постоянна (т.е. тождественно равна нулю или единице), либо сбалансирована (т.е. принимает оба значения ровно в половине случаев). нужно выяснить сбалансирована \(f\) или постоянна. квантовый алгоритм делает это за три действия.

27 ноября 2019

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

13 ноября 2019

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

9 октября 2019

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

2 октября 2019

Миша Трошкин рассказал про функториальный подход в комбинаторике. а именно, берётся категория конечных множеств, в которой морфизмы это только биекции; каждому множеству \(X\) сопоставляется множество некоторых геометрических структур на \(X\). также мы определили операции над комбинаторными структурами (например, множество всех способов разделить \(X\) на два подмножества, определить на первом комбинаторную структуру \(A\), а на втором комбинаторную структуру \(B\)). также мы поговорили про производящие функции комбинаторных структур и про то, как меняются производящие функции при различных операциях.
доклад был по книжке Bergeron, Labelle, Leroux. Combinatorial species and tree-like structures

25 сентября 2019

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

АРХИВ ДОКЛАДОВ 2018-19 УЧЕБНОГО ГОДА

в 2018-19 учебном году кружочек проходил по вторникам с 15:00 до 16:00

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

Андрей Овчинников начал свой миникурс "Введение в линейную алгебру". на первом занятии был разобран метод Гаусса и определители матриц второго порядка. с помощь них была выведена формула для решений совместной системы двух линейных уравнений с двумя неизвестными.

АРХИВ ДОКЛАДОВ 2017-18 УЧЕБНОГО ГОДА

это материалы по кружочку, который проходит по средам с 14:55 до 16:35.

4 апреля 2018

по причине существенно неполного состава слушателей, мы на время заморозили программу классификации пифагоровых троек и решили поговорить про эллипсы, а именно, про фокальное свойство и его возможные следствия. для разминки мы передоказали эквивалентность определений эллипса через фокусы и как нули уравнения \(ax^2+by^2=c\). после этого мы долго бились над пониманием, что же такое "угол падения" и "угол отражения".
стало ясно, что для работы с гладкими кривыми нужно строгое определение касательной, которого у нас пока нет. тем не менее, мы понадеялись обойтись свойствами выпуклости, а также существованием касательной в каждой точке (в последнее пришлось поверить без доказательства). на этом, собственно, и было закончено обсуждение технических вопросов. путеводные задачи, которые мы будем пытаться атаковать, выглядят так:

1. к плоскости приклеили эллипс, выпиленный из фанеры, на него набросили замкнутую нить (длина которой больше длины эллипса), вставили в неё карандаш, натянули и провели вокруг. доказать, что полученная замкнутая кривая будет эллипсом, причём с теми же фокусами, что и у фанерного.
2. на плоскости нарисованы два эллипса с совпадающими фокусами. известно, что существует замкнутая \(k\)-звенная ломаная, которая вписана в больший эллипс и касается меньшего (каждым звеном). доказать, что любая \(k\)-звенная ломаная, вписанная в больший эллипс и касающаяся меньшего, будет замкнутой.

21 марта 2018

мы снова пытались расклассифицировать пифогоровы тройки, решив уравнение \(x^2+y^2=1\) в рациональных числах. повторив всё, что было в прошлый раз, мы поняли, что нам нужна инверсия с центром в точке \((0;1)\) и радиусом \(2\) — она переводит единичную окружность в прямую \(y=-1\). записать такую инверсию явно в координатах мы, к сожалению, не успели, но надо это обязательно когда-нибудь проделать.

14 марта 2018

мы начали решать следующую задачу: найти все рациональные решения уравнения \(x^2+y^2=1\).
сначала мы поняли, что поворот одного из решений на угол с рациональными косинусом и синусом, возможно, даёт другое решение, но это нельзя использовать для классификации всех решений.
потом мы решили заняться инверсией и поняли, что вроде бы инверсия с рациональным центром и рациональным радиусом переводит рациональные точки в рациональные. это позволяет свести задачу об окружности к задаче о прямой. здесь-то видимо и скрывается решение исходной проблемы, о чём мы продолжим говорить в следующий раз.

28 февряля 2018

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

31 января 2018

мы попробуем доказать, что пара ломаных, удовлетворяющая КОП-критерию, имеет чётное число точек пересечения. это предполагается делать по пунктам (попробуйте дома):
а) для двух треугольников (разобрали 24 января);
б) для треугольника и четырёхзвенной ломаной;
в) для треугольника и \(n\)-звенной ломаной;
г) для \(m\)-звенной и \(n\)-звенной ломаных.
возможно, КОП-критерий придётся усилить, чтобы такое пошаговое доказательство прошло без ошибок в мелких деталях — либо придумать другое.

24 января 2018

пытаясь доказать алгоритм с прошлого занятия, мы натолкнулись на следующую задачу, которую начали атаковать:
при каких условиях на пару замкнутых ломаных число их точек пересечения чётно?
ответ (КОП-критерий):

• у ломаных не совпадают вершины;
• вершины одной не лежат на рёбрах другой;
• рёбра одной не проходят через точк пересечения рёбер другой.

17 января 2018

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

• по отрезку и прямой выяснить, пересекает ли прямая отрезок;
• по отрезку и лучу выяснить, пересекает ли отрезок луч

(входные данные — координаты концов отрезка, конца луча и произвольной точки на луче).

6 декабря 2017

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

29 ноября 2017

мы нарисовали пучок коник \(a(x^2-1)+b(y^2-1)=0\) (где \( (a,b)\) — любые пары вещественных чисел, отличные от \( (0,0)\)). получилось довольно красиво, но очень страшно, гиперболы там полезли, эллипсы..

22 ноября 2017

мы начали говорить про алгебраические уравнения от двух переменных и про кривые на плоскости, которые ими задаются. в частности, удалось доказать равносильность двух определений эллипса — как множества точек, сумма расстояний от которых до двух фокусов постоянна, и как окружности, растянутой по одному из направлений.
ещё поговорили про приводимые кривые и выяснили, как нарисовать кривую \(F(x,y)G(x,y)=0\), зная кривые \(F(x,y)=0\) и \(G(x,y)=0\).
домашнее задание
1. попробуйте доказать, что отрезки, соединяющие точку на эллипсе с двумя фокусами, образуют равные углы с касательной в этой точке.
2. даны окружности, заданные уравнениями \(x^2+y^2-9=0\) и \((x+1)^2+(y+2)^2-4=0\). попробуйте найти уравнение прямой, проходящей через их точки пересечения, не находя эти самые точки.

15 ноября 2017

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

8 ноября 2017

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

25 октября 2017

мы продолжили резать ориентируемые поверхности по разным наборам кривых. а именно, мы доразобрались с тором и порезали поверхность рода 2.
затем мы занимались обратной процедурой: склеиванием сторон 2n-угольника (без перекрутки) в каком-либо порядке.
упражнение на каникулы.
а) Сколькими способами можно разбить на пары стороны правильного восьмиугольника?
б) Поверхность какого рода получается при склеивании парных сторон для каждого из способов?
у квадрата таких способов два (получаются сфера и тор), а у шестиугольника — четыре (получается сфера и три тора). что же получается для восьмиугольника мы узнаем за каникулы, либо после, а затем, возможно, наконец обсудим более сложные вопросы, например почему сфера и тор не гомеоморфны.

18 октября 2017

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

4 октября 2017

мы определили действия групп, орбиты действия и стабилизаторы точек. примеров действия групп у нас пока не очень много, все они происходят из комбинаторных задач про раскраски. в конце была сформулирована формула Бёрнсайда, мы наметили путь её (возможного) доказательства через подсчёт двумя способами, а также попробовали применить для доказательства малой теоремы Ферма.
дома желающим предлагается изучить количество расстановок \(p\) ладей на торе \(p\times p\) и доказать с помощью него теорему Вильсона: \((p-1)!-1\) делится на \(p\).

27 сентября 2017

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

20 сентября 2017

мы поговорили про отображения между множествами и посмотрели на композиции отображений. выяснилось, что композиция отображений \(A \to A\) ассоциативна, но не коммутативна, что для них существует нейтральный элемент, а обратные — только для некоторых. совокупность обратимых отображений называется группой (всех) преобразований A. изучением этого объекта мы и рассчитываем заняться в следующий раз.