每日一题[1465]递归

一个国际象棋棋盘（由 $8\times 8$ 个方格组成），其中有一个小方格因破损而被剪去（破损位置不确定）．“L”形骨牌由三个相邻的小方格组成，如图所示．现要将这个破损的棋盘剪成数个“L”形骨牌，则（       ）

A．至多能剪成 $19$ 块“L”形骨牌

B．至多能剪成 $20$ 块“L”形骨牌

C．一定能剪成 $21$ 块“L”形骨牌

D．前三个答案都不对

答案       C．

解析       可以用数学归纳法证明更一般的结论：对于由 $2^n\times 2^n$ 个方格组成的棋盘，其中有一个小方格因破损而被剪去（破损位置不确定），则这个破损的棋盘一定能剪成 $\dfrac{4^n-1}{3}$ 块“L”形骨牌，即可以用 $\dfrac{4^n-1}{3}$ 块“L”形骨牌将其覆盖，且无余漏．

如图，将 $2^{n+1}\times 2^{n+1}$ 的棋盘划分为 $4$ 个 $2^n\times 2^n$ 个棋盘，不妨设左上角的 $2^n\times 2^n$ 棋盘有破损，则在中心放置对应的“L”形，剩下的 $3$ 个棋盘亦为有破损的 $2^n\times 2^n$ 棋盘，根据归纳假设即得．