IBM Ponder this 2016 July

r_64 posted @ 2016年8月01日 11:39 in 未分类 with tags ibm , 454 阅读

题目链接

我的题解(写得这么不清楚居然能通过)

题意就是,求一个五格骨牌的组合,其中至多包含三个五格骨牌。要求每一个$4^N\times 4^N$的棋盘去掉任意一个格子之后都可以被这个组合拼出来。骨牌可以旋转和翻转。

例如:考虑r型三格骨牌,它可以拼出任意$2^N\times 2^N$的棋盘去掉任意一个格子。

我开始不知道能否翻转。。给出了一个$2$个块(可以翻转),$3$个块(不能翻转)的方案。。自我感觉还不错吧。。

现在开始剧透

答案是

(答案不唯一)

证明:首先考虑用这两个小家伙拼出大一倍的家伙:

这样,通过一次一次地迭代可以构造出边长是原图像的$2^k$倍的块,其中$k$是任意自然数。

然后考虑用它们拼出$4\times 4$的情况:

注意因为允许旋转和翻转,所以只要考虑这三种情况。

现在考虑$4^N\times 4^N$的情况,把棋盘分成$4\times 4=16$个块,每个块的大小是$4^{N-1}\times 4^{N-1}$。恰有一个块包含被删掉的空格,对这个块递归,考虑覆盖剩下的块,其实这就是拿大小为$2^{N-1}$倍的东西覆盖$4\times 4$的棋盘,显然可做。

发现这玩意很难表述清楚。。就算是用中文啊


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter