在ahapuzzles.com逛了一天，看到了不少好玩的东西。

问号处应该填哪一个图形？
答案：E。各方块的对角线组成了数字3、4、5、6、7的字样。

问号处应该填什么数字？
答案：5。圆圈和点表示太阳和9大行星，旁边的数字表示每颗星球的名字的字母个数。

查看更多 »

如果一个矩形可以分割为若干个小矩形，每个小矩形都有至少一边为整数长，则原矩形同样有至少一个长度为整数的边。换句话说，用至少有一边的长度是整数的小矩形拼成一个大矩形，大矩形也有至少一条整数长的边。

    不假，利用数论知识我们真的可以证明这个和数论八杆子打不着的题目。证明的关键就在于，质数有无穷多个。给定一个满足要求的大矩形，如果你宣称它的每条边都不是整数，它们都至少多出了大小为ε的“零头”。那么，我就找出一个足够大的质数p，使得1/p < ε，然后说明有一条边的长度除去整数部分后的“零头”不会超过1/p。这样的话，至少有一边恰好是整数长才行。
    仍然是把大矩形放在平面直角坐标系上，左下角对齐原点(0,0)。考虑所有形如(i/p, j/p)的点所形成的点阵（其中i, j均为整数）。我们需要把整个点阵平移到一个合适位置，使得点阵中没有点恰好落在小矩形的边界上。这总是可以办到的，例如我们算出每个小矩形的横边到点阵中离它最近的点的距离，取所有这些最近距离中最小的非0的值，然后竖直方向上移动一个比这还小的距离；另一个方向亦是如此。注意到每个小矩形内部所含的点数都是两个数的乘积，由于其中至少有一个数是p的倍数，因此每个小矩形内都有p的倍数个点。那么，整个大矩形所含的点的个数（即每个小矩形所含点数之和）也是p的倍数。大矩形内的所有点的个数也是两个数的乘积，然而p是质数，因此两个数中至少一个是p的倍数（数论的一个基本结论）。那么，对应的那条边就应该是整数长，并且最多有1/p的误差。

（三）（四）两种证明均来自http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/solutions/May1999.html

如果一个矩形可以分割为若干个小矩形，每个小矩形都有至少一边为整数长，则原矩形同样有至少一个长度为整数的边。换句话说，用至少有一边的长度是整数的小矩形拼成一个大矩形，大矩形也有至少一条整数长的边。

    在这个命题的所有常见的证明方法中，我总觉得这个证明是最诡异的。真不知道第一个想出这个证明方法的人是怎么思考出来的。把矩形放在平面直角坐标系上，左下角对齐原点(0,0)。考虑函数e^(2 · pi · i · (x+y))在每个小矩形上的积分（展开并分离变量分别积分）：
    

    显然，这个式子等于0当且仅当(x1-x0)和(y1-y0)中至少一个是整数（也即至少有一边的长度是整数）。考虑函数在整个大矩形上的积分，它可以拆成各个小矩形上的积分的和，因此结果仍然是0。这说明，大矩形至少有一条整数长的边。

  
    接下来，我们用图论方法来证明：一个由小矩形拼接而成的大矩形，若每个小矩形都有至少一条整数长的边，则大矩形也有至少一条整数长的边。考虑图中每个矩形的每个顶点，把它们作为图G的顶点集（相邻矩形重合的顶点并作一个点）；对于每一个小矩形，把它整数边方向的两对顶点分别用一条边连接起来（相邻矩形公共边上的重边不合并）。如果哪个小矩形四条边都是整数，无妨随意把它当作横向整数边的或者纵向整数边的，连接任一种方向上的边。这样的话，每个矩形恰好产生两条边。注意这个图的一些很显然的性质：度为1的点只有4个（大矩形的四个角），其余的顶点的度都是偶数（只能是2或者4）。下面，我们把这个矩形放在平面坐标系上，大矩形的左下角对齐原点(0,0)。从原点开始沿着图G的边走（每条边最多走一次，不走走过的边），显然走到的每个点都满足这个性质：它的两个坐标均为整数。但我们的出发点是一个度为1的点，在走到另一个度为1的点之前，我们遇到的所有顶点的度都是偶数。因此只要没走到另一个度为1的点，我们就不可能走死。但是，图G总的边数有限，总有一个时候我们将不能再走。因此，这次旅程的终点必然落在另一个度为1的点上。这个终点是大矩形的另一个角，它的两个坐标值均为整数。命题得证。

    以上两个证明均来自http://www.cs.toronto.edu/~mackay/rectangles/

查看更多 »

    今天才听说了这样一个有趣的命题：如果一个矩形可以分割为若干个小矩形，每个小矩形都有至少一边为整数长，则原矩形同样有至少一个长度为整数的边。换句话说，用至少有一边的长度是整数的小矩形拼成一个大矩形，大矩形也有至少一条整数长的边。这个命题看似简单但却很难证明，更准确地说应该是很难想到证明方法。而有趣就有趣在，这个命题的证明方法出奇的多，从图论方法到数论方法，每个证明都相当巧妙。

    我们所要介绍的第一个证明是我觉得最巧妙的证明方法。证明的关键在于下面这个引理：像国际象棋棋盘一样对整个平面黑白染色，那么与两坐标轴平行放置且至少一边长为偶数的矩形一定覆盖了相同面积的黑色区域和白色区域。原因很简单，看上图，该矩形中的每一个（长度为偶数个单位的）横条显然都覆盖了相同面积的黑白两色区域。

查看更多 »

    下面给出一种算法，该算法只需要使用加法运算和比较运算就可以求出n个数的最小公倍数：每一次操作都把当前最小的那个数加上它的初始值，直到所有数都相等为止。下面这个列表显示了用这个算法寻找30, 12, 18三个数的最小公倍数的全过程。初始时12是三个数中的最小数，于是该数加上12；接下来18成了最小的数，于是该数加上18变成了36；此时第二个数24又变成了最小数，于是再加上其对应的初始值12；以此类推直到三个数都变成相同的数180为止，这个180就是30, 12, 18的最小公倍数。

30 12 18
30 24 18
30 24 36
30 36 36
60 36 36
60 48 36
60 48 54
60 60 54
60 60 72
90 60 72
90 72 72
90 84 72
90 84 90
90 96 90
120 96 90
120 96 108
120 108 108
120 120 108
120 120 126
150 120 126
150 132 126
150 132 144
150 144 144
150 156 144
150 156 162
180 156 162
180 168 162
180 168 180
180 180 180

    这个算法为什么是正确的呢？它有什么实际用途呢？

查看更多 »

    下面这个问题出自The American Mathematical Monthly (Vol.75, No.3.(Mar.,1968), pp.299-301)：
    给定一个有限长的非负整数序列。一次操作是指把数列中的每个数替换为它右边比它小的数的个数。对该数列不断进行这个操作。证明总有一个时刻该数列将不再发生改变（即此时每个数都恰好等于它右边比它小的数的个数）。

    下面是一个实际的例子。这个数列在第四次操作之后进入循环，不再发生改变。
     5, 44, 19,  6, 49,  1, 27, 19, 50, 20
     1,  6,  2,  1,  4,  0,  2,  0,  1,  0
     3,  8,  5,  3,  5,  0,  3,  0,  1,  0
     4,  8,  6,  4,  5,  0,  3,  0,  1,  0
     5,  8,  7,  5,  5,  0,  3,  0,  1,  0
     5,  8,  7,  5,  5,  0,  3,  0,  1,  0
     ....................

查看更多 »

对于哪些n，存在一个1到n-1的排列S_1, S_2, ..., S_n-1，使得T_1, T_2, ..., T_n-1也是一个1到n-1的排列，其中，

T_1 = S_1 mod n,
T_2 = (S_1 + S_2) mod n,
T_3 = (S_1 + S_2 + S_3) mod n,
.......
T_n-1 = (S_1 + S_2 + ... + S_n-1) mod n.

查看更多 »