魔方吧·中文魔方俱乐部

标题: 3*3*3魔方上帝之数至多为27！ [打印本页]

作者: zslswemz 时间: 2009-9-10 00:00:15 标题: 3*3*3魔方上帝之数至多为27！

3*3*3魔方上帝之数至多为27

[ 本帖最后由 zslswemz 于 2009-9-10 00:52 编辑 ]

作者: 今夜微凉 时间: 2009-9-10 00:02:27

请给个证明？26早早就被证了~http://bbs.mf8-china.com/viewthread.php?tid=7815&extra=page%3D1，看楼主UID那么靠前~这居然是处女帖~汗一个~

[ 本帖最后由今夜微凉于 2009-9-10 00:08 编辑 ]

作者: zslswemz 时间: 2009-9-10 00:04:28

一个魔方出厂时每个面各有一种颜色，总共有六种颜色，但这些颜色被打乱后，所能形成的组合数是多少？
在组成魔方的小立方体中，有 8 个是顶点，它们之间有 8! 种置换；这些顶点每个有 3 种颜色，在朝向上有 37 种组合 (由于结构所限，魔方的顶点只有 7 个能有独立朝向)。类似的，魔方有 12 个小立方体是边，它们之间有 12!/2 种置换 (之所以除以 2，是因为魔方的顶点一旦确定，边的置换就只有一半是可能的)；这些边每个有两种颜色，在朝向上有 211 种组合 (由于结构所限，魔方的边只有 11 个能有独立朝向)。因此，魔方的颜色组合总数为 8!×37×12!×211/2 = 43252003274489856000，即大约 4325 亿亿。

作者: zslswemz 时间: 2009-9-10 00:05:42 标题: 回复 2# 的帖子

看我的证明啊！上帝之数至多为27！

[ 本帖最后由 zslswemz 于 2009-9-10 00:51 编辑 ]

作者: 小波 时间: 2009-9-10 00:08:10

楼上能说明什么呢

作者: 今夜微凉 时间: 2009-9-10 00:12:04

恕在下才疏学浅~没看懂和“27”〔或者说“27以内都是错的”〕有什么关系~真没看懂~

作者: windancerlxp 时间: 2009-9-10 00:13:01

没看出楼主的证明和这个步数有什么关系

作者: superacid 时间: 2009-9-10 00:16:18

请LZ说明确一点

作者: zslswemz 时间: 2009-9-10 00:16:38

一个魔方转动一下可以出现27个组合。再转一下有27*24种组合（27*27就包含有一些回到上一步的重复组合，下面也有一些重复就不再计算）
转一次：  27                                     =                27
转两次：  27*24                                  =                648
转三次：  27*24*24                               =             15552
转四次：  27*24*24*24                            =             373248
转五次：  27*24*24*24*24                         =             8957952
转六次：  27*24*24*24*24*24                      =          214990848
转七次：  27*24*24*24*24*24*24                   =          5159780352
转八次: 27*24*24*24*24*24*24*24                =       123834728448
转九次：  27*24*24*24*24*24*24*24*24             =       2972033482752
转十次：  27*24*24*24*24*24*24*24*24*24          =    71328803586048
转十一次：27*24*24*24*24*24*24*24*24*24*24       =    1711891286065152
转十二次：27*24*24*24*24*24*24*24*24*24*24*24    = 41085390865563648
转十三次：27*24*24*24*24*24*24*24*24*24*24*24*24 = 986049380773527552
转十四次：27*24*24*24*24*24*24*24*24*24*24*24*24*24= 23665185138564661248

作者: MJ_Colonel 时间: 2009-9-10 00:17:34

呃，慢慢看看，不是很好懂

[ 本帖最后由 Lonely_Dragon 于 2009-9-10 00:21 编辑 ]

作者: superacid 时间: 2009-9-10 00:18:35

这样得到的数比魔方状态种数多很多

作者: happydufei 时间: 2009-9-10 00:22:40 标题: 回复 1# 的帖子

我看看uid 额上帝之数是什么东东。。

作者: zslswemz 时间: 2009-9-10 00:23:20

魔方A代表启示状态，魔方B代表还原成的状态。
两个魔方各转14次以内得到总组合数大于2366,5185,1385,6466,1248*2>4325,2003,2744,8985,6000,因此组合有重复，
上帝之数至多为14*2-1=27.

[ 本帖最后由 zslswemz 于 2009-9-10 00:50 编辑 ]

作者: superacid 时间: 2009-9-10 00:29:04

提示楼上：是平方，不是*2...

作者: 奇遇 时间: 2009-9-10 00:40:29

暴强果然是暴强啊，牛逼

作者: 逗鱼 时间: 2009-9-10 00:46:12

LZ忽略了好多东西~~~~《geek》或者是《新知客》这两本中的一本上已经研究过上帝之数~没有楼主想的那么简单~~

作者: zslswemz 时间: 2009-9-10 01:00:34 标题: 重新整理：3*3*3魔方上帝之数至多为27！

一个魔方出厂时每个面各有一种颜色，总共有六种颜色，但这些颜色被打乱后，所能形成的组合数是多少？
      在组成魔方的小立方体中，有 8 个是顶点，它们之间有 8! 种置换；这些顶点每个有 3 种颜色，在朝向上有 37 种组合 (由于结构所限，魔方的顶点只有 7 个能有独立朝向)。类似的，魔方有 12 个小立方体是边，它们之间有 12!/2 种置换 (之所以除以 2，是因为魔方的顶点一旦确定，边的置换就只有一半是可能的)；这些边每个有两种颜色，在朝向上有 211 种组合 (由于结构所限，魔方的边只有 11 个能有独立朝向)。因此，魔方的颜色组合总数为 8!×37×12!×211/2 = 43252003274489856000，即大约 4325 亿亿。
   一个魔方转动一下可以出现27个组合。再转一下有27*24种组合（27*27就包含有一些回到上一步的重复组合，下面也有一些循环重复就忽略不计）
转一次：  27                                     =                27
转两次：  27*24                                  =                648
转三次：  27*24*24                               =             15552
转四次：  27*24*24*24                            =             373248
转五次：  27*24*24*24*24                         =             8957952
转六次：  27*24*24*24*24*24                      =          214990848
转七次：  27*24*24*24*24*24*24                   =          5159780352
转八次: 27*24*24*24*24*24*24*24                =       123834728448
转九次：  27*24*24*24*24*24*24*24*24             =       2972033482752
转十次：  27*24*24*24*24*24*24*24*24*24          =    71328803586048
转十一次：27*24*24*24*24*24*24*24*24*24*24       =    1711891286065152
转十二次：27*24*24*24*24*24*24*24*24*24*24*24    = 41085390865563648
转十三次：27*24*24*24*24*24*24*24*24*24*24*24*24 = 986049380773527552
转十四次：27*24*24*24*24*24*24*24*24*24*24*24*24*24= 23665185138564661248
魔方A代表启示状态，魔方B代表还原成的状态。
两个魔方各转14次以内得到总组合数大于2366,5185,1385,6466,1248*2>4325,2003,2744,8985,6000,因此组合有重复，设重复组合中其中一个组合为C,折A->C->B的步数<=14+14-1=27,所以上帝之数至多为14*2-1=27.

这里的转动一次是指将魔方的任意一个面(包括3个中间的面，一共9个面）沿顺时针或逆时针方向转动 90° 或 180°，对每个面来说，这样的转动共有 3 种。因此开始的可能性为27，再转动一次的可能性为24.

[ 本帖最后由 zslswemz 于 2009-9-10 01:20 编辑 ]

作者: zslswemz 时间: 2009-9-10 01:07:50

哈哈！题目改了，对了吧！

作者: zslswemz 时间: 2009-9-10 01:27:33

1995 年，里德通过计算发现，最多经过 12+18=30 次转动，就可以将魔方的任意一种颜色组合复原。
在得到上述结果后，里德很快对自己的计算作了改进，将结果从 30 减少为了 29，这表明 “上帝之数” 不会超过 29。此后随着计算机技术的发展，数学家们对里德的结果又作进一步的改进，但进展并不迅速。直到 11 年后的 2006 年，奥地利开普勒大学 (Johannes Kepler University) 符号计算研究所 (Research Institute for Symbolic Computation) 的博士生拉杜 (Silviu Radu) 才将结果推进到了 27。第二年，即 2007 年，美国东北大学 (Northeastern University) 的计算机科学家孔克拉 (D. Kunkle) 和库伯曼 (G. Cooperman) 又将结果推进到了 26，他们的工作采用了并行计算系统，所用内存高达 700 万兆，所耗计算时间则长达 8000 小时 (相当于将近一年的 24 小时不停歇计算)。
2006年才得出3*3*3魔方上帝之数至多为27？

作者: schuma 时间: 2009-9-10 02:44:09

嗯，2006年的上界是27，2007年还是 Kunkle 和 Cooperman把它减小到26。2008年里 Tomas Rokicki 把它减少到了22。他宣布22步的上界参见这里
http://cubezzz.homelinux.org/drupal/?q=node/view/121

作者: 今夜微凉 时间: 2009-9-10 04:23:16

呃，这个标题就没问题了~但是“14+14-1”中的“减1”是为什么呢？A->C需要至多14步，C->B需要至多14步，那A->B就需要至多28步吧~〔可以这样简化想，如果A->C需要至多1步，C->B需要至多1步，那A->B就至多需要2步了，需要减1吗？〕，睡不着~失眠啊~凌晨4点半，只有4个会员在线~感觉好独特~

[ 本帖最后由今夜微凉于 2009-9-10 04:26 编辑 ]

作者: Zeon.C 时间: 2009-9-10 06:46:28

不是说很可能是21么…

作者: zslswemz 时间: 2009-9-10 07:18:05

昨天晚上就这么想的，现在给你一提，还真的不该减一，看来题目又要重编辑了。

作者: xhzwd 时间: 2009-9-10 08:13:58

应该是22步吧？？？

作者: 今夜微凉 时间: 2009-9-10 08:27:26 标题: 回复5楼7楼

这帖是楼主用了很简单的方法就证出至多28步内就能还原魔方~本身就没想证22，21步~22，21步如果能这么轻松~那近几年的疯狂穷举证明就白费了~

作者: purple 时间: 2009-9-10 08:58:42

传说中的民科？？

作者: xuelinji9568 时间: 2009-9-10 09:03:22

晕了，晕了~还是看不懂~

作者: 无为子 时间: 2009-9-10 11:38:21

数学不好，只能看热闹
只看懂了这个
魔方的颜色组合总数为 8!×37×12!×211/2 = 43252003274489856000，即大约 4325 亿亿。

作者: 乌木 时间: 2009-9-10 15:58:03

3的7次方可以写成3^7，或在编辑时把7改为上标：：3[sup]7[/sup] 。

作者: noski 时间: 2009-9-10 20:07:16

楼主没有计算就直接把循环重复的状态忽略了，这属于猜测。

魔方转14次，楼主算得是有2366,5185,1385,6466,1248个组合，
如果我说这2366,5185,1385,6466,1248个状态里有一半是重复的，于是，两个魔方各转14次以内得到总组合数：
（2366,5185,1385,6466,1248 / 2）*2 < 4325,2003,2744,8985,6000, 因此它们没有交集，上帝之数也不是27。

楼主怎么证明我上面说的是错的？

作者: zslswemz 时间: 2009-9-10 21:17:25

12楼说的对！循环重复的状态如何剔除是较难的问题，其实如果能把转n次的组合能准确算出的话，那上帝之数就出来了。
看我的证明中算出一个魔方转15次的组合超出4千亿亿，那是不是上帝之数就是15呢？显然不是。因此在计算转n次后可能出现的魔方组合中一定要剔除循环重复的部分！

作者: zslswemz 时间: 2009-9-10 21:59:48

3*3*3循环公式中循环步数和周期之积很少有20以内的，因此转14次得到的实际组合和27*24*24*...*24(一共13个24相乘)结果相差不大。因此转15次得到的实际组合和27*24*24*...*24(一共14个24相乘)结果相差不大，大于3*3*3魔方的总组合数，因此上帝之数为15.

另外请注意：这里的转动一次是指将魔方的任意一个面(包括3个中间的面，一共9个面）沿顺时针或逆时针方向转动 90° 或 180°。
而《魔方与 “上帝之数”》文中转动是指将魔方的任意一个 (包含 9 个小方块的) 面沿顺时针或逆时针方向转动 90° 或 180°，这是有区别的。

作者: 魔鱼儿 时间: 2009-9-10 22:06:11

看不大明白,这个数字最终会是多少呢?

作者: ursace 时间: 2009-9-10 22:22:10

不是已经证明到26了么？

作者: zslswemz 时间: 2009-9-10 22:35:57

上帝之数越小越好！现在有人证到22（证明方法使用了群论，数学系大学毕业的也没几人能看懂）。
我粗粗地找了一下上帝之数为15.哈哈！
不过如果准确找到转n次过程中出现的总组合（剔除重复）等于魔方的所有组合数，则上帝之数<=n。

[ 本帖最后由 zslswemz 于 2009-9-13 23:48 编辑 ]

作者: 乌木 时间: 2009-9-11 09:10:39

17楼说“转n次过程中出现的总组合（剔除重复）大于魔方的所有组合数，则上帝之数<=n”，好像此话自身是矛盾的，等于说一个数A大于自身A，不是矛盾的吗？

从某一事先确定好的初态出发，到达魔方的任一状态，路线不是唯一的，所以，两态之间魔方表层的转动次数n不是唯一的。这些不同的n值之中，有一个是两态之间的最少步数。不同的两态，对应于不同的最少步数。不同的最少步数总有个上限，对此，人们的认识，随着计算方法的改进和计算机性能的提高，一次次在改变。

还有，中层转可以等价于两个表层转，不必考虑中层转动数的，能精简就精简，也可以统一转动次数的统计法。

[ 本帖最后由乌木于 2009-9-11 09:56 编辑 ]

作者: zslswemz 时间: 2009-9-13 23:36:09

转n次过程中出现的总组合（剔除重复）等于魔方的所有组合数，则上帝之数<=n。

作者: zslswemz 时间: 2009-9-13 23:45:53

“转动一次”定义不同，上帝之数就不同。
如将一个六面魔方中间面转动一次（我的“转动一次”定义）的状态要转动两次（《魔方与 “上帝之数”》文中定义）才能回到初始状态。

作者: 今夜微凉 时间: 2009-9-14 19:06:50

晕~~我说怎么跑热门了呢~~~原来是合并了~~研究无极限！思维无极限！

作者: cod 时间: 2009-9-14 20:11:55

超级技术贴纯灌水留言。

作者: 2rabbits 时间: 2009-9-14 21:07:39

本人不参与学术界讨论！

作者: _Neo__ 时间: 2009-9-14 21:19:23

是21！我看过这方面文章

作者: JLXBD 时间: 2009-9-15 20:41:13

什么啊！不懂，来学习了！

作者: lernem 时间: 2009-9-16 17:57:24

晕了楼主求扫盲

作者: Icet0wn 时间: 2009-9-16 20:46:50

有LZ想的这么简单那上帝之数就不是上帝之数了...

作者: 497672121 时间: 2009-10-19 21:58:14

慢慢研究。。。。。。。。。。。。。。。。。。。。。。。。。。。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)