|||
答魔方网友:回答你的问题需要“魔方代数”
我在我的《魔方和数学建模》视频公开课第3讲里,提出两个命题。
命题1:
任何操作序列对处于原始状态的魔方进行操作,必然还能回到原始状态。
命题2:
如果能找到一个操作序列,用这个操作序列操作处于原始状态的魔方,得到的状态 是距离原始状态最远的状态,那么,这个操作序列的操作周期必然等于2。
对于第1命题,没有人能找出反例推翻这个命题。
假如有人真找到了一个反例,通过演示即可判断这个“反例”的真伪。
对于第2个命题,在视频公开课里是针对Google公司一个小组的工作(在第1讲已经提到)。那个小组在网络里声称:他们找到了距离魔方原始状态最远的魔方搅乱态,并且给出了一个具体的例子(20步操作序列)。
针对他们的那个20步操作序列,我提出命题:
【如果能找到一个操作序列,用这个操作序列操作处于原始状态的魔方,得到的状态是距离原始状态最远的状态,那么,这个操作序列的操作周期必然等于2。】
显然,我的命题是个必要条件。如果他们的那个20步操作序列能把魔方搅乱到距离原始状态最远的状态,则它的循环周期必然是2。在视频公开课里我说:他们给出的这个20步操作序列满足必要条件,即循环周期是2。但是,他们的这个20步操作序列到底能不能把魔方搅乱到距离原始状态最远,我无法鉴定。
因为充分条件涉及到“魔方代数”问题(后面再讨论)。
先说说网友的问题和我的答案。
网友说:【关于命题2,有网友找到了如下反例:
F U' F2 D' B U R' F' L D' R' U' L U B' D2 R' F U2 D2, 使用该操作序列操作处于原始状态的魔方后,魔方将处于距离原始状态最远的状态 之一(距离原始状态20步)。但这个操作序列的周期为6。与命题2矛 盾。】
我的第一次简单回答是:你的20步操作是不是独立的?
网友不理解“独立”概念,现在展开讨论如下。
我的回答是:
1)如果你的操作序列(红色字母串)的循环周期是6,这本身就证明你的操作序列不可能把魔方搅乱到距离原始状态最远,因为能把魔方搅乱到距离原始状态最远的操作序列,其循环周期必然是2。(当然了,这是我的命题2,^_^)
2)实际上,你(网友)给出的例子是自相矛盾的。
(a)你一方面声称你的操作序列(红色字母串)能把魔方搅乱到距离原始状态最远;
(b)你已经实际操作证明你的操作序列的循环周期是6。
对于以上a、b两点,我更坚信(b)。
我可以简单地用你的(b)点,逻辑地证明你的操作序列(红色字母串)不可能把魔方搅乱到距离原始状态最远的状态。换句话说,如果你的操作序列的循环周期是6的话,你那个20步的红色字母串不是距离魔方原始状态最远,距离魔方原始状态最远的是循环谱上的另外一段,距离魔方原始状态有100步。
你找到的20步操作序列,把魔方操作到当前态(如图所示),显然,另外一段距离魔方的原始状态更远,有100步。一边是20步,一边是100步,自相矛盾。
Google公司的一个小组用了35CPU年证明,把魔方搅乱到距离原始最远的状态,只需要20步。
在此基础上,我提出了一个命题:如果能找到一个操作序列,用这个操作序列操作处于原始状态的魔方,得到的状态 是距离原始状态最远的状态,那么,这个操作序列的操作周期必然等于2。
Google公司的一个小组给出的一个20步操作序列,其循环周期是2,满足必要条件。但是,他们给出的操作序列到底能不能把魔方搅乱到距离原始状态最远的状态,这需要计算,涉及到“魔方代数”。
例如,下面的4步操作序列和5步的操作序列,操作魔方后的结果是完全相同的。
4步操作序列:G 1 R 1 S1 B 1(BF’ D L)
5不操作序列:R 2 G1 R 3 S 1 B 1(F2B F D L)
以上的4步操作是独立的,即我用所有可能的“四字母串”操作魔方后,如果魔方的状态有相同的,或者和“三步字母串”、“二步字母串”、“一步字母串”的相同,则要消除这些操作序列,只保留1个。因此,4步的独立操作状态有43,239个。5步的独立状态有574,908个。一般步数越大,独立的状态越多,但是,截止点是20步。
因此,网友的F U' F2 D' B U R' F' L D' R' U' L U B' D2 R' F U2 D2,这个20步操作序列,能不能给出真正的属于“20步独立”的状态,即要排除你这个20步操作字母串的操作结果是否和“19步字母串”、“18步字母串”、“17步字母串”、------、“1步字母串”等的操作结果相同?完成这种判断,需要计算,工作量巨大,Google公司的一个小组花费了35CPU年(还加上了群论简化)。
(红色补丁是网友的名字,这里保护网友的隐私)
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-24 12:39
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社