полезно в хозяйстве

[avva]

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

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

Если один поворот занимает одну секунду, то в среднем кубик будет полностью собран за время, равное примерно 50 возрастам Вселенной на сегодняшний день.

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

Comments

[vladimir000]

Мне как-то казалось, что существование такого цикла практически очевидно. Или он его построил и в это мдостижение?

кстати, более стандартное наблюдение,

[a-shen.livejournal.com]

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

[avva.livejournal.com]

Достижение и в том, что построил, но в общем-то даже существование не кажется мне столь уж очевидным. Я не знаю, было ли оно доказано до этого построения.

Re: кстати, более стандартное наблюдение,

[avva.livejournal.com]

Я этим занимался на скучных уроках в школе. Помню, что период был неожиданный, кажется, 105 (собственно, 3x5x7, так что логично, но *тогда* мне эта мысль не была доступна).

а из чего это

[a-shen.livejournal.com]

существование следует? есть какие-то общие причины?

[norian.livejournal.com]

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

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

[avva.livejournal.com]

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

[norian.livejournal.com]

то есть нужно не только гарантировать все комбинации, а избежать их повторения

это сложнее, да :о))

[avva.livejournal.com]

Да. Я забыл это упомянуть? Упс :) сейчас исправлю.

Re: кстати, более стандартное наблюдение,

[utnapishti.livejournal.com]

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

Re: а из чего это

[francis-drake.livejournal.com]

В тексте поста не хватает пояснения, что в гамильтоновом пути нет петель.

[occuserpens.livejournal.com]

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

[occuserpens.livejournal.com]

Потому как Гамильтоновский

[alaev.livejournal.com]

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

А как выглядят эти подходы?

[xaxam.livejournal.com]

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

И это только "Р", а найти его - огого какой "NP"!

[freedom_of_sea.livejournal.com]

Почему он назыаается гамильтонов?

[freedom_of_sea.livejournal.com]

Шпионы с колодами карт были, шпионы с кубиками рубика в качестве шифроблокнотов.

[xxxxx.livejournal.com]

цимес этой теоремы в "пределах терпения", то есть существование разумной оценки на количество шагов. Это элементарно? Мне например сразу вот так не очень ясно, откуда там пятёрка выскакивает. Семёрка и тройка вроде понятно.

[david-2.livejournal.com]

"Если один поворот занимает одну секунду, то в среднем кубик будет полностью собран за время, равное примерно 50 возрастам Вселенной на сегодняшний день"

"Хе, и я так могу" (с) Промокашка.

[a-konst.livejournal.com]

Простите, что Вас сдерживает от того, чтобы вбить в гугл "гамильтонов цикл"?

[utnapishti.livejournal.com]

Прежде всего, заметь, что, если ты по очереди крутишь две грани с общим ребром (каждую из них всегда в одну и ту же сторону), есть два способа это делать. В одном из них (более естественном анатомически - каждая грань крутится по часовой стрелке, если смотреть на неё снаружи), орбиты собственно кубиков имеют длину 7 и 5 (пар движений) - 7 у срединных, 5 у угловых. (Есть один угловой кубик, у которого оно вовсе 1, что ничему не мешает.) Соответственно, после 35 пар движений все кубики возвращаются на место. По-видимому, угловые при этом провернулись на 120 градусов, поэтому нужно повторить 3 раза, пока всё точно встанет на место.

[xxxxx.livejournal.com]

мне это представляется ацки сложным. Таки наверное проще выписать в явном виде обе перестановки (угловых и рёберных) и пересчитать в ней циклы. И заметь ещё: вот углы-то ПО-ВИДИМОМУ повернулись (на самом деле это как раз сразу видно --- тот твой туда-сюдашный уголок, который неподвижная точка таки крутится, то есть он и требует множителя 3, а на остальных тогда можно наплевать, раз хоть про одного знаем, что крутится), а вот из рёберных никто не перекувырнулся? ну раз ответ нечётный, то конечно нет, но если заранее ответа не знать, то задолбаешься за ними следить. Ну и вообще, начали с "элементарно" и договорились до "орбит", хе-хе. Кстати мне "анатомически" больше нравится другой, без неподвижных точек, там такой же ответ?

[utnapishti.livejournal.com]

Да чего там аццкого, вот все циклы, что есть.



Про рёберные кубики ты прав, но наверняка там какой-нибудь инвариант несложный; и про угловые тоже прав - я сам это понял, когда шёл с обеда (в смысле, что ТОТ кубик провернётся). Но вот что касается "начали с "элементарно", а договорились до орбит", так я только по поводу того говорил "элементарно", что вернёмся к исходному положению, а не по поводу того, сколько нужно шагов. (Да и орбиты-то тут довольно гнилые, единственное математическое понятиэ, которое тут нужно, это эл-си-эм).

Во втором, кажется, на 5 ничто не делится.

[xxxxx.livejournal.com]

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

А с инвариантами такое дело: когда они есть, они все несложные, а когда он нужен, но его не видать, то охрененно сложная задача ;)

[utnapishti.livejournal.com]

Для тех, кто не проходил эл-си-эм, в данном случае можно соврать, что это просто пэ (ну или пи): 1*3*5*7, оппа! А тем, кто ищет во всём высший смысл, предложим подумать, нет ли какой-нибудь особенной причины, по которой это произведение первых идущих подряд нечётных чисел! - "А может быть, для кубика 4х4х4 это будет 1*3*5*7*9*11 ???"

Re: а из чего это

[gegmopo4.livejournal.com]

«проводит кубик сквозь все возможные конфигурации, посещая каждую ровно один раз»

Re: а из чего это

[francis-drake.livejournal.com]

Теперь хватает.

[gaz-v-pol.livejournal.com]

Подумал над Вашей задачей. А правильно ли будет понимать, что длина периода разная в зависимости от того, поворачиваем ли мы верхнюю грань направо или налево? Вроде бы получается 63 и 105, если я не ошибся при подсчете без кубика.

[xxxxx.livejournal.com]

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

[utnapishti.livejournal.com]

Oh, Herr Krämer, hier entsteht wohl grad' eine Verallgemeinerung!

[xxxxx.livejournal.com]

Ну чо, пиши статью, не забудь указать благодарность уютной жежешечке на предоставленную коллаборативную платформу и моей конторе за предоставление средств на пропитание одного из автороф

[utnapishti.livejournal.com]

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

[xxxxx.livejournal.com]

смотри, научная задача. Типа дана матрица NxM записанная в одномерный массив по строкам. А хочется её иметь записанной в тот же массив по столбцам. Дальше три варианта (а) дополнительной памяти дано O(NM) но с малой константой (б) её дано ровно NM бит + O(1) и наконец (в) её дано просто O(1). Все три варианта абсолютно тривиальны, но имеется реферируемый математический журнал (из матскинета), который в 200х году про это опубликовал статью каких-то испанских овощей. Так что вот.

[avva.livejournal.com]

Без кубика это слишком сложно для меня :) но да, я помню что период разный в этих двух случаях, только не помню, действительно ли 63.

[trurle.livejournal.com]

https://ru.wikipedia.org/wiki/%D0%93%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2_%D0%B3%D1%80%D0%B0%D1%84#.D0.9A.D1.80.D0.B8.D0.BF.D1.82.D0.BE.D0.B3.D1.80.D0.B0.D1.84.D0.B8.D1.8F

[(Anonymous)]

В термодинамике есть аналогичная теорема о возвращении.

[occuserpens.livejournal.com]

ага, спасибо

[musatych.livejournal.com]

Гамильтон изобрёл настольную игру Икосиан, где надо было пройти по всем вершинам додекаэдра.

[huzhepidarasa.livejournal.com]

Royle's conjecture: "All Cayley graphs are Hamiltonian".

[gaz-v-pol.livejournal.com]

До кубика так и не добрался, но ехал долго в электричке и проверил еще раз в уме -- вроде бы правильно, 63 и 105. Естественно, в уме надо не 63 действия делать (это вряд ли кто-то в уме способен сделать), а только:

7 для угловых кубиков, игнорируя, что происходит с боковыми (и тогда видно, что через 9 таких операций угловые вернутся на круги своя)

(теперь эту первую часть можно забыть)

9 для боковых кубиков, игнорируя, что происходит с угловыми (и тогда видно, что через 7 таких итераций боковые вернутся в исходное положение)