求证:给定任意一个魔方操作序列,在经过有限次重复操作该序列后,魔方的状态和初始状态相同。
证:f(x) = y ,表示经过 f 操作序列后,魔方状态由 x 变为 y 。假设魔方初始状态为 a ,那么多次操作后,状态的序列为 abcd…。因为魔方的状态总数是有限的,所以这个序列一定会出现重复,可以理解为单链表里存在环。又因为存在 f 的反向操作 g ,使得 g(y) = x ,不可能存在两个不同的魔方状态在经过同一个魔方变换序列后得到同样的新状态,所以单链表的环不可能在中间形成(那样的话两个不同的节点的 next 指向了同一个节点),只能在单链表的头部形成,所以魔方一定会回到初始状态 a 。
这个证明里有几个前置条件:
1. f(x)=y 中 x 和 y 同属于一个有限的集合。
2. f 是可逆的。
hash 和加密都不满足 f 可逆的条件。即使 hash 和加密的状态集合是有限的(包括原始输入),也只能证明环是存在的,并不能证明单链表的头在环里。