推 mikisummer:夭壽.. 10/20 23:04
推 daleleu: 夭壽.. 10/20 23:04
推 william25836:我暈了 10/20 23:08
→ twmstudentkf:跟我最近學的演算法還有離散數學好有感覺喔...真HIGH 10/20 23:44
推 CHOIP:嗯，推一下，太厲害了...... 10/20 23:58
推 rehearttw:推數學高手！ 10/21 06:14
※ 引述《XII (MathKid)》之銘言：
: ※ 引述《seanwu (Blindest)》之銘言：
: : 我目前試過的手順，大概轉個一定數量就會轉回來(R Y' - 約700次)
: : 所有的手順到最後一定會解回來，
: : 這很容易證明：
: : 魔方組合數是有限的，依鴿籠原理，最後一定重複
抱歉沒有寫得很仔細
: 這其實是代數中的group(群)的概念(或可說是group action)
===================
Definition A group (G,*) is a set G, closed under a binary operation *
s.t. the following axioms are satisfied:
G1 For all a,b,c in G, we have (a*b)*c=a*(b*c)
G2 There is an element e in G s.t. for all x in G, we have x*e=e*x=x
G3 For any a in G, there is an element a' in G s.t. a*a'=a'*a=e
===================
e.g. G=(Z_2,+) Z_2={0,1} 定義 0+0=1+1=0, 0+1=1+0=1 是一個群
這裡 e = 0 0'=0 1'=1
一般而言運算符號 * 是可以用任意符號寫的(反正只是個符號)
但通常寫成 + 是代表 G 是可交換的(abelian)
(所以我下面不寫 + 是因為此時 G 不可交換)
寫成 * 則不一定可交換
: 這個group G 有6個 generator i.e. U,D,F,B,L,R
: 寫成 G = < U,D,F,B,L,R | ~~ > 後面~~是一些relation
: e.g. U^4 = UUUU = 1(不動) , (RUR'U')^6 = 1 ...etc
^^^^^^^^^^
^ 的確是次方的意思, 就是同樣的步驟做幾次
X^1=X
X^2=X*X=XX (同樣的步驟做2次)( ( RUR'U' )^2 = RUR'U' RUR'U' )
X^3=(X^2)*X=XXX
....
X^n=(X^(n-1))*X
: 容易算出 |G| = (8!)(3^7)(12!/2)(2^11) = 8!12!(2^10)(3^7)
: 由群論(group theory)易知:
(此為 Lagrange Throrem)
: 任意手順 X (e.g. X=RUR'U') 回覆所需的步數(order) |X| 整除魔方組合數 |G|
: e.g. |U| = 4 整除 |G|
: |RUR'U'| = 6 整除 |G|
: |Ry'| = 4*|RBLF| = 4*9*5*7 = 1260 整除 |G|
: (任意手順 X 均可手算最少回覆步數(order))
: : 曾經想過"懶人解法"
: : 如果有個手順，回覆所需的步數洽等於魔方組合數
: 不會
: proof
: 若有某個手順 X (e.g. X=UBFB'...) 回覆所需步數 = |G|
: (用代數說法,即 G 是cyclic,亦即 G 可用一個元素生成)
: 則 G 中每個元素均可表為 X^n for some n
: 即可設 R = X^m , U = X^n
: 則 RU = (X^m)(X^n) = X^(m+n) = (X^n)(X^m) = UR
: 但明顯地 RU =\= UR (G is not abelian)
: 矛盾
: QED
: (G is cyclic ==> G is abelian ==> contradiction !)
: : 那是不是同樣的步驟轉個幾兆京次，就會解回來......
他這邊本來的意思是(應該是...)
同樣的手順 X (例如 Ry ) 一直做, 會不會做 |G| 次才回覆(答案是no, 證明如上)
X 不一定是 |G| 步的轉法
例如 X =RUR'U' 是四步的轉法, 但 ( RU'R'U )^6 = 1(即做6次可回復) 6=/=|G|
把 X 做 |G| 次一定可以回覆, 但會不會做不到 |G| 次就回復了?
例如前述的 X = Ry , 只要做1260次即可回復
若不考慮位置的對稱性, Ry 只能轉出1260種組合
若一開始做 Ry 的位置不同, 也只能轉出 1260*4*6=30240 種組合
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.121.118.13