平铺三角形网格

Question

设计并解释递归分而治之算法。有人有想法吗？

\n\n

给定一些 k \xe2\x89\xa5 2 的等腰直角三角形网格，如图 1(b) 所示，此问题要求您使用图 1(a) 中给出的图块完全覆盖它。网格的左下角不得被覆盖。没有两个图块可以重叠，并且所有图块必须完全保持在给定的三角形网格内。您必须使用图 1(a) 中所示的所有四种类型的图块，并且任何图块类型都不能覆盖总网格面积的 40% 以上。在将图块放在网格上之前，您可以根据需要旋转图块。\n

\n

Answer 1

这确实是归纳的思想，类似于著名的例子“L-Tile”覆盖

正如你所说，你已经解决了 k = 2 的问题，这是首先解决小例子的一个很好且正确的起点，但我认为这个问题对于 k = 2 的情况有点棘手，主要是因为每种类型不能超过40%的限制。

然后，对于 k>2，在您的示例中假设 k = 3，我们尝试利用您已解决的问题，即 k = 2 的情况

通过非常简单的观察，人们可能会注意到，对于 k = n，它实际上可以由 4 k=n-1 种情况组成（见下图）

现在中间的阴影部分形成了一个可以用1个B型填充的洞，所以我们可以先填充4个小n-1案例，然后用B型填充这个洞......

但这样的施工面临一个问题：B型将超过40%的面积！

考虑k = 2，无论你如何填充该区域，都必须使用2个B类型，我没有强有力的证据，但通过一些强力的尝试和错误，你应该被说服。然后，对于 k = 3，我们有 4 个小三角形，这意味着我们有 2*4 = 8 个 B 型，再加上 1 个来填充孔，将得到 9 个 B 型，每个使用 1.5 平方英尺，总共使用 13.5 平方英尺。

当 k = 3 时，总面积为 (2^3)^2 / 2 = 32 平方单位 13.5/32 = 0.42...这违反了约束！

那么该怎么办？这就是为什么我们必须使用技巧来处理 k = 2 情况的原因（我假设您已经完成了这部分，正如您所说的那样，您知道如何处理 k = 2 情况）

首先，我们知道使用我们的构造方法由4个小三角形构建一个大三角形，只有B型会违反这个约束（即40%面积），您可以自己验证。所以我们想要减少Type B的使用总数，但是每个小三角形必须至少使用2个Type B，所以我们唯一可以减少的地方就是大三角形中间的空洞，是否可以使用其他Type来代替B型的？同时，我们希望小三角形的其他部分保持不变，以便我们可以使用相同的参数进行归纳（即一般来说，使用相同的参数将 4 个 2^(n-1) 个三角形形成 2^n 三角形施工方法）

如果我们专门设计 k = 2 的情况，答案是肯定的， 请参见下面我的构造：（也许还有其他构造工程，但我只需要知道一个）

诀窍是我故意将 1 个 B 型移到空（灰色）三角形旁边 让我们在这里停一下，并进行一些验证：

为了构建 ak = 2 的情况，我们使用

• 2 A 型 = 2 平方英尺 < 40%
• 2 B 型 = 3 平方英尺 < 40%
• 1 C 型 = 1.5 平方英尺 < 40%
• 1 D 型 = 1 平方英尺 < 40%

总使用面积7.5平方，不错

现在想象一下，我们使用完全相同的方法来构建这 4 个三角形以制作一个大三角形，中间的三角形仍然是一个形状为 B 型的空洞，但现在我们不是用 1 个 B 型来填充它，而是将洞一起填充紧挨着它们的 3 个 B 型（回顾 k = 2 的情况），使用 A 型和 D 型 （为了便于理解，我使用与上面相同的配色方案），我们对构成孔的所有 3 个小三角形执行此操作中间。

这是最后一部分（我知道它很长......）我们减少了用较小的三角形构造大三角形时使用的类型 B 的数量，但同时我们增加了使用的类型 A 和 D 的数量！那么这种新的施工方法有效吗？

首先注意，除了灰色三角形旁边的 B 型之外，它不会改变小三角形的任何部分，即如果满足 40% 约束，则此方法是归纳和递归填充 2^n 边三角形

然后我们再统计一下我们使用的每种类型的数量。

对于 k = 3，总单位为 32，我们使用：

• 2*4+3 = 11 A 型 = 11 平方英尺 < 40%
• 2*4-3 = 5 B 型 = 7.5 平方英尺 < 40%
• 1*4 = 4 C 型 = 6 平方单位 < 40%
• 1*4+3 = 7 D 型 = 7 平方单位 < 40%

我们总共覆盖了 31.5 个单元，很好，现在让我们证明 k = n > 3 时满足 40% 约束

令 FA(n-1) 为用于使用我们的新方法填充 2^n-1 个三角形的 A 型总面积，同样，FB(n-1)、FC(n-1)、FD(n-1)具有相似的定义

假设F*(n-1)为真，即不超过总面积的40%，我们证明F*(n)为真。

我们有

FA(n) = FA(n-1)*4 + 3*1

FB(n) = FB(n-1)*4 - 3*1.5

FC(n) = FC(n-1)*4

FD(n) = FD(n-1)*4 + 3*1

我们只给出FD(n)的证明，其他三个应该用类似的方法证明（MI）

使用替换法，FD(n) = 2*(4^(n-2)) - 1 for n>=3（你至少应该尝试自己想出这个方程）

我们想展示FD(n)/(2^2(n)/2) < 0.4

IE2FD(n)/4^n < 0.4

考虑 LHS，

左轴 = (4*(4^(n-2)) - 2)/4^n

< 4^(n-1)/4^n = 1/4 < 0.4 QED

这意味着使用这种方法，对于任何 2^k 边三角形，所有 Type AD 都不会超过总面积的 40%，对于 k >= 3，最后我们归纳地表明，有一种满足所有约束的方法来构造这样的三角形。

长话短说

1. 困难的部分是满足40%的面积限制
2. 首先对 k = 2 的情况使用特殊构造，尝试用它来构建 k = 3 的情况（然后 k = 4，k = 5...归纳的想法！）
3. 当用k=n-1案例构建k=n案例时，写出每种类型消耗总面积的公式，并表明它们不会超过总面积的40%
4. 结合第 2 点和第 3 点，这是一种归纳方法，表明对于任何 k >= 2，有一种方法（我们描述过）可以在不打破任何约束的情况下填充 2^k 边三角形