一個有趣的矩形剖分問題

顧森

如果一個矩形能裝進另一個矩形里（假設它們的對應邊互相平行）。那么這兩個矩形的長和寬需要滿足什么樣的條件呢？容易看出，前一個矩形的長必須小于等于后一個矩形的長，同時前一個矩形的寬也必須小于等于后一個矩形的寬，1973年，美國計算機科學家愛德華·萊因戈爾德提出了一個有趣的數(shù)學問題：能否把一個矩形分成若干個小矩形，使得任意一個小矩形都無法裝進另一個小矩形里？簡單試一試你就會發(fā)現(xiàn)，要想構造出這樣的例子其實并不容易。

但是，問題的答案是肯定的，其中的一種方案如圖l所示（為簡潔起見，左下角的矩形的尺寸未標示，它為18×1），而且，如果每個小矩形的長和寬都必須是整數(shù)，那么圖1就是這個問題的最小的解——整個大矩形的面積僅為22x13=286。

我們可以把萊因戈爾德的問題稍微修改一下：能否把一個正方形分成若干個小矩形，使得任意一個小矩形都無法裝進另一個小矩形里？問題的答案也是肯定的，其中的一種方案如圖2所示（最上面的矩形為27x1），這是目前已知的最小的解——整個大正方形的邊長僅為27，究竟還有沒有更小的解，仍然是未解之謎。