немного математики

[avva]

Задачи Putnam Competition за 2008-й год. Хорошие задачки. Несколько решил с наскока, над остальными подумаю.

Comments

[zwischenschicht.livejournal.com]

Или здесь (http://www.mathlinks.ro/index.php?f=80&sid=ca3627bab4d111eb6518f1a513b2a9a0).

"научные" соображения к 1 и 3

[etre-moral-etre-sincere.blogspot.com (from livejournal.com)]

1. http://ivan-ghandhi.livejournal.com/895481.html?thread=6451193#t6451193

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

\mathbb{Z}/a_1\mathbb{Z}\oplus\ldots\oplus\mathbb{Z}/a_n\mathbb{Z}.

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

Re: "научные" соображения к 1 и 3

[avva.livejournal.com]

1. Как здорово :) жаль, что я это только очень смутно понимаю. Но я как раз пытаюсь исправить свое почти полное незнания языка гомологий/когомологий (а именно, читаю книгу Hatcher'а по алгебраической топологии; правда, привязку к цепям и интеграции я там не найду - где мне потом об этом лучше почитать, подскажите?); может, через несколько месяцев вернусь к вашему комментарию и лучше пойму.

Я же решил эту задачу в точности по "ненаучному" пути: f(x,x)=0, f(x,y)=-f(y,x) путем простого тыка, ну а дальше интуиция подсказывает, что g определяется с точностью до аддитивной константы, поэтому можно взять g(0) = 0 и проверить с помощью f(x,0), что все совпадает.

3. А откуда следует, что мы к этой канонической форме придем?

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

Re: "научные" соображения к 1 и 3

[kapahel.livejournal.com]

правда, привязку к цепям и интеграции я там не найду - где мне потом об этом лучше почитать, подскажите?

Про цепи у Хэтчера написано. А про связь с дифф. формами/интегрированием и совпадение сингулярных когомологий и когомологий де Рама написано, например, в Foundations of Differentiable Manifolds and Lie Groups by Frank W. Warner (и много где еще).

[(Anonymous)]

5. Нет времени решать, соображение:
Наверное, должна получиться сумма величин O(1) по экспоненциально растущим отрезкам, которая должна сходиться.

Re: "научные" соображения к 1 и 3

[etre-moral-etre-sincere.blogspot.com (from livejournal.com)]

Про связь с интегрированием и когомологиями де Рама - это отдельная история, такое много где пишут, а совсем "правильного" источника я сходу не знаю. А про симплициальные и сингулярные когомологии очень хорошо написано в книжке Васильева, изданной странным издательством "Фазис" лет 10 назад (но я не знаю, находится ли она в сети).

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

[http://users.livejournal.com/_navi_/]

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