Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Преждевременные мемуары

Спрашивает одногруппник.

— А почему когда Тиль сказал, что любой группе можно найти матричное представление, ты сразу спросил про свободную группу из двух элементов?
— Смотри, любой элемент этой группы мы можем представить в виде последовательности ненулевых (кроме первого; ему позволено быть нулевым) целых чисел и отображение это биективно:
phi(i_1, i_2,..) = a^(i_1) b^(i_2) a^(i_3) ...

Вот и представь, нам нужно закодировать все возможные конечные последовательности целых чисел конечномерными матрицами. А конечномерная матрица содержит всего конечное число клеток, куда числа вписывать, значит, последовательность целых чисел, которая длиннее количества клеток, придётся кодировать так, что какие-то два числа будут «сосчитаны» в одну ячейку. А при этом скорее всего потеряется информация. Скодировать последовательность целых чисел без потерь в одно, скажем, рациональное, можно только каким-нибудь эзотерическим способом. Если порядок не имеет значения, это ещё достаточно просто: конечной последовательности целых чисел биективно разложение на простые множетели положительного рационального числа.
(i_1, i_2, i_3...) <-> 2^(i_1) · 3^(i_2) · 5^(i_3) · ···
Если порядок имеет значение, единственный способ, который сразу приходит в голову — цепная дробь.
(i_1, i_2, i_3) <-> i_1 + 1/(i_2 + 1/(i_3 + ···))
Тоже взаимнооднозначно, конечно. Наверное, ещё как-нибудь при помощи остатков закодировать можно.

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

— И как ты всё это успел сообразить за полторы секунды?
— А я и не соображал. Я сам внятно понял свои соображения только сейчас, когда тебе излагал. На самом деле мысль была такой: «Матрица => конечное количество степеней свободы. Нужно группу с бесконечным количеством степеней свободы. Свободные группы, о!».

— А почему именно про свободные группы подумал?
— А потому что мне про них один знакомый (dmitri83) в Брюсселе рассказал. Мне понравилось. :-)
— А вообще с теорией групп ты давно знаком?
— И недавно, и давно. С группами, вообще-то, совсем недавно, но кое-какие алгебраические структуры часто автоматически возникают при решении олимпиадных задач.

В далёком 1996, кажется, году учился я в Омске Школе №66, а по вторникам был у нас математический кружок. Омский Универ с незапамятных времён вёл по школам кружки. Называлось это дело «Четверговая математическая школа». Ещё моя матушка будучи студенткой в таковой преподавала. В те времена она [школа] маленькая была и была вправду по четвергам. А потом разрослась и стала в самые разные дни. В особенно почётной 64 физикоматематической она была по воскресеньям и это тема отдельной истории. :-) А у нас в 66 — по вторникам. Преподавала нам в том году студентка по имени Анна Николаевна Перцева. У меня, как ни странно, хорошая память на некоторые имена.

Преподавалась там всякая дискретика, по сей день очень мне близкая и приятная: теория графов, делимость, биномиальные коэффициенты всякие с числами Стирлинга. В тот год мы решили поучаствовать в ежегодной коммандной заочной олимпиаде, организуемой журналом "Квант".
Олимпиада «Математика 6-8» состоит из трех заочных и одного очного тура. Задачки там были — ууух. В одной из задачек нужно было доказать нескладываемость одной фигуры из множества специальных других. Я сел дома и начал искать инварианты — т.е. свойства, общие для всех фигур, сложенных из данных. Я хотел всего лишь найти какое-то свойство, не выполненное на фигуре, которую надо было сложить.

Надо сказать, что моё решение в итоге заняло более 20 листов-черновиков А4 и содержало полную теорию складывания заданных фигур. :-)
Каждую элементарную фигуру там можно было составить из одинаковых треугольничков-кирпичиков, кажется. Т.е. пространство можно представить разделённым на такие треугольники и каждый треугольник координатизировать парой чисел. Фигура есть функция, сопоставляющая каждому треугольнику, сиречь паре чисел, число. 0, если треугольник в фигуру не входит и 1 в противном случае. «Обобщённые» фигуры могут отображать из множества треугольников во все целые числа (так удобнее было). Множество доступных нам фигур — это элементарные фигуры во всех их вариациях, т.е. параллельных переносах, вращениях, доступных в треугольном пространстве и отражениях. Сложение фигур = сложение функций. Я долго изучал множество функций, порожденных всеми возможными сложениями элементарных и обнаружил набор достаточно простых критериев, определяющий, принадлежит ли некоторая функция к нему. Для фигур удовлетворяющих критериям был придуман алгоритм, как их составить.

А вот теперь угадай, почему меня так прёт от Теории Галуа? :-))

Такие штуки у меня всегда получались намного лучше, чем простое нахождение инвариантов. Всегда очень хочется получить завершенный формализм, а не просто решить задачу. В одной олипиадной (на этот раз, олимпиада была очной) задаче про Синие и Красные числа я на том и прокололся. Вместо того, чтобы решать задачу, я полез искать красивый формализм. А когда мы по этому поводу общались со Штерном (автором задачи) лично, вместо того, чтобы говорить о задаче, я запнулся на определении деления с остатком и разбирался с ним минут пять. АлексанСавеличу (Штерну) надоело и до обсуждения решелия мы так и не дошли. :-)

К сожалению, в "Квант" ушло решение задачи в ранней, некрасивой форме. Целиком записать красивое я банально не успел к сроку сдачи. В Кванте мы, кстати, совместными усилиями с Артёмом Романенко, Никитой Анкиловым и ещё одним Артёмом, фамилии которого я не помню, прошли все три тура. Грамота до сих пор где-то лежит у Анны Николавны, никаких контактов которой у меня на сегодняшний день нет. На очный тур мы не попали, так как узнали о нём слишком поздно.

PS: Анна Николаевна! Если Вы меня слышите.. :-)
Subscribe

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

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

  • 36

    Традиционный деньрожденный пост. Год выдался необычный. :)

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment