A Practical Guide To Quantitative Finance Interviews 收录了一些量化面试中的经典题目. 本文介绍的是来自第二章的「Box Packing」.

Box Packing #

Problem #

Can you pack 53 bricks of dimensions 1×1×4 into a 6×6×6 box?

Solution #

这里我们讨论的摆放方式只包括竖直、平放 (占据完整 $1\times 1\times 1$ 方块) 的方式. 放入 $52$ 个砖块的解法不难想到, 再进一步却很难. 事实上, 不可能在 $6\times 6\times 6$ 的盒子内放进 $53$ 块 $1\times 1\times 4$ 的砖块.

在给出证明之前, 先介绍一个二维版本的经典问题:

• 去掉左上角和右下角的国际象棋棋盘, 能否不重叠地摆放 $31$ 个 $1\times 2$ 的多米诺骨牌?

这个问题是染色法的代表题目. 把棋盘染成黑白交错的颜色, 那么去掉的左上角和右下角的格子是同色的. 一个骨牌会恰好占据一个黑色方块和一个白色方块, 然而这个残缺的棋盘中黑白格子数量不对等, 因此不能够摆放 $31$ 个骨牌.

同样的, 我们可以把 $6\times 6\times 6$ 的盒子切割成 $27$ 块 $2\times 2\times 2$ 的中等块, 并把它们间隔染成黑白色. 此时黑白色的中等块数量也是不对等的. 注意到一个 $1\times 1\times 4$ 的砖块必定会占用 $2$ 单位体积的黑色块与白色块, 因此想要放入 $53$ 块砖块至少分别需要 $53\times 2=106$ 体积的白色块与黑色块, 然而其中必有一种颜色体积至多为 $13 \times 2 \times 2 \times 2 = 104 < 106$ . 根据这一点可以断定, 不存在放入 $53$ 块砖块的方法.