0%

由魔方问题引出的思考

证明以下内容后经群友提醒才确定这属于群论,那本文就当作是循环群的通俗解释吧.

对任意封闭体系内的元素进行互换位置的操作,
一定能在有限次操作后恢复到操作前的状态,
且这有限次操作的次数是可以计算的.

下面尝试给出其证明,若有误欢迎指出.


由来

上一篇博文中,我提及:“和同学讨论有关魔方还原的问题”,同学(ZLR)的原话大概是这样的:

既然一直重复 “上左” 操作需要一百多次就能复原,“上右” 需要六十多次也能复原. 那对魔方一直重复同一个操作,是否也一定能复原呢?

之后,同学给出了他的证明方案(文末介绍),我个人认为他是对的,并将次方案推广到其他情况.

下面换另一个角度介绍我的方法.


新问题

我有一串数列 A,标号 1 ~ 10:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

我规定一次操作为:将该数列的元素按照一定的顺序 B 互换位置.

那么问至少经过多少次操作能使数列恢复原样(复原).

例如,我规定顺序 B 为:

  1. 先将第 1 个位置的数放到第 8 个位置;
  2. 然后将第 2 个位置的数放到第 10 个位置;
  3. 然后将第 3 个位置的数放到第 5 个位置;
  4. 然后将第 4 个位置的数放到第 3 个位置;
  5. 然后将第 5 个位置的数放到第 7 个位置;
  6. 然后将第 6 个位置的数放到第 9 个位置;
  7. 然后将第 7 个位置的数放到第 6 个位置;
  8. 然后将第 8 个位置的数放到第 1 个位置;
  9. 然后将第 9 个位置的数放到第 2 个位置;
  10. 最后将第 10 个位置的数放到第 4 个位置.

为了方便,我们用序列 8, 10, 5, 3, 7, 9, 6, 1, 2, 4 来表示一次操作.

一直按照该操作进行,我们得到以下数列:

1
2
3
4
5
6
7
8
<1 次操作> 8 9 4 10 3 7 5 1 6 2
<2 次操作> 1 6 10 2 4 5 3 8 7 9
<3 次操作> 8 7 2 9 10 3 4 1 5 6
<4 次操作> 1 5 9 6 2 4 10 8 3 7
<5 次操作> 8 3 6 7 9 10 2 1 4 5
<6 次操作> 1 4 7 5 6 2 9 8 10 3
<7 次操作> 8 10 5 3 7 9 6 1 2 4
<8 次操作> 1 2 3 4 5 6 7 8 9 10

可见,数列 A 在 8 次 B 操作后复原.


解释

仍按照先前的例子,B = 8, 10, 5, 3, 7, 9, 6, 1, 2, 4,共需 8 次复原.

前面我们提到,顺序 B 为:

  1. 先将第 1 个位置的数放到第 8 个位置;
  2. 然后将第 2 个位置的数放到第 10 个位置;
  3. 然后将第 3 个位置的数放到第 5 个位置;
  4. 然后将第 4 个位置的数放到第 3 个位置;
  5. 然后将第 5 个位置的数放到第 7 个位置;
  6. 然后将第 6 个位置的数放到第 9 个位置;
  7. 然后将第 7 个位置的数放到第 6 个位置;
  8. 然后将第 8 个位置的数放到第 1 个位置;
  9. 然后将第 9 个位置的数放到第 2 个位置;
  10. 最后将第 10 个位置的数放到第 4 个位置.

它又可以表示为:

1
2
3
4
5
6
7
8
9
10
1 -> 8
2 -> 10
3 -> 5
4 -> 3
5 -> 7
6 -> 9
7 -> 6
8 -> 1
9 -> 2
10 -> 4

如果把这些数据点连成一个图,效果如下:

显然,这些数据一定会连成一个或多个环,因为这是互换位置的操作,每个数据节点一定有且只有一个输入和一个输出.

这样便涉及到了我熟悉的图论领域了. 也就是说,最终绘制出的图形一定是多个有向环的集合,每进行一次操作,每个环上的点就会按照箭头所指的方向 “前进” 一格.

对于每一个环,“前进” 一圈就能回到原位,如果要让所有的环回到原位(复原),只需操作每个环长度的最小公倍数次就好了.

因此,在这个例子中,只需要操作 2 和 8 的最小公倍数 8 次就能复原.


扩展

因此,我们可以给出这种问题的通解:列出变换的点;画出对应的图;数每个环的长度,求最小公倍数即为结果.

我们拿一个稍微复杂点的例子:

B = 2, 6, 5, 7, 3, 1, 8, 10, 4, 9

该数据共需要 30 次操作才能复原.

它的变化情况是这样的:

1
2
3
4
5
6
7
8
9
10
1 -> 2
2 -> 6
3 -> 5
4 -> 7
5 -> 3
6 -> 1
7 -> 8
8 -> 10
9 -> 4
10 -> 9

绘制出有向图:

其中存在三个环,长度分别为:2, 5, 3,最小公倍数恰恰为 30.

为了方便测试,我写了一个简单的 C++ 程序来随机生成 B 并操作数列 A:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
using namespace std;

#define MAXN 10000

int n = 10;
int A[MAXN];
int B[MAXN];

bool check();
void apply();

int main()
{
for (int i = 1; i <= n; i++)
A[i] = B[i] = i;
srand(time(0));
random_shuffle(B + 1, B + n + 1);

cout << "B = ";
for (int i = 1; i <= n; i++)
cout << B[i] << " ";
cout << endl << endl;

for (int i = 1; i <= n; i++)
cout << i << " " << B[i] << endl;
cout << endl << endl;

for (int test = 1;; test++)
{
apply();
cout << "<" << test << "> ";
for (int i = 1; i <= n; i++)
cout << A[i] << " ";
cout << endl;
if (check())
getchar();
}
return 0;
}

void apply()
{
int tA[MAXN] = {0};
for (int i = 1; i <= n; i++)
tA[B[i]] = A[i];
for (int i = 1; i <= n; i++)
A[i] = tA[i];
}

bool check()
{
for (int i = 1; i <= n; i++)
if (A[i] != i)
return false;
return true;
}

魔方

前面提出的模型是可以广泛应用的,其中一个例子便是之前提出的魔方问题.

下面使用我自己开发的魔方模拟器进行研究,它的介绍地址:

用于学术研究的魔方模拟器 https://blog.xecades.xyz/articles/CubeSimulator/

以操作 “左上” 为例,也就是指令 RU.

我们把魔方的每一个格子依次编号为 1 ~ 54:

进行一次 RU 操作:

统计变化的块:

输出如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
3 1
6 2
27 3
2 4
26 6
1 7
4 8
25 9
19 10
22 13
43 16
30 19
29 22
28 25
44 26
45 27
9 28
33 29
36 30
51 31
35 33
48 34
31 35
34 36
52 43
53 44
54 45
16 48
13 51
7 52
8 53
10 54

输入到图论绘图工具 csacademy 中,稍作整理,我们得到图:

在这个例子中,出现了四个环,其长度分别为:

3, 7, 7, 15

其最小公倍数为 105,表示一直进行操作 “上左” 至少需要 105 次才能复原.

我们可以通过 Cube Simulator 验证:

可见次结论是对的.

另外,计算一个图中环的个数,信息学领域可以很轻松地用 bfs 算法(广度优先搜索)实现,这里我就不给出代码了.


若有逻辑上的漏洞,欢迎在评论区指出.

另:强烈推荐图论绘图工具 csacademy(我真的不是打广告…)