每日一题[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$ 棋盘,根据归纳假设即得.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表评论