《具体数学:计算机科学基础(第2版)》第 2 章研究题 37:

第 2 章研究题 37

对于 k ≥ 1,所有 1/k 乘 1/(k+1) 的长方形能否填满一个 1 乘 1 的正方形?(记住它们的面积之和为 1 。)

1

计算长方形的面积之和

sum1

sum2

可见,所有 1/k 乘 1/(k+1) 的长方形的面积之和的确为 1 。

填充方案一

0200

上图就是研究题 37 中的图的彩色版本。1/k 乘 1/(k+1) 的长方形标记为 k,以后简称为长方形-k。注意,根据著名的四色定理,我们使用四种颜色就足够了。

填充方案二

我们在上图的基础上继续填充:

0400

小心,这里有陷阱:

sum3

也就是说,长方形-7实际上没有办法放到那个位置的。

填充方案三

我们从头开始用另外的方案的填充:

1600

1600-1

(注:下图是上图的局部放大,本小节中提到的图都是指上图)

这次经过精心规划,填充了 64 个长方形进去。请注意,在上图中,除了长方形-1长方形-2以外,其他长方形都是成对出现的。比如说,先竖放长方形-3,那么长方形-4一定是横放在它下边。再比如说,先横放长方形-9,那么长方形-10一定是竖放在它右边。

沿着上图的上边界从左往右看,我们有:

sum4

沿着上图的左边界从上往下看,我们有:

sum5

沿着长方形-7长方形-8的右边界从上往下看,我们有:

sum6

也就是说,长方形-59 是可以填充到那个位置的,而且还留有一点点儿的空隙。

书上的答案

(葛立恒认为,它们可能填不满正方形;高德纳认为,它们有可能填满;帕塔许尼克尚未发表意见。)

我赞同葛立恒。你们呢?各位朋友有什么想法,可以在本文的评论中畅所欲言。

进一步的问题

我们可以思考以下两个问题:

  1. 填充进正方形的所有长方形的面积之和 S 是多少?
  2. 无法填充进正方形的长方形的最小编号 n 是多少?

对于上述两个问题,有下述不等式:

sum7

我们已经知道:

  • 对于高德纳来说,S = 1、n = ∞。
  • 对于葛立恒来说,S < 1、n < ∞。
  • 对于填充方案三来说,S ≥ 64/65、n ≥ 65 。

当然,这里的填充方案必须是合理的。

0100

在上图中,由于长方形-1的位置不适当,长方形-2无论如何都填充不进去了。

有理数的运算

前面几个小节中的分数的运算,可以使用 Ruby 交互环境:

$ irb
irb(main):001:0> '1/3'.to_r+'1/5'.to_r+'1/5'.to_r+'1/7'.to_r+'1/8'.to_r
=> (841/840)
irb(main):002:0> '1/4'.to_r+'1/6'.to_r+'1/12'.to_r+'1/2'.to_r
=> (1/1)
irb(main):003:0> '1/3'.to_r+'1/5'.to_r+'1/10'.to_r+'1/30'.to_r+'1/3'.to_r
=> (1/1)
irb(main):004:0> ('1/7'.to_r+'1/9'.to_r)-('1/15'.to_r+'1/17'.to_r+'1/17'.to_r+'1/19'.to_r)-'1/60'.to_r
=> (29/81396)
irb(main):005:0> exit

也可以使用 F# 交互环境:

$ fsharpi

F# Interactive for F# 3.0 (Open Source Edition)
Freely distributed under the Apache 2.0 Open Source License

For help type #help;;

> #r "FSharp.PowerPack.dll";;

--> Referenced '/home/ben/repo/FSharpPowerPack-4.0.0.0/bin/gac/FSharp.PowerPack.dll'

> 1N/3N+1N/5N+1N/5N+1N/7N+1N/8N;;
val it : BigRational = 841/840N
> 1N/4N+1N/6N+1N/12N+1N/2N;;
val it : BigRational = 1N
> 1N/3N+1N/5N+1N/10N+1N/30N+1N/3N;;
val it : BigRational = 1N
> (1N/7N+1N/9N)-(1N/15N+1N/17N+1N/17N+1N/19N)-1N/60N;;
val it : BigRational = 29/81396N
> #quit;;

- Exit...

ConcreteMath