The lower bound n! + (n-1)! + (n-2)! + (n-3)

МЕНЮ


Главная страница
Поиск
Регистрация на сайте
Помощь проекту
Архив новостей

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


•Вариация Теоремы Де Брейна – Эрдеша (теория графов), доказанная Anonymous Poster 4chan,

как теорема о суперперестановках из аниме

«????? Suzumiya Haruhi»

(Меланхолия Харухи Судзумии)

Теорема де Брейна( https://www.renyi.hu/~p_erdos/1948-01.pdf ) давно изучена: существовало Евклидово доказательство, а также комбинаторное доказательство Дж.Х.Конвея, которое, следовательно, также справедливо для точек и прямых над комплексными числами, кватернионами и октонионами.

Позже, в 1993 году, в работе Даниэля Эшлока и Джанетт Тилотсон возникла задача о суперперестановках. Суперперестановкой авторы работы назвали последовательность де Брейна типа (n, n), в которой все перестановки встречаются ровно по одному разу. Собственно, задача из работы звучала так — какова длина суперперестановки для данного n?

И в 2018 Anonymous 4chan Poster, Robin Houston, Jay Pantone и Vince Vatter все же нашли решение. Зачинателем стал Anonymous треда /sci/, приведший арифметические док-ва нижней границы, краев, 1-петлей и 2-петлей: https://web.archive.org/web/20181024190314/https://warosu.org/sci/thread/3751105 ,— также предоставив алгоритм на Python, который систематически генерирует последовательность, доказывая, что в каждом n-цикле содержится 4 перестановки, и другой любой метод менее эффективен: https://pastebin.com/aNwANugC. Процесс выстраивания математически усовершенствованного доказательства можно проследить в https://groups.google.com/g/superpermutators/c/j5y24bOemiM (google группы), —где также нашли решение верхней границы.

И окончательное Latex’ed доказательство задачи о суперперестановках, с адаптированной конструкцией для построения гамильтонова путей через граф Кэли симметричной группы, представлено: https://15015121149859966999.googlegroups.com/attach/b3f67acb2f74f/v2.pdf?part=0.1&view=1&vt=ANaJVrFluRNpGg9mVCi0sIJ6EuKYFZ_k9ba1U3k-Os40NZRk644yPu5fllXPUytrDDAfeSg4BNBOTjbLJFwJNIco_t8nmod9vlr0fitCdcbSog9uB28U7uE


Источник: groups.google.com

Комментарии: