我将首先给出该问题的数学描述,我认为这对于高中 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
–
|