CWYAlpha

Just another WordPress.com site

Thought this was cool: 几个精彩的数论问题

leave a comment »


从同事那里借来了一本单墫教授主编的《初等数论》奥数书,看到很多精彩的问题,在这里做个笔记,与大家一同分享。不少问题和答案都有过重新叙述,个别问题有所改动。

 
问题:找出所有使得 2n – 1 能被 7 整除的正整数 n 。

答案:由于 2n 的二进制表达为 1000…00 (n 个 0),因此 2n – 1 的二进制表达为 111…11 (n 个 1)。而 7 的二进制表达是 111 ,要想让它整除 n 个 1 ,显然 n 必须是也只能是 3 的倍数。


问题:是否存在 100 个数,使得它们的和等于它们的最小公倍数?

答案:是的。考虑 3, 2 × 3, 2 × 32 , 2 × 33, …, 2 × 398, 399 ,它们的和为:

     3 + 2 × 3 + 2 × 32 + 2 × 33 + … + 2 × 398 + 399
  = 3 × (1 + 2) + 2 × 32 + 2 × 33 + … + 2 × 398 + 399
  = 32 + 2 × 32 + 2 × 33 + … + 2 × 398 + 399
  = 32 × (1 + 2) + 2 × 33 + … + 2 × 398 + 399
  = 33 + 2 × 33 + … + 2 × 398 + 399
  = … …
  = 399 + 399
  = 2 × 399

而这 100 个数的最小公倍数正是 2 × 399

 
问题:能否找出 100 个不同的正整数,使得其中任意 2 ≤ k ≤ 100 个数的算术平均数都恰为整数。

答案:能。这个问题非常唬人,它的答案异常简单: 1 · 100!, 2 · 100!, 3 · 100!, …, 100 · 100! 显然满足要求。

 
问题:求证,存在任意长的连续正整数,使得其中任何一个数都不是质数的幂(当然更不能是质数)。

答案。有一个经典的问题是,求证存在任意长的连续正整数,它里面不包含任何质数。换句话说,相邻质数的间隔可以达到任意大。构造的方法堪称经典。显然 n! + 2 是 2 的倍数(因为我们可以提出一个 2 来), n! + 3 是 3 的倍数,等等。因此, n! + 2, n! + 3, n! + 4, …, n! + n 就是 n – 1 个连续的正整数,其中任意一个数都不是质数。由于 n 可以任意大,因此这个数列可以任意长。

现在,我们要证明的是一个更强的结论。我们可以把刚才的构造方案简单地修改一下。只需要考虑 (n!)2 + 2, (n!)2 + 3, (n!)2 + 4, …, (n!)2 + n ,则其中每一个数都不是质数的幂。比如说 (n!)2 + 5 ,显然它是 5 的倍数,因为我们可以提出一个 5 来;然而提出一个 5 之后将会得到 5 · (12 · 22 · 32 · 42 · 5 · 62 · … · n2 + 1) ,括号里的数显然不再是 5 的倍数,它除以 5 余 1 。

利用中国剩余定理,我们还能给出另一种非常巧妙的构造方案,它能找出 n 个不含质数幂的连续正整数数列,其中 n 可以任意大。我们只需要保证,每个数都含有至少两个不同的质因数即可。取 2n 个不同的质数 p1, p2, …, pn, q1, q2, …, qn ,显然 p1 · q1, p2 · q2, …, pn · qn 是两两互质的 n 个数。由中国剩余定理,我们能找到一个正整数 M ,使得 M 除以 p1 · q1 余 1 ,并且 M 除以 p2 · q2 余 2 ,并且 M 除以 p3 · q3 余 3 ,一直到 M 除以 pn · qn 余 n 。于是, M – 1, M – 2, M – 3, …, M – n 就是 n 个连续的正整数,其中每一个都含有两个不同的质因数。

 
问题:求证,对于任意大的 n ,我们都能够找出 n 个两两互质的数,使得任意 2 ≤ k ≤ n 个数之和都不是质数

答案:如果只要求任意多个数之和都不是质数,这很好办:让所有数都是某个数的倍数即可。但是,如果这些数必须两两互质,同样的要求还能办到吗?可以的。考虑 n! + 1, 2 · (n!) + 1, 3 · (n!) + 1, …, n · (n!) + 1 这 n 个数,显然任意 k 个数之和都是 k 的倍数,因而不是质数。下面说明这 n 个数两两互质。假设 i · (n!) + 1 和 j · (n!) + 1 有公共的质因数 p ,其中 1 ≤ i < j ≤ n ,那么它们的差 (j – i) · (n!) 也能被 p 整除,说明 p 只能是不超过 n 的质数。这与 p 能整除 i · (n!) + 1 矛盾。

 
问题:证明,对于任意正整数 n ,方程 x2 + y2 = zn 都有无穷多组正整数解。

答案:考虑 x + yi = (a + bi)n ,其中 i 为虚数单位。对于每一个固定的 n ,只要 a 和 b 都是整数,那么展开后得到的 x 和 y 也都一定是整数。我们选取充分大的 a ,让 a + bi 的辐角非常小非常小(小于 π/2 的 n 分之一),从而让 (a + bi)n 不会与坐标轴重合,因而保证 x 和 y 都是非零整数。等式两边同时取模,便有 x2 + y2 = (a2 + b2)n

 
问题:我们把平面直角坐标系上所有横纵坐标互质的整格点(也就是和原点的连线不经过其他点的整格点)叫做“既约格点”。证明,对于任意大的正整数 n ,总存在一个整格点,它到任意既约格点的距离都大于 n (换句话说,既约格点集的“空洞”可以达到任意大)。

答案:列一张 (2n + 1) × (2n + 1) 的表,每个格子里面填写一个不同的质数(由于质数无穷多,这是总可以办到的)。现在,找出这样的一个 a ,它除以第 i 行的质数总是余 i (其中 – n ≤ i ≤ n )。找出这样的一个 b ,它除以第 j 列的质数总是余 j (其中 -n ≤ j ≤ n)。中国剩余定理保证了这样的 a 和 b 是存在的。下面说明,点 (a, b) 满足要求。

  

假如 (a, b) 到 (x, y) 的距离不超过 n ,则 (a – x)2 + (b – y)2 ≤ n2 。因而, a – x 和 b – y 都必须在 – n 到 n 的范围内。把 a – x 的值记作 i ,把 b – y 的值记作 j ,那么 x 就等于 a – i , y 就等于 b – j ,由 a 、 b 的构造可知, x 和 y 都是表格中第 i 行第 j 列的那个质数的倍数,故 (x, y) 不是既约格点。

 
问题:找出所有这样的正整数序列 (a1, a2, …, an) ,它们的和为 2n ,但我们无法把它们分成和相等的两组。

答案:考虑 a1, a2, a1 + a2, a1 + a2 + a3, …, a1 + a2 + a3 + … + an ,除了 a1 和 a2 以外,这些数除以 n 的余数不允许相等,否则它们的差就是 n 的倍数,我们就找到了和为 n 的子集。然而,上面一共有 n + 1 个数,它们除以 n 的余数必然有相等的,因而一定是 a1 和 a2 除以 n 的余数相等。类似地, a2 和 a3 除以 n 的余数也相等, a3 和 a4 除以 n 的余数也相等,因而事实上从 a1 到 an 所有的数除以 n 的余数都是相等的。

但是这 n 个数加起来只有 2n ,可见所有的数除以 n 的余数只可能都是 1 或者都是 2 。于是我们得到了所有满足要求的数列: (1, 1, 1, …, 1, n + 1) ,以及 (2, 2, 2, …, 2) 。其中后者要求 n 为奇数。

 
问题:证明,存在无穷多个正整数三元组 (a, b, c) ,使得 a2 + b2 、 b2 + c2 、 a2 + c2 都是完全平方数。

答案:任取一组勾股数 (x, y, z) ,令 a = x|4y2 – z2| , b = y|4x2 – z2|, c = 4xyz 。于是,

  a2 + b2 = x2(3y2 – x2)2 + y2(3x2 – y2)2
             = x6 + 3x2y4 + 3x4y2 + y6
             =(x2 + y2)3 = (z3)2
  a2 + c2 = x2(4y2 + z2)2
  b2 + c2 = y2(4x2 + z2)2

从而 a 、 b 、 c 满足要求。由于勾股数有无穷多组,因此满足要求的 (a, b, c) 也有无穷多组。

这相当于给出了 Euler 砖块(所有棱长和所有面对角线都是整数的长方体)的一种构造解。当 (x, y, z) = (3, 4, 5) 时,我们将得到棱长分别为 117 、 44 、 240 的 Euler 砖块,这就是最小的 Euler 砖块,它是由 Paul Halcke 在 1719 年发现的。

大家或许会想,有没有什么长方体,不但所有棱长和所有面对角线都是整数,连体对角线也是整数呢?这样的长方体就叫做完美长方体。有趣的是,虽然 Euler 砖块有无穷多种,但是人们目前还没有找到哪怕一个完美长方体。完美长方体究竟是否存在,目前仍然是一个未解之谜。

 
问题:证明,若正整数 a 和 b 互质,则 [b / a] + [2b / a] + [3b / a] + … + [(a – 1) b / a] = (a – 1)(b – 1) / 2 。其中, [n] 是 n 的整数部分,即对 n 取下整。

答案:我们先举一个例子来说明这个问题的复杂性。数列 [b / a], [2b / a], [3b / a], …, [(a – 1) b / a] 的规律并不一定非常明确。例如,当 a = 17 且 b = 12 时, [12 / 17], [2 · 12 / 17], [3 · 12 / 17], … [16 · 12 / 17] 分别为 0, 1, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 9, 10, 11 ,但这 16 个数之和为 88 ,正好是 16 和 11 乘积的一半。

  

结论的证明很有意思。在平面直角坐标系的第一象限摆放一个宽为 a ,高为 b 的矩形。则 [k · b / a] 就是图中第 k 条红色竖直线上的整格点数目,所有 [k · b / a] 之和也就是阴影三角形内的整格点总数。然而由于 a 和 b 互质,矩形的对角线不会经过矩形内部的任何格点,因此阴影三角形内的整格点数就应该是矩形内的整格点数的一半,即 (a – 1)(b – 1) / 2。

 
问题:若正无理数 α 和 β 满足 1 / α + 1 / β = 1 ,求证数列 [1 · α], [2 · α], [3 · α], … 和 [1 · β], [2 · β], [3 · β], … 既无重复又无遗漏地包含了所有的正整数。这里 [ ] 同样是取下整的意思。

答案:让我们先来看一个例子吧。考虑黄金比例 φ = (√5 + 1) / 2 ≈ 1.618 ,我们有 1 / φ + 1 / (φ + 1) = 1 。数列 [1 · φ], [2 · φ], [3 · φ], … 为 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, … ,而数列 [1 · (φ + 1)], [2 · (φ + 1)], [3 · (φ + 1)], … 则为 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, … 。你会发现,前一个数列里没有的数,正好都在后一个数列里,而后一个数列里没有的数,前一个数列里正好都有。两个数列合在一起,就是整个正整数序列。

这个定理叫做 Beatty-Rayleigh 定理,它有很多种证明,其中两种证明参见 Wikipedia 。这里给出一种我非常喜欢的证明,它出自 Using your Head is Permitted

首先注意到,如果 x 和 y 都不是整数,那么 [x] 严格地小于 x ,[y] 严格地小于 y ,从而 [x] + [y] < x + y 。另外,[x] 一定严格地大于 x – 1 , [y] 一定严格地大于 y – 1 ,从而 [x] + [y] 一定严格地大于 x + y – 2。这说明,当 x 和 y 都不是整数时, [x] + [y] 将介于 x + y – 2 和 x + y 之间。

回到原问题。显然,在第一个数列中,小于 n 的正整数有 [n / α] 个。显然,在第二个数列中,小于 n 的正整数有 [n / β] 个。因此,在这两个数列中,小于 n 的正整数共有 [n / α] + [n / β] 个。由于 α 和 β 都是无理数,因此 n / α 和 n / β 不可能为整数,由刚才的结论, [n / α] + [n / β] 一定介于 n / α + n / β – 2 和 n / α + n / β 之间,即 n – 2 和 n 之间。但是, [n / α] + [n / β] 是个整数,因而它精确地等于 n – 1 。

这说明,前 n – 1 个正整数在两个数列中一共出现了 n – 1 次,这对于所有 n 都成立。于是,正整数 1 必须且只能出现在其中一个数列中,正整数 2 必须且只能出现在其中一个数列中,以此类推,每一个新的正整数都必须且只能出现在其中一个数列中。

这种取整函数的处理技巧也可以用到上一个问题里:对上一个问题里的数头尾配对,你会发现每一对数之和都是 b – 1 。

 
问题:把 10, 100, 1000, 10000, … 分别写成二进制数和五进制数:

  原数列:10, 100, 1000, 10000, 10000, …
  二进制:1010, 1100100, 1111101000, 10011100010000, …
  五进制:20, 400, 13000, 310000, 11200000, …

你会发现,对于任意正整数 n > 1 ,后两个数列里恰好有一个数是 n 位数。这是为什么?

答案:这是 Beatty-Rayleigh 定理的一个非常漂亮的直接推论。 10k 的二进制表达恰好有 [log210k] + 1 位,即 [k · log210] + 1 位。10k 的五进制表达恰好有 [log510k] + 1 位,即 [k · log510] + 1 位。我们只需要证明,数列 [1 · log210], [2 · log210], [3 · log210], … 和 [1 · log510], [2 · log510], [3 · log510], … 既无重复又无遗漏地包含了所有正整数。注意到 log210 和 log510 是两个倒数和为 1 的无理数,用一下 Beatty-Rayleigh 定理就出来了。

 
如果你喜欢这些问题,这里还有另一个类似的小合集:http://www.matrix67.com/blog/archives/3172


from Matrix67: My Blog: http://www.matrix67.com/blog/archives/5013

Written by cwyalpha

六月 14, 2012 在 5:10 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: