关于魔方最少步数的问题

骰迷

看來我是表達錯誤了，Y只可能往上、平行和向下兩層兼合
X只可能往上、平行兼合
所以通常那些打亂魔方的程式都不是一步一步算的，因為動了單數步/雙數步都只能達到總狀態數一半的狀態，雖然還是很多，一輩子都玩不完，但還是較不公平一些
小籠包兄和樓主在＂最長例外列＂中的證明做得很好看，雖然沒全搞懂，希望他快點找到這裡吧，我可不會

乌木

嗯。这种时候，X走一步所得到的态Y，Y消同态和不消同态，在态树上的位置虽然不同，但两个位置的Y的步数和X的步数，两者之差的绝对值都是1。

这和“Y的步数不该算作（N＋1）而应该算作（N－1）”是两个问题，且这两个问题谈不上冲突的。

我举这个第四代的“UUU”合并为第二代的“U' ”的例子，只是表明我反对“Y不可能往下兼合”这种说法而已。

[ 本帖最后由 乌木 于 2009-2-14 20:10 编辑 ]

骰迷

那麼X就是U2，Y既是N+1，又是N-1，這和我的意見沒有衝突。X和Y的步數必相差一，要不就是零。題目就是要證明一定不能是零。

xiaobao

看不明白，不懂呀！最小步很难不知道该如何学习。

乌木

原帖由 乌木 于 2009-2-13 23:16 发表
何以见得？在建立态树时，原来Y那个位置（N＋1步的位置）已经被消同态了。但是在单独考查这原来Y位置的原父代X时，这X完全可以再次走一步而到达Y，不料此处是个“空号”，只好空欢喜一场，一下子跌到更低处了－－看看状态还是和Y一样，但是和X0的距离却小于N＋1了。

补充：用具体一些的例子来说吧。
0步态   X0 。
1步态 （用X0做一步动作的符号U、U' ……等等来表示1步态）U， U'， D， D'， L， L'， R， R'， F， F'， B， B'  ，共12个1步态。
2步态   每个1步态有11个后代（2步态），所以，刚才的12个1步态共有可能的2步态数目为12×11＝132个，但是这同一代内部要消去18个同态（比如UU＝U'U' ，UD＝DU，……等等）。故X0的2步态只有114个，分别是UU，UD， UD'  ……等等。
3步态    且看一个2步态UU，它再走一步U，得到3步态UUU，可是UUU＝U'，这个3步态UUU应该合并到同态U'，而U' 却是个1步态！！！

这最后一个例子说明问题了吧？！

注：X0不一定要用复原态，任何一个态出发，变化都是上述规律。但老祖宗X0取复原态的话，看起头几代来较简明直观。

骰迷

那麼Y完全可以再走一步到達X啊。這樣的話，X反而變成了Y+1。但那也符合題意。
只是如果N因此而變小了，那麼就不合法了。由此看來，Y既等於N+1，合拼後又等於N-1了。如果是其他數字，N就會因而變小，不符題意。

[ 本帖最后由 骰迷 于 2009-2-13 23:29 编辑 ]

乌木

何以见得？在建立态树时，原来Y那个位置（N＋1步的位置）已经被消同态了。但是在单独考查这原来Y位置的原父代X时，这X完全可以再次走一步而到达Y，不料此处是个“空号”，只好空欢喜一场，一下子跌到更低处了－－看看状态还是和Y一样，但是和X0的距离却小于N＋1了。

[ 本帖最后由 乌木 于 2009-2-14 10:17 编辑 ]

lulijie

28楼误会了我的意思，我题目的意思是每步只允许转90度。

骰迷

回樓主：我理解題目有點錯誤了，必須重新思考。我理解的版本是：只可轉180度。

[ 本帖最后由 骰迷 于 2009-2-13 23:13 编辑 ]

骰迷

以角先法作證明比較易懂。（雖然我沒學過角先法，但想來也是差不多吧。）
第一部分：角的還原步數奇偶性必和打亂步數的奇偶性相同

第二部份：稜的還原必為雙數步

[ 本帖最后由 骰迷 于 2009-2-13 23:15 编辑 ]