由魔方问题引出的思考

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

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

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

由来

在上一篇博文中，我提及：“和同学讨论有关魔方还原的问题”，同学（ZLR）的原话大概是这样的：

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

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

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

新问题

我有一串数列 A，标号 1 ~ 10：

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

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

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

例如，我规定顺序 B 为：

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

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

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

<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 个位置的数放到第 8 个位置；
然后将第 2 个位置的数放到第 10 个位置；
然后将第 3 个位置的数放到第 5 个位置；
然后将第 4 个位置的数放到第 3 个位置；
然后将第 5 个位置的数放到第 7 个位置；
然后将第 6 个位置的数放到第 9 个位置；
然后将第 7 个位置的数放到第 6 个位置；
然后将第 8 个位置的数放到第 1 个位置；
然后将第 9 个位置的数放到第 2 个位置；
最后将第 10 个位置的数放到第 4 个位置.

它又可以表示为：

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
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：

#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 操作：

统计变化的块：

输出如下：