Занимательная математика в эпоху хайтека

АРХИВ

автор: Евгений Скляревский   16.11.2004

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

ИВАН ДАВЫДОВИЧ: Слушайте меня внимательно. Мы отсюда не уйдем до тех пор, пока не выясним все, что нас интересует. И вы нам обязательно расскажете все. Вопрос только — какой ценой. Церемониться мы не будем. Мы не умеем церемониться. И должно быть тихо, даже если вам будет очень больно…
Он берет саквояж, ставит на стол, раскрывает, извлекает автоклавчик и, звякая металлом и стеклом, принимается снаряжать шприц для инъекций.
Феликс наблюдает эти манипуляции, покрываясь испариной.
ИВАН ДАВЫДОВИЧ: Разумеется, мы бы предпочли получить от вас информацию быстро, без хлопот и в чистом виде, без примесей. Я думаю, это в ваших интересах…

А. и Б. Стругацкие. «Пять капель эликсира»

Рунет создавался, точнее наполнялся, постепенно. Сначала хозяйничали создатели-технари — до сих пор львиную долю ресурсов составляют сайты, посвященные веб-строительству, языкам программирования, администрированию, защите, движкам, RSS-лентам и прочим непригодным в домашнем хозяйстве заклинаниям. Когда стали платить за показ рекламы и началась борьба за посетителей — расцвели пупсики-кроватки, знакомства-клубнички, астропрогнозы, байки из жизни звезд и желто-скандальные новости. Были, конечно, и замечательные литературные, «фотографические» и прочие интересные странички — число их росло по мере приобщения народа к Сети. Научным и особенно научно-популярным сайтам повезло меньше. Их по сей день до обидного мало — все хорошие ресурсы можно перечесть по пальцам.

Доступ к Интернету получила в основном молодежь, связанная с ним учебой или работой. Люди же постарше, которым, возможно, и есть что сказать, в силу экономических и прочих причин зачастую не владеют технологией «выкладывания себя». В связи с этим невозможно переоценить роль проекта «народ.ру», позволившего всем желающим заиметь свою страничку. Были и другие бесплатные хостеры, но на «народе» — удобная веб-форма для закачки файлов, заготовки форумов, гостевых книг, каталоги-рейтинги, народная газета. Все это совершило революцию — народ через «народ» пошел в Сеть.

Отметим, что признанные научно-популярные издания не стали объединяющими центрами. «Наука и жизнь», «Знание — сила», «Химия и жизнь», «Квант» имеют свои страницы, но это скорее веб-представительства, даже не дублирующие бумажное издание (Кстати, огромное спасибо ребятам из Кинешмы, которые уже не первый год полностью выкладывают материалы бумажной «Компьютерры» (www.kinnet.ru/cterra)). На все, конечно, есть причины, но так уж сложилось, что нет общего сетевого журнала, который непременно хотелось бы полистать в свободную минутку, или даже урвать момент от минутки несвободной.

Может, оно и к лучшему. Отсутствие «толстых» журналов породило интересное явление — стихийную популяризацию науки! Врачи, инженеры, научные работники, журналисты и просто энтузиасты за последние два-три года открыли множество интереснейших сайтов, особенно по биологии, математике и астрономии. Появились тематические сообщества в «Живом Журнале» (www.livejournal.com/community/ru_math/89010.html, www.livejournal.com/community/ru_math/89010.html). Неплох сайт «Известия-Наука», рубрика моего виртуального коллеги Андрея Колесникова в «Компьютерных вестях» (www.kv.by); часто печатают статьи по занимательному программированию в киевском еженедельнике «Мой компьютер», в московском журнале «Hard'n'Soft». Общего «занимательного центра» — по образцу, например, «Науки и жизни» с ее обязательными рубриками, предсказуемой навигацией и списком годовых публикаций в декабрьском номере — по-прежнему нет. Но нужен ли он, если существуют десятки самобытных интересных адресов, каждый с изюминкой, со своей структурой и логикой, разобравшись в которой, вы получаете истинное наслаждение. Вот чудесная rechka.ru, протекающая по самым вкусным занимательным областям, вот страница www.px-pict.com, посвященная составлению фигур из квадратов с сопутствующими занимательными сведениями. Посещение каждой такой страницы — небольшой праздник, а я, например, именно этого жду от Интернета, предлагая рассматривать его как карнавал-калейдоскоп приятных событий, а не заурядную кормушку для бизнеса.

Что же изменилось за последние годы в области наших любимых развлечений? Каждый знает об огромном влиянии ИТ-новшеств на повседневную жизнь, которую так преобразили мобильная связь и электронные гаджеты, сетевые СМИ и веб-сервисы, электронный бизнес и даже садово-парковое проектирование при помощи компьютера. Уважительно отношусь к чужому труду и чужим увлечениям, но посмею заметить, что все перечисленное довольно скучно по сравнению с вещами более привлекательными — в первую очередь, с занимательной математикой. Эта приятнейшая забава тоже прошла интересный путь за последние двадцать лет.

Большинству читателей времена «Феликсов» и логарифмических линеек кажутся такими же далекими, как дата первого выхода «Арифметики» Магницкого. Однако я считал дипломный проект и все курсовые работы на логарифмической линейке. Красивые графики из книжек по занимательной математике я строил на миллиметровке с помощью таблиц Брадиса. Восторга от полученных результатов было ничуть не меньше, чем от общения с нынешней любимой двухгигагерцовой числомолотилкой. Простой настольный калькулятор вызывал восхищение. Помню, с каким удовольствием я нажимал его клавиши при первом знакомстве, проверяя известные закономерности и числовые фокусы.

Здесь же следует уронить несколько слез ностальгии, например, по номограммам — ныне это таинственное искусство совмещать несколько функций на одном графике приказало долго жить. Та же легкая грусть возникает при рассматривании картинок остроумнейших механизмов для дифференцирования, интегрирования и рисования графиков сложнейших функций. Они почили в бозе, как и логарифмические линейки, арифмометры, таблицы логарифмов, счеты и перфокарты с перфолентами. Мало того, канула в Лету и чудесная школьная арифметика, требующая фантазии и воображения, уступив место тривиальному составлению уравнений (см. «Ностальгия по арифметике», «КТ» #409).

Следующим шагом после калькуляторов можно считать появление дисплеев ЭВМ (Электронная вычислительная машина; так, дети, раньше по-русски называли компьютер. — Л.Л.-М) серии ЕС и СМ. Я и раньше умудрялся экспериментировать, вводя информацию на перфокартах, а результаты рассматривая на координатографах, но эти алфавитно-цифровые дисплеи впервые позволили испытать интерактивность, сделать нечто развлекательное на основе диалога. Все помнят игровую классику того времени — «быков и коров», посадку спутника на Луну, стрельбу из пушки (вы задаете угол, а вам сообщают недолет или перелет в метрах) и, конечно же, ним-подобные игры с кучками предметов, которые надо брать по очереди, последний взявший проигрывает. Популярны были отгадыватели задуманного машиной числа, особенно «вилкой» из двух чисел (программа сообщала, где лежит задуманное — ниже меньшего, выше большего или между ними). Отличное упражнение для изучающих бейсик и просто повод приятно порассуждать — в каком максимальном диапазоне должно находиться число, чтобы его можно было отгадать с пяти попыток?

Прежде чем перейти к взрывообразному эффекту от появления графических дисплеев, отметим два важнейших «алфавитно-цифровых» события. Первое, конечно же, игра «Жизнь». В докомпьютерную эпоху я играл в нее на шахматной доске. Потом она стала классикой программирования, и как только появлялось новое оборудование или менялась операционная система на старом, сразу же на экране возникали «мигалки» и «планеры», организмы двигались, рождались и умирали. Каждый программист после «Hello, World» просто был обязан написать «Жизнь» на своем любимом языке. Впрочем, «Жизнь» лишь частный случай обширной теории клеточных автоматов (КА), открывающей необъятный простор для творчества. На основе КА построены (см. статью Константина Кнопа «Тьюрмиты», «КТ» #246, а также ссылки в arbuz/y_life.html) алгоритмы, повторяющие на экране циклические химические реакции Белоусова с их характерными вихрями, модели движения людей в переходах, апплеты, моделирующие панику при эпидемии (www.kevan.org/proce55ing/zombies). Известны также варианты «Жизни» на треугольных, шестиугольных и объемных полях, есть скрипты для запусков организмов в онлайне. Не пожалейте времени, напишите игру «Жизнь» для шестиугольного поля. Получите удовольствие от подбора законов существования колонии и от попутно возникающих идей — например, менять законы в той или иной зависимости от числа особей в популяции.

Второе событие, определившее целую эпоху в нашей недолгой истории, — это тетрис. Простое и остроумное детище Алексея Пажитнова, сопоставимое в офлайне разве что с кубиком Рубика, прошагало по всем компьютерам, начиная с БК, ДВК и Синклера, породило десятки клонов и навсегда запомнится нам как компьютерная игра номер один3. Работая в ВЦ АН СССР, Пажитнов занимался проблемами искусственного интеллекта и распознавания речи, а для обкатки идей применял головоломки, в том числе и классическое пентамино. Костяшка домино состоит из двух квадратиков, тримино — из трех, а уж пять фигурок тетрамино, использующихся в тетрисе, знакомы каждому (на самом-то деле их не пять, а семь, две пары переходят друг в друга при отражении и не переходят при вращении). Напомню, что интерес во всем мире к этим квадратикам вспыхнул благодаря книге С. В. Голомба «Полимино»4 (М.: Мир, 1975). Центральное место в подобных развлечениях занимали пентамино — фигурки из пяти квадратиков. Двенадцать плиток пентамино были необычайно популярны, читатели постарше помнят, что в «Науке и жизни», начиная с 70-х годов, был постоянный раздел, посвященный составлению фигурок из набора пентамино. Попробуйте самостоятельно нарисовать все варианты пентамино — непременно получите удовольствие. Если справились, попробуйте ответить на следующие вопросы: сколько существует гексамино (из шести квадратиков) и гептамино (из семи)? Сколькими вариантами можно сложить цепочки из n треугольников? А шестиугольников?

Вот Пажитнов и пытался автоматизировать укладку пентамино в заданные фигурки. Однако вычислительных мощностей тогдашнего оборудования не хватало для вращения пентамино, приходилось отлаживать в тетрамино, что и определило название игры — «Тетрис» от греческого tetra («четыре»). В тех опытах и родилась великая идея — чтобы фигурки падали, а заполненные ряды исчезали. Кстати, в последнее время все чаще пишут просто тетрис (без кавычек, как радио или трамвай), что свидетельствует о проникновении слова в повседневный язык.

Чтобы написать тетрис на языке Pascal для «Электроники-60», Пажитнову хватило двух недель. Сослуживцы Алексея были в восторге, но расширить аудиторию игры можно было лишь портированием на IBM PC. В этом Пажитнову помог его приятель, шестнадцатилетний школьник Вадим Герасимов. Вскоре вся Москва сходила с ума по тетрису. За «железный занавес» игра проникла благодаря венгерским программистам, которые переписали его под платформы Apple II и Commondore 64. В бесчисленных публикациях о создателе тетриса неизменно подчеркивается, что Алексей практически ничего не получил за свою сверхплодотворную идею. Зато теперь он работает на Microsoft, где принимал участие в разработке целого набора игр Puzzle Collection (www.microsoft.com/games/puzzle).

Некий фантазер однажды высказал мысль, что тетрис — это аллегория человеческой жизни (www.kv.by/index.cgi?id=1998161104). Когда ты молод, все просто и безоблачно, ты без особых усилий справляешься с ерундовыми трудностями, сыплющимися со всех сторон. Даже можешь позволить себе некоторое лихачество и эстетство. Дальше трудности делаются все более серьезными, но ты, не слишком напрягаясь, все-таки преодолеваешь их. Ты уже поймал ритм жизни, вошел во вкус. Иногда удается одним удачным движением расправиться со всеми проблемами — «стакан» на мгновение пустеет. Но проходит время, и ты вдруг начинаешь совершать досадные ошибки буквально на ровном месте. Тут уже не до лихачества — быть бы самому живым. А затем… Затем наступает быстрый и печальный финал — игра заканчивается.

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

Упомянем компьютерную реализацию старой игрушки «Спирограф» — в бесконечных опытах с эпи- и гипоциклоидами, задавая разные соотношения радиусов катящихся колес, можно получать красивейшие узоры (см. «Роз узор», «КТ» #412). Ну, и известные с детства уравнения цветка сирени, листики, розетки и лепестки, эллипсы и спирали. Есть и другие волнующие кривые — улитка Паскаля, кардиоида, овалы Кассини, конхоида, лемниската Бернулли и прочие чудеса. Можно, конечно, рисовать их и вручную, но… овалы Кассини, например, задаются уравнением четвертой степени, без компьютера я бы не взялся за столь трудоемкие вычисления, а тут пожалуйста — за несколько минут можно отладить программу и провести десятки экспериментов с параметрами.

Еще одна потрясающая воображение возможность — это, конечно, полное владение цветом выводимых элементов. Если фигуры Лиссажу и розетки, похожие на узоры на банкнотах, красивы и в черно-белом варианте, то эпи- и гипоциклоиды, прорисованные с разными параметрами разными цветами, красивы необыкновенно. При рисовании тора, например, можно синим цветом сделать поперечные полоски, зеленым — продольные, красный привязать к текущему радиусу и наслаждаться полученным монстром («Колечко дыма и дырка от бублика», «КТ» #339). На ленте Мебиуса, подбирая цвета, можно смоделировать главные ее сюрпризы — необычные результаты от разрезания вдоль средней линии и вдоль линии, отстоящей на треть ширины от края. Самое интересное — рисовать не только известные ранее кривые и поверхности, но и получать новые (некоторые из них я условно назвал пузырями, паутинами, одуванчиками).

Следующим важнейшим шагом в развитии всяких занимательностей стала возможность задания движения. Если запустить две точки летать по экрану в разных фазах и соединять их цветными линиями — получим эдакое непоседливое веерообразное облако. Можно заставить прыгать на экране радужную пружинку — попробуйте, получите удовольствие даже от продумывания алгоритма. В Сети есть масса скриптов, апплетов и GIF-анимаций на геометрические темы. Особенно бурное развитие получили эти забавы с появлением технологии Macromedia Flash. Вот (arbuz.uz/u_applets.html) апплет, позволяющий поиграть с каждым из семнадцати известных вариантов симметрии при замощении плоскости. После длительных поисков нашлась даже флэшка, моделирующая диск Бенхама (www.michaelbach.de/ot/col_benham/index.html, www.arbuz/gazeta_38.html ) — при вращении его черно-белая окраска дает цветные полосы (читал о нем лет 35 назад в «Науке и жизни»). Есть в Сети и заготовки (*.fla) разных геометрических узоров, позволяющие каждому реализовать свои математические фантазии.

Все вышеизложенное можно считать компьютерным развитием забав прежних, докомпьютерных. Но, хотя небольшому кругу теоретиков и ранее были известны множество Жюлиа и множество Мандельброта, только с появлением компьютеров началось победное шествие фракталов. Если задать в любом поисковике слово «фрактал», получим такое количество ссылок, что покажется, будто Сеть создана лишь для фракталов. Каждый уважающий себя программист непременно устраивает на своей страничке фрактальную галерею. И не только программист! Владимир Васнев из Анадыря выложил подборку восхитительных изображений, созданных известной программой Fractal Explorer (vasnyov.narod.ru). А недавно Владимир написал мне, что его фракталы будут использованы в оформлении местного Дворца культуры.

Фракталы не только фантастически, обворожительно красивы. Еще лет пятнадцать назад известный популяризатор науки Клиффорд Пиковер (Clifford Pickover) обнаружил фракталы, похожие на клетки живых организмов. Это дало толчок к изучению особых геометрических объектов, так называемых биоморфов, и даже к исследованию их размножения, подчиняющегося законам Моргана о расщеплении наследуемых признаков при скрещивании («КТ» ## 335, 401, 486).

Множество Мандельброта (классический фрактал) строится при помощи многократного возведения в квадрат комплексного числа. Но комплексные числа по формуле Муавра можно возводить в любую степень, в том числе дробную и отрицательную. При этом шипы и колючки неожиданно превращаются в цветочки и бабочки (arbuz.uz/y_muavr.html). Если же в цикле использовать тригонометрические функции или логарифм… приходится чуть ли не силком заставлять себя прекратить эти захватывающие опыты.

К фракталам примыкают аттракторы и репеллеры — таинственные порождения теории хаоса. Сложные аттракторы не обязательно задаются системой дифференциальных уравнений, как, например, бабочка Лоренца. Их может порождать и простейшая на первый взгляд зависимость (так называемое логистическое отображение) Хнов = К · Хстар · (1 – Хстар), таящая в себе неожиданные чудеса.

Общеизвестны объекты вроде ковра Серпинского, снежинки Коха, «кривых дракона», а также более экзотические порождения рекурсии — так называемые L-деревья. Эти потрясающие рисунки обязаны своим появлением программированию и компьютерной визуализации результатов. Визуализация привнесла революционные идеи в методы контроля за различными процессами. График какого-либо многофакторного процесса может порождать цветной узор, позволяющий специалисту судить обо всех тонкостях процесса. Предпринимались также попытки различать узоры от разумного сигнала и белого шума. («Бульон из информации», «КТ» #367). Все это необычайно интересно и практически не требует ничего, кроме фантазии.

Главная функция Сети — доступ желающих к любым сведениям. Это важно и математикам — есть, например, энциклопедия последовательностей (стр. 34), где каждому обратившемуся робот поможет подобрать обобщенную формулу для исходных данных, укажет на дополнительные источники информации. Существуют многочисленные клубы любителей числа π, их страницы так насыщены материалом, будто все за последние тысячелетия человечество только тем и занималось, что уточняло это таинственное число. Если думаете, что про π всё давным-давно известно, — напрасно, то и дело появляются новые и новые результаты исследований, что вынуждает периодически обновлять и мою почти всеохватную «Зону π» на «Арбузе» (www.arbuz.uz).

Общение любителей математики в Сети позволяет им насладиться такими лакомствами, как золотое сечение, интересные числа, цифровые стихи, нумерология, биоритмы, совершенные и дружественные числа, числа Фибоначчи и Люка, треугольник Паскаля, «Ханойская башня», «Книга Перемен», «Игра 15», «История календаря». Плюс разнообразные геометрические, топологические и числовые забавы и масса красивых задач, обсуждаемых в форумах.

Популярная наука не ограничивается занимательной математикой. В онлайне много материалов по генетике, антропогенезу, о мышлении и этологии (науке о поведении животных, благодаря которой мы узнаем много интересного и о себе). Отыскиваются закономерности в таких новых явлениях, как общение в Сети и интернет-зависимость, появляются публикации по истории хайтека и рассказы о чудо-вычислителях и чудо-запоминателях. Палиндромы, флексагоны, гипотеза о причинах исчезновения Арала и еще много всяких любопытных тем выложено на «Арбузе», который стал победителем сетевого конкурса РОТОР 2004 в номинации «Наука и образование» (что лишь подтверждает сильную тягу людей к занимательной и популярной науке — и в Сети, и в жизни).

http://www.divisorplot.com/

ПэЧэ, граф Кэли, кубик Рубика и универсалии

Универсального свойства достаточно, чтобы определить объект с точностью до изоморфизма. Таким образом, появляется ещё один способ доказать, что два объекта изоморфны, а именно доказать, что они обладают одинаковым универсальным свойством.


Определение некоего свойства не гарантирует существование объекта, ему удовлетворяющего. Если однако, такой (A, φ) существует, то он единственен. Точнее говоря, он единственен с точностью до единственного изоморфизма.

https://ru.wikipedia.org/wiki/Универсальное_свойство

Свобо́дная гру́ппа в теории групп — группа ${\displaystyle G}$, для которой существует подмножество ${\displaystyle S\subset G}$ такое, что каждый элемент ${\displaystyle G}$ записывается единственным образом как произведение конечного числа элементов ${\displaystyle S}$ и их обратных. 

Возможно предъявить явную конструкцию свободных групп, доказав тем самым их существование^[1][2]

https://ru.wikipedia.org/wiki/Свободная_группа

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

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

Граф Кэли симметрической группы S₄

Гру́ппа ку́бика Ру́бика — подгруппа симметрической группы S₄₈, 

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

Порядок группы ${\displaystyle G}$ равен^{[2][3][4][5][6]}

${\displaystyle |G|={\dfrac {8!\cdot 12!\cdot 3^{8}\cdot 2^{12}}{3\cdot 2\cdot 2}}=43\ 252\ 003\ 274\ 489\ 856\ 000=2^{27}\cdot 3^{14}\cdot 5^{3}\cdot 7^{2}\cdot 11.}$

==============================================

http://ru.unionpedia.org/Группа_кубика_Рубика

Unionpedia is a concept map or semantic network organized like an encyclopedia – dictionary. It gives a brief definition of each concept and its relationships.

========================================

Если p — простое число, то любая группа порядка p циклическая и единственна с точностью до изоморфизма

====================================

http://esciencecommons.blogspot.ca/2011/01/new-theories-reveal-nature-of-numbers.html

Thursday, January 20, 2011

New theories reveal the nature of numbers

A key creative breakthrough occurred when Emory mathematicians Ken Ono, left, and Zach Kent were hiking. As they walked, they noticed patterns in clumps of trees and began thinking about what it would be like to "walk" amid partition numbers. 

By Carol Clark

For centuries, some of the greatest names in math have tried to make sense of partition numbers, the basis for adding and counting. Many mathematicians added major pieces to the puzzle, but all of them fell short of a full theory to explain partitions. Instead, their work raised more questions about this fundamental area of math.

Now, Emory mathematician Ken Ono is unveiling new theories that answer these famous old questions. (Click here to watch a video of Ono's lecture on the topic.)

Ono and his research team have discovered that partition numbers behave like fractals. They have unlocked the divisibility properties of partitions, and developed a mathematical theory for “seeing” their infinitely repeating superstructure. And they have devised the first finite formula to calculate the partitions of any number.

“Our work brings completely new ideas to the problems,” Ono says. “We prove that partition numbers are ‘fractal’ for every prime. These numbers, in a way we make precise, are self-similar in a shocking way. Our ‘zooming’ procedure resolves several open conjectures, and it will change how mathematicians study partitions.”

The problems of partition numbers "have long fascinated mathematicians," Ono says.

The work was funded by the American Institute of Mathematics (AIM) and the National Science Foundation. Last year, AIM assembled the world’s leading experts on partitions, including Ono, to attack some of the remaining big questions in the field. Ono, who is a chaired professor at both Emory and the University of Wisconsin at Madison, led a team consisting of Jan Bruinier, from the Technical University of Darmstadt in Germany; Amanda Folsom, from Yale; and Zach Kent, a post-doctoral fellow at Emory.

“Ken Ono has achieved absolutely breathtaking breakthroughs in the theory of partitions,” says George Andrews, professor at Pennsylvania State University and president of the American Mathematical Society. “He proved divisibility properties of the basic partition function that are astounding. He went on to provide a superstructure that no one anticipated just a few years ago. He is a phenomenon.”

Child’s play

On the surface, partition numbers seem like mathematical child’s play. A partition of a number is a sequence of positive integers that add up to that number. For example, 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1. So we say there are 5 partitions of the number 4.

It sounds simple, and yet the partition numbers grow at an incredible rate. The amount of partitions for the number 10 is 42. For the number 100, the partitions explode to more than 190,000,000.

“Partition numbers are a crazy sequence of integers which race rapidly off to infinity,” Ono says. “This provocative sequence evokes wonder, and has long fascinated mathematicians.”

By definition, partition numbers are tantalizingly simple. But until the breakthroughs by Ono’s team, no one was able to unlock the secret of the complex pattern underlying this rapid growth.

The work of 18th-century mathematician Leonhard Euler (below) led to the first recursive technique forcomputing the partition values of numbers. The method was slow, however, and impractical for large numbers. For the next 150 years, the method was only successfully implemented to compute the first 200 partition numbers.

“In the mathematical universe, that’s like not being able to see further than Mars,” Ono says.

A mathematical telescope

In the early 20th century, Srinivasa Ramanujan and G. H. Hardy invented the circle method, which yielded the first good approximation of the partitions for numbers beyond 200. They essentially gave up on trying to find an exact answer, and settled for an approximation.

“This is like Galileo inventing the telescope, allowing you to see beyond what the naked eye can see, even though the view may be dim,” Ono says.

Ramanujan also noted some strange patterns in partition numbers. In 1919 he wrote: “There appear to be corresponding properties in which the moduli are powers of 5, 7 or 11 … and no simple properties for any moduli involving primes other than these three.”

The legendary Indian mathematician died at the age of 32 before he could explain what he meant by this mysterious quote, now known as Ramanujan’s congruences.

In 1937, Hans Rademacher found an exact formula for calculating partition values. While the method was a big improvement over Euler’s exact formula, it required adding together infinitely many numbers that have infinitely many decimal places. “These numbers are gruesome,” Ono says.

In the ensuing decades, mathematicians have kept building on these breakthroughs, adding more pieces to the puzzle. Despite the advances, they were unable to understand Ramanujan’s enigmatic words, or find a finite formula for the partition numbers.

“We were standing on some huge rocks, where we could see out over this valley and hear the falls, when we realized partition numbers are fractal,” Ono says. Photo by Zach Kent.

Ono’s “dream team” wrestled with the problems for months. “Everything we tried didn’t work,” he says.

A eureka moment happened in September, when Ono and Zach Kent were hiking to Tallulah Falls in northern Georgia. As they walked through the woods, noticing patterns in clumps of trees, Ono and Kent began thinking about what it would be like to “walk” amid partition numbers.

“We were standing on some huge rocks, where we could see out over this valley and hear the falls, when we realized partition numbers are fractal,” Ono says. “We both just started laughing.”

The term fractal was invented in 1980 by Benoit Mandelbrot, to describe what seem like irregularities in the geometry of natural forms. The more a viewer zooms into “rough” natural forms, the clearer it becomes that they actually consist of repeating patterns (see youtube video, below). Not only are fractals beautiful, they have immense practical value in fields as diverse as art to medicine.

ПэЧэ и КуРу (p-адические числа и кубик Рубика)

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

подумал, что изучение p-адических чисел можно превратить в игру и развлечение на основе идеи кубика Рубика

итак, читаем вики https://ru.wikipedia.org/wiki/Группа_кубика_Рубика

-----------------------------

Гру́ппа ку́бика Ру́бика — подгруппа симметрической группы S<sub>48

...</sub>

Порядок группы ${\displaystyle G}$ равен^{[2][3][4][5][6]}

${\displaystyle |G|={\dfrac {8!\cdot 12!\cdot 3^{8}\cdot 2^{12}}{3\cdot 2\cdot 2}}=43\ 252\ 003\ 274\ 489\ 856\ 000=2^{27}\cdot 3^{14}\cdot 5^{3}\cdot 7^{2}\cdot 11.}$

Пусть ${\displaystyle K_{f}}$ — граф Кэли группы ${\displaystyle G}$ с 18 образующими, которые соответствуют 18 ходам метрики FTM.

Каждая из ${\displaystyle \approx 4{,}32\cdot 10^{19}}$ конфигураций может быть решена не более чем за 20 ходов FTM. Другими словами, эксцентриситет вершины графа ${\displaystyle K_{f}}$, соответствующей «собранному» состоянию головоломки, равен 20^[7].

Диаметр графа ${\displaystyle K_{f}}$ также равен 20^[8].

-----------------------------

грубо говоря, интуитивно РАССТОЯНИЕ для КР - это минимальное число поворотов, за которое он собирается  (максимальное - это 20)

-------------------------------

9 сентября 2010 в 00:56

Разработка → Кубик Рубика за 20 шагов

https://habrahabr.ru/post/103843/

Любая позиция Кубика Рубика может быть решена не более, чем за 20 шагов.

Несколько лет назад было доказано, что для Кубика Рубика есть решение за 23 хода. Теперь это число сократилось до 20. Чтобы это сделать, потребовалось 35 (тридцать пять) лет компьютерного времени, пожертвованного Гуглом.


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

Разумно полагать, что Бог может использовать более эффективный алгоритм, который решает задачу за наикратчайшее число шагов. Этот алгоритм известен как “алгоритм Бога”. Число шагов в худшем случае называется числом Бога. В конце концов, было показано, что это число — 20.

После изобретения Кубика Рубика пятнадцать лет ушло на поиск позиции, которая наверняка решается за 20 шагов. Через 15 лет после этого мы докажем, что 20 шагов достаточно для любой позиции.

История числа Бога

К 1980 году было установлено, нижняя граница — 18, а верхняя — вероятно, около 80. В таблице ниже собраны все результаты:

Как мы это сделали

Как мы справились с 43 252 003 274 489 856 000 позициями Кубика Рубика?

• Мы разделили все позиции на 2 217 093 120 множеств — по 19 508 428 800 позиций в каждом.
• Мы уменьшили число множеств для решения до 55 888 296 на основе симметрии и покрытии множества.
• Мы не искали оптимальное решение, а только решения с длиной 20 или менее шагов.
• Мы написали программу, находящее решение для одного множества за 20 секунд.
• Потребовалось 35 лет компьютерного времени для поиска решений всех конфигураций в каждом из 55 888 296 множеств.

Деление пространства позиций

Мы разбили большую задачу на 2 217 093 120 меньших подзадач: в каждую входило по 19,508,428,800 различных позиций. Одна такая подзадача легко помещается в память современного компьютера, и этот метод позволил достаточно быстро получить решение.

Симметрия

Если повертеть Кубик Рубика влево-вправо или вверх-вниз, то, по сути, ничего не изменится: число шагов в решении останется тем же самым. Вместо того, чтобы решать все эти позиции, можно получить решение для одной и распространить его на повернутые позиции. Есть 24 различных ориентации в пространстве и 2 зеркальных положения Кубика для каждой позиции, что позволяет уменьшить число решаемых позиций в 48 раз. Если использовать аналогичные рассуждения и воспользоваться поиском задачи “покрытия множества”, то число подзадач уменьшается от 2 217 093 120 до 55 882 296.

Хорошие и оптимальные решения

Оптимальное решение содержит достаточное количество шагов, но не больше, чем надо. Так как уже известна одна позиция, для которой требуется 20 шагов, то мы можем не искать оптимальное решение для каждой позиции, а только решения в 20 или менее шагов. Это многократно убыстряет задачу.

Оборудование

У нас была возможность решить 55 882 296 подзадач на мощностях Гугла и выполнить все вычисления за несколько недель. Гугл не раскрывает характеристики компьютеров, но было затрачено 1.1 миллиард секунд компьютерного времени (Intel Nehalem, four-core, 2.8GHz) на выполнение расчетов.

Самая трудная позииция

Мы знали в течении 15 лет, что есть позиции, которые требует 20 шагов, но мы доказали, что ни для одной позиции и не надо больше.

Позиции с решениями в 20 шагов редки, но их вполне возможно встретить в реальности. Вероятность встретить такую позицию варьируется от 10^(-9) до 10^(-8). Мы точно не знаем точное количество таких позиций. Таблица дает оценку числа позиций для каждой длины решения.
 

Для длин от 16 и больше, числа являются примерными. Наши исследования подтвердили все первоначальные данные до 14 строки включительно, а 15 строка — новый результат. На 11 августа мы обнаружили 12 миллионов позиций с длиной решения 20. Эта позиция была самой сложной для наших программ:

---------------------------

теперь попробуем сформулировать проблему в терминах ПэЧэ

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

на этом дереве 5-адических чисел вводим отображение (функцию) и "расстояние"

любая "загогулина" на этом дереве (ПэЧэ), повторенная определенное число раз, возвращает чило "к себе" (визуально можно представить себе стрелочки в обратную сторону)

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

игру можно переделать в форму "бродилки со стрелками телепортации"

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

на полпути "траектория" возврата почти соприкасается с исходной точкой - именно это позволило найти путь к сборке (не самый короткое но всё же решение)

короче, цель головоломки - за минимально число шагов (20 шагов - это вроде с возможностью поворачивать в обе стороны и на 180 градусов - т.е. для 5-алического дерева наверно нужно не больше 52 движений ? ) с учётом автоматической "телепортации" с любой ветки "слезть на землю" (т.е. очутиться в корне 5-адического дерева)

тут можно даже игру бродилку нарисовать - пусть дети с малолетства приучаются мыслить в адических понятиях о расстоянии

ибо как говорил Козьма Прутков - "Бросая в воду камешки, смотри на круги, ими образуемые; иначе такое бросание будет пустою забавою.":-)