UyHiP趣题：按照盒子的三边长之和来计费有没有漏洞？

    今天的趣题来自 UyHiP 今年十月的趣题。

    许多快递公司都依据物件的长、宽、高三边之和来收费，一些航空公司也要求托运行李的三边长相加不能超过某个限制。那么是否有人想过，有没有可能把一个三边之和较大的盒子装进一个三边之和较小的盒子里，从而骗取更低的费用呢？有人会说，恐怕不行吧，长宽高之和更大的盒子体积不也应该更大一些吗？不见得。比方说，盒子 A 的长宽高分别是 10 、 10 、 10 ，盒子 B 的长宽高分别是 9 、 9 、 12.1 。盒子 B 的三边长之和显然比盒子 A 要大，但体积只有 980.1 ，比前者要小近 20 个单位。那么，为什么就不能把盒子 B 沿斜线方向塞进盒子 A 呢？有人会敏锐地发现，在上面的例子中，盒子 A 的体对角线长为 17.3205 ，但盒子B的对角线长度达到 17.5616 ，显然无法完全放进盒子 A 里。不过且慢，我也能举出这样的例子，三边和更大的盒子其体积和对角线都比小的盒子的要小。盒子 A 的长宽高分别为 10 、 10 、 20 ，盒子 B 的长宽高分别为 7.1 、 16.5 、 16.5 。盒子 B 的长宽高之和比盒子 A 大，体积为 1932.98 ，对角线长度比前者小大约 0.1 。看来，为了解决这个问题，我们还需要从一些更巧妙的方面入手。

    其实我偷了一个懒。这个 Blog 之前就曾经介绍过这个有趣的数学问题，上面的文字直接取自那篇文章。不过，当时我们给出的解法来自 Peter Winkler ，是一个虽然巧妙但却并不那么美观的方法。 UyHiP 给出了一个基于线性代数的解答。这个解答不但更加漂亮，而且直接适用于任意维度的情况。下面我们来证明，在任意维度中，我们都无法把 n 边长之和更大的盒子放进 n 边长之和更小的盒子。

    令 d 是一个 n 维向量，向量中的 n 个正实数依次表示小盒子 n 个维度上的长度。假设我们现在要把它以一个很诡异的角度放进大盒子里。让我们用一个 n × n 的矩阵 A 来表示小盒子的放置角度，矩阵的每一行都是一个单位向量，依次表示小盒子各个维度上的边在大盒子中的方向。

    n 维盒子共有 2ⁿ 个顶点，每个顶点都有一个与之完全相对的顶点，因而整个小盒子中一共有 2ⁿ 条体对角线向量。这些体对角线向量是很容易求出来的，它们就是小盒子各个维度上的边的向量和，也就是 ± d₁A₁ ± d₂A₂ ... ± d_nA_n 。如果考虑所有 2ⁿ 条体对角线向量，我们也就会取遍上式中所有可能的 2ⁿ 种正负号组合。大盒子第 i 个维度上的长度，必须大于等于所有可能的体对角线在第 i 个维度上的分量的最大值，也就是 d₁ · |A_1i| + d₂ · |A_2i| ... + d_n · |A_ni| 。因此，大盒子所有维度上的长度之和，至少也就有

        d₁ · |A₁₁| + d₂ · |A₂₁| ... + d_n · |A_n1|
      + d₁ · |A₁₂| + d₂ · |A₂₂| ... + d_n · |A_n2|
      + d₁ · |A₁₃| + d₂ · |A₂₃| ... + d_n · |A_n3|
      + ... ...
      + d₁ · |A_1n| + d₂ · |A_2n| ... + d_n · |A_nn|

    换一种方式累加起来，也就是 d₁ · ∑_i |A_1i| + d₂ · ∑_i |A_2i| ... + d_n · ∑_i |A_ni| 。下面我们将证明，对于任意 r 都有 ∑_i |A_ri| ≥ 1 ，从而完成全部证明。

    注意到矩阵 A 是一个正交矩阵，它的每一行数的平方和都等于 1 。由于正交矩阵的转置仍然是正交矩阵，因此矩阵 A 的每一列数的平方和也都等于 1 。也就是说， ∑_i A_ri² = 1 。然而 ( ∑_i |A_ri| )² = ∑_i A_ri² + ∑_i≠j ( |A_ri| · |A_rj| ) ≥ ∑_i A_ri² = 1 ，也就说明 ∑_i |A_ri| 是大于等于 1 的。