我将首先给出该问题的数学描述，我认为这对于高中 MOers 来说是一个好问题。
给定正整数米, n≥3米，n≥3m, n \geq 3， 在哪里米米m是一个奇数，考虑一个矩形米米m列和nnn行，分为n米nmn小的1 × 11×11 \times 1正方形。此矩形的良好着色方法是将每个小正方形涂成黑色或白色，并满足以下条件：
- 所有的白色方块都是相连的。
- 对于每个黑色方块，至少一个共享共同顶点（因此可以是水平、垂直或对角线相邻）的方块是白色的；
- 底部中间的正方形是白色的。
在所有可能的良好着色中，找到最少数量的白色方块。
我想答案取决于n , m米，nm,n模3。我知道什么时候m = n = 5米=n=5m=n=5，答案应该是8。然而，我找不到一个可以推广到所有n , m米，nm, n。
这个问题的背景：这是一个关于星露谷 (Stardew Valley) 中最佳酒桶布局的问题，星露谷是一款很棒的 Steam 游戏。你需要在一个房间内放置尽可能多的酒桶（黑色方块），房间形状为n米nmn尽可能多地移动，但同时要留出一条路径（白色方块）供您移动。如果桶与您水平、垂直或对角相邻，您可以操作它。我们给底部的中点上色，因为毕竟我们需要一扇门来盖这所房子。根据 Stardew Valley wiki，当m = 11 , n = 9米=11，n=9m = 11, n = 9，答案应该是 32（67 桶），当m = 17 , n = 12米=17，n=12m = 17, n = 12答案应该是 67 (137 桶)。
以下情况被认为是最佳的m = 11 , n = 9米=11，n=9m = 11, n = 9和m = 17 , n = 12米=17，n=12m = 17, n = 12由星露谷玩家创作。
\endgroup
1
最佳答案
3
为了证明nnn是的倍数333在这种情况下，考虑一次增加一个方格的白色空间网络。每个新的白色方格最多可以333新的方格可以进入（原始方格除外），因为其他的666已经可以从你到达它的前一个白色方块访问。因此要添加三千3钾3k可访问的方块（黑色或白色）需要添加至少钾钾k白色方块。
我们从白色方形渲染开始我们的网络666正方形可以访问，因此可以覆盖n米nmn我们需要添加一个额外的米n − 6米n−6 mn-6正方形，需要额外的13米n − 213米n−2\frac13 mn-2白色方块，总共13米n − 113米n−1\frac13 mn-1所示的布置实现了该界限，因此是最佳的。
这提供了⌈13米n ⌉ − 1⌈13米n⌉−1\lceil \frac13 mn\rceil-1白色方块，无论米米m和nnn，而且这始终是可以实现的。
实际上，我还需要证明每个方块都可以通过最佳排列访问：这很容易，因为如果存在不可访问的方块，则某些方块必须与可访问区域接壤，这意味着有一个方块可以只用一个白色方块访问（即净000黑色方格）。通过反复进行此操作，我们会找到一种排列方式，其中每个方格都是可访问的，并且至少具有同样高的容量。
\endgroup
0
|
我将稍微概括一下你的问题。将房子的“门槛”定义为与门相邻的地板方块。你指定门槛应该位于底行的中间；我将给出一种当门槛是任何边缘方块（角落除外）时有效的策略。
定理：对于一栋米米m行和nnn列中，成功放置酒桶的最少白色方块数是⌈13米n ⌉ − 1⌈13米n⌉−1\lceil \tfrac13mn\rceil-1。
证明：不失一般性，假设门槛位于南墙。
我将根据以下剩余内容，通过几种情况来说明这一策略：米米m和nnn模数333。此外，我只会展示一个例子，并希望能够推广到更大的米米m和nnn显然，其剩余部分与示例相同。请注意，图中未显示门槛方块；您可以删除南墙上任何非角落的桶，并将其设为门槛。
这些排列是最优的，这可以从中看出。更直接地，你可以看到，当你在这些排列中一次添加一个白色方块时，你总是让三个新方块“可访问”，用 Zoe 的话来说。由于 Zoe 的证明表明你每次最多可以让三个新方块可访问，因此这些是最优的。
案例 0： m ≡ 0（模式3 ）米≡0（模式3）m\equiv 0\pmod 3，nnn随意的。
# # # # # # #
# . . . . . #
# . # # # # #
# . # # # # #
# . . . . . #
# # # # # # #
案例 1.0： m ≡ 1（模式3 ）米≡1（模式3）m\equiv 1\pmod 3，n ≡ 0（模式3 ）n≡0（模式3）n\equiv 0\pmod 3。
# # # # # # # # #
# . # # . # # . #
# . . . . . . . #
# . # # # # # # #
# . # # # # # # #
# . . . . . . . #
# # # # # # # # #
案例 1.1： m ≡ 1（模式3 ）米≡1（模式3）m\equiv 1\pmod 3，n ≡ 1（模式3 ）n≡1（模式3）n\equiv 1\pmod 3。
# # # # # # # # # #
# . # # . # # . . #
# . . . . . . . . #
# . # # # # # # # #
# . # # # # # # # #
# . . . . . . . . #
# # # # # # # # # #
案例 1.2： m ≡ 1（模式3 ）米≡1（模式3）m\equiv 1\pmod 3，n ≡ 2（模式3 ）n≡2（模式3）n\equiv 2\pmod 3。
# # # # # # # # # # #
# . # # . # # . # . #
# . . . . . . . . . #
# . # # # # # # # # #
# . # # # # # # # # #
# . . . . . . . . . #
# # # # # # # # # # #
案例 2.0： m ≡ 2（模式3 ）米≡2（模式3）m\equiv 2\pmod 3，n ≡ 0（模式3 ）n≡0（模式3）n\equiv 0\pmod 3。
# # # # # # # # #
# . # # . # # . #
# . # # . # # . #
# . . . . . . . #
# . # # # # # # #
# . # # # # # # #
# . . . . . . . #
# # # # # # # # #
案例 2.1： m ≡ 2（模式3 ）米≡2（模式3）m\equiv 2\pmod 3，n ≡ 1（模式3 ）n≡1（模式3）n\equiv 1\pmod 3。
# # # # # # # # # #
# . # # . # # . . #
# . # # . # # . # #
# . . . . . . . . #
# . # # # # # # # #
# . # # # # # # # #
# . . . . . . . . #
# # # # # # # # # #
案例 2.2： m ≡ 2（模式3 ）米≡2（模式3）m\equiv 2\pmod 3，n ≡ 2（模式3 ）n≡2（模式3）n\equiv 2\pmod 3。
# # # # # # # # # # #
# . # # . # # . . . #
# . # # . # # . # # #
# . . . . . . . . . #
# . # # # # # # # # #
# . # # # # # # # # #
# . . . . . . . . . #
# # # # # # # # # # #
\endgroup
|
简单的情况就是你已经展示的情况，nnn是的倍数333。 你有n3n3\frac n3每排都有过道，每排都有米− 2米−2m-2白色方块。除了最上面一行，其他行中间只有一个白色方块，所以你有n3（米− 2 ）+2 n3− 1 =n3− 1n3（米−2）+2n3−1=米n3−1\frac n3(m-2)+\frac {2n}3-1=\frac {mn}3-1白色方块。这和你给出的图表一致。
什么时候nnn比 的倍数小一333我看不出有什么比从你的一张图片中删除最下面一行更好的方法。你现在有n + 13n+13\frac {n+1}3过道米− 2米−2m-2正方形和2n − 232n−23\frac {2n-2}3中间过道有更多方块n + 13（米− 2 ）+2n − 23n+13（米−2）+2n−23\frac {n+1}3(m-2)+\frac {2n-2}3白色方块。
什么时候nnn比 的倍数大一333这非常令人沮丧。你必须删除另一行几乎满的行。
所有这些都假设米米m足够大于nnn。 如果nnn足以大于米米m垂直过道比水平过道更好。我留给你去思考这个问题和交叉点。现在最简单的情况是米米m是的倍数333。
\endgroup
0
|
类似：
\endgroup
–
|