魔方与群论：借助Rubik's Cube理解Group Theory

需积分: 31 154 浏览量更新于2024-07-20 1 收藏 387KB PDF 举报

"通过魔方理解群论" 这篇文档，"Group Theory via Rubik's Cube"，由Tom Davis撰写，旨在以一种更为直观的方式介绍数学中的群论概念，特别是通过魔方这一广为人知的益智玩具来阐述。群论是数学的一个核心分支，通常学习起来较为抽象，对许多学生来说可能难以理解。而魔方，尤其是其背后的排列性质，与群论有着密切的联系，因此成为了解释群论概念的绝佳实例。文档首先强调，即使对于一个全新的魔方，也不建议立即打乱它，因为第2节的某些练习在解决立方体的状态下会更易于进行。如果已经打乱了魔方，也不必担心，附录A提供了还原魔方的方法，尽管初试时可能会犯错。在整篇文档中，作者交替探讨了群论和魔方的主题，利用群论的工具来解决魔方问题，同时利用魔方来阐明群论中的关键概念。这样的结合使得理论学习变得更加生动和实践化。群论的核心在于它的基本概念——群，它是一个集合和一个运算的组合，满足特定的规则，如封闭性、结合律、存在单位元以及存在逆元。在魔方的例子中，这些群元素可以代表魔方的转动操作，而群的运算则对应于这些操作的组合。通过魔方，我们可以理解到以下群论概念： 1. **群的结构**：魔方的每个面可以看作一个子群，每次旋转一个面就是执行一次群操作。 2. **循环群**：魔方的某些旋转操作可以形成循环，例如单个面的连续旋转。 3. **置换群**：魔方的所有可能状态形成一个大的置换群，每个状态对应着一种特定的面排列。 4. **子群**：特定的魔方解法（如只转顶部两层）形成子群。 5. **群的同态和同构**：不同魔方解法之间的关系可以通过群同态和同构来研究。 6. **群的阶**：魔方群的阶等于所有可能状态的数量，这是一个非常大的数。 7. **正规子群和商群**：通过固定一面或一组面，可以构造出魔方的正规子群，进一步可以形成商群，这在解决魔方的不同策略中体现出来。魔方的解决方案往往涉及到群论的深度应用，例如通过寻找群的生成元（基础转动），以及计算最小生成集来找到最短的解立方体序列。这种方法称为“群论解法”，它使得复杂的魔方问题能够被简化并系统地解决。通过这种交互式的教学方法，不仅使群论变得更具吸引力，也帮助读者建立起理论与实践的桥梁，从而更好地理解和掌握这一抽象的数学概念。无论是对数学爱好者还是初次接触群论的人来说，"Group Theory via Rubik's Cube"都是一个极好的学习资源。

be described equally well by any of the following:



1234

1342





2134

3142





4321

2431





3412

4213



(1)

or in any of 20 other forms, as long as there’s always a 1 under the 1, a 3 under the 2, et cetera.

5 Permutation Cycle Notation

The notation introduced in the previous section certainly works to describe any permutation, but

there is a much better way that we will call “cycle notation”. If we are looking at a particular

permutation, we can begin at any box and see where the contents of that box are moved by the

permutation. If that ﬁrst ball doesn’t remain ﬁxed, it moves to a new box, so the ball in that new

box is moved to yet another box, and so on. Eventually, a ball has to move back to the original

box since there are only a ﬁnite number of boxes. This forms a cycle where each ball moves to

the next position in the cycle and the moves eventually “cycle around” to the original box.

These cycles can have any length from 1 up to N, the total number of boxes. In the previous

example shown in equation 1, item 1 forms a cycle of length 1 (since it doesn’t move, or if you

like, it moves to itself). The other three form a cycle: 2 moves to 3, 3 moves to 4 and 4 moves

back to 2. The cycle notation for that permutation is this:

(1)(2 3 4).

To interpret cycle notation, the set of items between each pair of parentheses form a cycle,

with each moving to the box of the one that follows it. Finally, the last one in the list moves back

to the box represented by the ﬁrst one in the list. These cycles will be disjoint in the sense that

each item will appear in only one of them. If an item appeared in two different cycles, then it

would appear to follow two different paths.

Notice also that the cycle notation is not unique although it can be made to be. All the

permutations in the list below are equivalent:

(1)(2 3 4) (1)(3 4 2) (1)(4 2 3) (2 3 4)(1) (3 4 2)(1) (4 2 3)(1)

Since they are independent, we can list the cycles in any order, and since we can begin with

any element in the cycle and follow it around, a cycle of n objects can appear in any of n forms.

5.1 Canonical Cycle Notation

This makes it a bit difﬁcult to determine at a glance whether two descriptions of a permutation

in cycle notation are equivalent, but if there is some sort of “natural” ordering to the objects then

it is possible to form a canonical cycle notation:

1. Find the smallest item in the list and begin a cycle with it.

2. Complete this ﬁrst cycle by following the movement of the objects by the permutation and

close the cycle.

3. If you have ﬁnished listing all of the objects in the permutation, you are done; otherwise,

return to step 1.

The canonical form of the cycle above is (1)(2 3 4).

Let’s now look at a few more complex permutations and see what their cycle notations look

like.

The permutation (1 3)(2 4)(5) exchanges the contents of boxes 1 and 3 and also exchanges

the contents of boxes 2 and 4 and leaves the contents of box 5 unchanged.

The permutation (1 2 3 4 5)(9 8 7) cycles 1 to 2, 2 to 3, 3 to 4, 4 to 5 and 5 back to 1. In

addition, it cycles 9 to 8, 8 to 7 and 7 back to 9.

Often, if the set of objects being permuted is obvious, the objects that do not move are not

listed. Thus (1)(2 3 4) might be listed simply as (2 3 4). With this convention, however, there’s

no reasonable way to list the identity permutation that moves nothing, so it is often listed as (1),

where only one example of a non-moving object is listed, or even as 1 to indicate that it is an

identity transformation.

If you were listing the primitive cube operations in this cycle notation, the convention of

leaving out 1-cycles would be a big advantage. Of the 54 facelets on a cube, a single face twist

only moves 21 of them, which obviates listing 33 of the 1-cycles.

5.2 The Cycle Structure of a Permutation

A very important feature of a permutation is captured when it is listed in cycle notation, and that

is its cycle structure. For example, the cycle structure of

(1)(2)(3 4 5)(6 7 8)(9 10 11 12)

has two 1-cycles, two 3-cycles, and one 4-cycle. To see why this is important, let’s begin with a

few simple examples.

Consider (1 2 3). If this operation is applied three times, it is obvious that the result is the

identity permutation. Each time it is applied, each element advances to the next box in the cycle,

but the cycle is three boxes long, so after three steps, each object will return to where it started.

In fact, if P is a permutation whose structure consists of a single n cycle: (i

· · · i

) then

= 1.

Also obvious, but worth stating, is that if you apply a permutation that consists of a single

cycle of length n repeatedly, it will return to the identity after every n applications. If P consists

of a single 5-cycle, then P

= P

= · · · = 1.

Next, let’s consider the permutation P = (1 2 3)(4 5 6 7) that consists of both a 3-cycle and

a 4-cycle. Since the two cycles have no elements in common, if we apply P repeatedly and don’t

pay any attention to the elements in the 4-cycle, we see the elements in the 3-cycle returning to

their initial locations every three applications. Similarly, if we ignore the elements in the 3-cycle

and pay attention only to those in the 4-cycle, then every 4 applications of P returns those four

elements to their starting places.

In other words, the elements in the 3-cycle return to their original locations for P

, P

, and so on. Similarly, the elements in the 4-cycle return to their original locations for

, P

, and so on.

Notice that P

appears in both lists, and that this is the ﬁrst exponent of P that is in both

lists. This means that after 12 applications of P , the elements in both the 3-cycle and in the 4-

cycle are returned to their starting locations, and furthermore, this is the ﬁrst time that it happens.

Thus P

= 1, and since it’s the ﬁrst time this happens, the order of P is 12.

The number 12 is the least common multiple of 3 and 4, usually written as

LCM(3, 4) = 12.

In other words, 12 is the smallest number larger than 0 that is a multiple of both 3 and 4. It should

be obvious from the discussion above that if a permutation consists of two cycles of lengths m

and n, then then order of that permutation is simply LCM(m, n).

The concept of a least common multiple can be extended easily to any number of inputs. We

have: LCM(4, 5, 8, 7) = 280—280 is the smallest number that is a multiple of 4, 5, 8 and 7. If

a permutation consists of a 4-cycle, a 5-cycle, an 8-cycle and a 7-cycle, then the order of that

permutation would be 280.

5.3 Applications of Cycle Structure to the Cube

Let’s consider a permutation that looks like this: P = (1 2)(3 4 5 6 7) that consists of a 2-cycle

and a 5-cycle, so its order is LCM(2, 5) = 10. What happens if we repeat P ﬁve times? In other

words, what does P

look like? The 5-cycle will disappear, since after 5 applications, every

element in it has cycled back to its starting point. The 2-cycle will have been applied an odd

number of times, so it will remain a 2-cycle. Thus P

= (1 2).

Thus, although the permutation P by itself moves 7 objects, the permutation P

moves only

two objects. If the objects 1, 2, ..., 7 in this example were really cubies in Rubik’s cube, then if

the operation P were repeated 5 times, the net result would be an operation that moved exactly

2 cubies and left all the others where they were.

Toward the end of Section 3.1 we saw an example of this: The operation FFRR moves 13

cubies, but (FFRR)

moves only 4—it exchanges two pairs of edge cubies.

Using the names for the individual cubies described in the documentation for the Rubik

program, here is what the permutation FFRR does:

(DF UF)(DR UR)(BR FR FL)(DBR UFR DFL)(ULF URB DRF)

where we use “DF” to indicate the “down-front” edge cubie, “DBR” to represent the “down-

back-right” cubie, et cetera. Obviously, since there are 13 cubies in the permutation cycle listing,

13 of the cubies are moved by FFRR. But nine of those 13 appear in 3-cycles, so the permutation

剩余58页未读，继续阅读

buck

粉丝: 181
资源: 23

魔方与群论：借助Rubik's Cube理解Group Theory

3D魔方Rubik's Cube 又叫魔术方块

(魔方资料)Group Theory and the Rubik's Cube.pdf

Adventures in Group Theory

A Course in Group Theory

java-codes.rar_CUBEBean.java_RUBIK S CUBE_create a cube java_解魔方

Rubik-Cube-Wizard:增强现实Android Rubik Cube向导

Rubik's cube

Rubik_Cube1-Arduino:ESP32 Rubik Cube-1 Arduino库

rubik_cube_timer

rubik-cube-solver

最新资源