巧克力掰块

Chocolate Bar

专题: Discrete Math / 离散数学
难度: L4
来源: Brainstellar

题目详情

一块 6×8 的巧克力由 48 个 1×1 小方块组成。

每次只能选择一块现有巧克力沿网格线横向或纵向掰成两块（不能一次掰两块）。

问：最少掰多少次能把它分成 48 个 1×1 小块？

There is a 6x8 rectangular chocolate bar made up of small 1x1 bits. We want to break it into the 48 bits. We can break one piece of chocolate horizontally or vertically, but cannot break two pieces together! What is the minimum number of breaks required?

解析

最少需要 47 次。

每次掰开只会让“块数”增加 1。初始 1 块，目标 48 块，因此至少需要 $48-1=47$ 次，且可达到。

Original Explanation

Solution

For a chocolate of size mxn, we need mn - 1 steps. By breaking an existing piece horizontally or vertically, we merely increase the total number of pieces by one. Starting from 1 piece, we need mn - 1 steps to get to mn pieces. Another way to reach the same conclusion is to focus on "bottom left corners of squares": Keep the chocolate rectangle in front of you and start drawing lines corresponding to cuts. Each cut "exposes" one new bottom left corner of some square. Initially, only one square's bottom left corner is exposed. In the end, all mn squares have their bottom left corners exposed.