小偷也要会数学：暴力破解的偷懒方法 | 科学人 | 果壳网 科技有意思
很多保险箱的密码都是四位数，这足以给人带来安全感——由于从 0000 到 9999 共有 10000 种情况，要想试遍所有的密码，按 40000 次数字键似乎是必需的。但是，很多保险箱的数字键盘上并没有输入键。只要连续输入的四个数字恰好和预先设定的密码相同，保险箱都会打开。比如说，当你尝试输入 1234 和 1235 两个密码时，2341、3412、4123 也被试过了。聪明的小偷可以利用这一特性，设计出一种数字输入顺序，大大减少最坏情况下需要的总按键次数。你认为，试遍所有的密码最少需要按多少个键呢？
如果一个数字序列包含了 10000 个不同的四位数，这个数字序列至少得有 10003 位长。令人吃惊的是，真的就存在这么一个 10003 位的数字序列，它既无重复又无遗漏地包含了所有可能的四位数。更神的是，满足要求的数字序列不止一种，而寻找数字序列的任务竟完全等价于一笔画问题！
为了把事情解释清楚，不妨让我们先来看一个更为简单的问题：假如密码是一个只由数字 0 和 1 构成的三位数（这有 8 种可能的情况），如何构造一个 10 位数字串，使它正好包含所有可能的三位数？现在，让我们在图上画四个点，分别标记为 00、01、10、11，它们表示数字串中相邻两个数字可能形成的 4 种情况。如果某个点上的数的后面一位，恰好等于另一个点上的数的第一位，就从前面那个点出发，画一个到后面那个点的箭头，表示从前面那个点可以走到后面这个点。举例来说，00 的后一位数正好是 01 的前一位数，则我们画一个从 00 到 01 的箭头，意即从 00 可以走到 01。注意，有些点之间是可以相互到达的（比如 10 和 01），有些点甚至有一条到达自己的路（比如 00）。
图上有 00、01、10、11 四个点，如果两个点满足 xy 和 yz 的关系（x、y、z 有可能代表相同的数字），就画一条从 xy 到 yz 的路，这条路就记作 xyz
试密码的过程，其实就相当于沿着箭头在上图中游走的过程。不妨假设你最开始输入了 00。如果下一次你输入了 1，那么你就试过了 001 这个密码，同时你最近输过的两位数就变成了 01；如果你下一次还是输入的 0，那么你就试过了 000 这个密码，你最近输过的两个数仍然是 00。从图上看，这无非是一个从 00 点出发走了哪条路的问题：你是选择了沿 001 这条路走到了 01 这个点，还是沿着 000 这条路走回了 00 这个点。同理，你每按下一个数字，就相当于沿着某条路走到了一个新的点，路上所写的三位数就是你刚才试过的密码。我们的问题就可以简单地概括为，如何既无重复又无遗漏地走完上图中的所有路。也就是说，我们要解决的仅仅是一个一笔画问题！
稍试几下，我们便可以找出一条一笔画路径。其中一条路就是：
00 → 00 → 01 → 10 → 01 → 11 → 11 → 10 → 00
它给出了一个满足要求的 10 位数字序列：
0001011100
这个 10 位数字串就真的包含了全部 8 个由 0 和 1 构成的三位数！事实上，利用一些图论知识，我们可以直接看出这个图一定能一笔画走完的。在图论中，从一个顶点延伸出去的箭头数叫做这个点的"出度"，而指向这个顶点的箭头数则叫做这个顶点的"入度"。图论中有一个重要的定理：对于一个连通的图，如果每个点的出度都等于入度，那么一定能够找到一种经过每条路恰好一次的走法。很显然，在上图中，从任意一点出发，都有两条路可以走；同时，走到这个点也总有两种不同的途径。这就告诉我们，遍历所有路恰好一次的方法是一定存在的。
同样地，对于 0 到 9 组成的全部四位数来说，我们可以设置 1000 个顶点，分别记作 000, 001, …, 999。如果某个数的后两位等于另一个数的前两位，就从前者出发，画一个箭头指向后者。容易想到，每个顶点的入度和出度都是 10，因此存在一条一笔画路径。也就是说，只需要按 10003 次数字键，便能试遍所有可能的四位数密码了。
虽然我们利用数学证明了符合要求的数字序列一定存在，但这个 10003 位数究竟是多少呢？这时，就轮到计算机登场了。利用计算机程序，我们可以很快给出一个答案；限于篇幅，我们就不在这里展示了，欢迎大家到 死理性派小组 里围观。
本文版权属于果壳网（guokr.com），转载请注明出处。商业使用请联系果壳
Read full article from 小偷也要会数学：暴力破解的偷懒方法 | 科学人 | 果壳网 科技有意思
No comments:
Post a Comment