Beatrix 将多米诺骨牌水平或垂直地放在 5×5 的棋盘上,这样每张多米诺骨牌可以覆盖两个小方格。当她无法再放置多米诺骨牌时,她就会停下来,如图所示。
当 Beatrix 停下来时,最多还能发现多少个方格?
澄清1:水平多米诺骨牌的数量不一定与垂直多米诺骨牌的数量相同。
澄清 2:当 Beatrix 放置多米诺骨牌时,她不一定会在水平和垂直多米诺骨牌之间交替放置。
澄清3:多米诺骨牌一旦放置就无法移动。
归因:2016 年英国青少年数学挑战赛
\endgroup
最佳答案
3
答案是
7 个正方形。
最优性证明:
因为有 25 个方格,而多米诺骨牌必须占据相等的面积,所以没有 8 个方格的解决方案。假设有一个有 9 个空方格的解决方案。我们可以像这样用棋盘格图案给网格涂色,每张多米诺骨牌必须涂上一个深色方格和一个浅色方格。一
共有 13 个浅色方格和 12 个深色方格,所以如果有 9 个方格的解决方案,它必须有 5 个浅色方格和 4 个深色方格未被覆盖。
让我们来看看这四个深色方格。每个方格都有两个截然不同的位置可以放置 – 边缘或中心。边缘的深色方格会消除三个潜在的浅色方格位置,中心的深色方格会消除四个。此外,我们不能在同一个角落放置两个深色方格,因为角落方格会被挡住,不能在上面放置多米诺骨牌。
潜在的亮色方块位置有 13 个,因此我们需要至少其中 5 个未被阻挡,即最多可以阻挡 8 个。由于深色方块至少阻挡了 12 个亮色方块,因此我们需要至少其中 4 个重叠。实际上,由于我们不能在同一个角落有两个深色方块,因此我们需要至少一个方块位于中心以使两个方块重叠(而我们可以在同一边缘上有两个深色方块,从而阻挡太多方块):
这意味着这些(感谢)是唯一可以留下足够亮色方块未被阻挡的配置(直到旋转):
但显然不可能在这些亮色方块周围放置多米诺骨牌,因此不存在 9 块瓷砖的解决方案。
\endgroup
2
-
\begingroup
暗方块间隙有第二种有效的排列——隔离 T 的路径——但它存在与第一种完全相同的问题。
\endgroup
– -
\begingroup
也许可以添加一句话来解释为什么由于奇偶校验,你不能有 8 张未覆盖的牌。
\endgroup
–
|
证明最优性的另一种方法:
如果你像这样分割它:
请注意,在四个 2×3 矩形中,不能有三个未覆盖的正方形,因为它们必须呈棋盘状,但这样就没有地方放多米诺骨牌了。因此,如果有九个未覆盖的正方形,则每个 2×3 矩形中必须恰好有两个,中间有一个。
这里可能存在多米诺骨牌吗?
不,因为没有办法在左下角的 2×3 中添加两个未覆盖的方块。因此,为了使中心方块未被覆盖,我们需要执行如下操作:
现在,要在每个 2×3 中放置两个未覆盖的方块,需要它们尽可能地分开,但这会导致相邻 2×3 区域中未覆盖的方块紧挨着彼此,这是一种矛盾。
\endgroup
|
7 个孔是最佳的
在马丁·加德纳 (Martin Gardner) 所著的《打结的甜甜圈》一书中,第 15 章写道:“桑兹能够证明孔的数量不能超过多米诺骨牌的数量。”对于宽度和高度为> 1>1>1。
\endgroup
1
-
\begingroup
据推测,最后的结果并不适用于诸如1×1
和之类的琐碎板1×4
?
\endgroup
–
|
|