\begingroup

我将首先给出该问题的数学描述,我认为这对于高中 MOers 来说是一个好问题。

给定正整数, n≥3n3m, n \geq 3, 在哪里m是一个奇数,考虑一个矩形m列和nnn行,分为nnmn小的1 × 11×11 \times 1正方形。此矩形的良好着色方法是将每个小正方形涂成黑色或白色,并满足以下条件:

  • 所有的白色方块都是相连的。
  • 对于每个黑色方块,至少一个共享共同顶点(因此可以是水平、垂直或对角线相邻)的方块是白色的;
  • 底部中间的正方形是白色的。

在所有可能的良好着色中,找到最少数量的白色方块。

我想答案取决于n , mnm,n模3。我知道什么时候m = n = 5=n=5m=n=5,答案应该是8。然而,我找不到一个可以推广到所有n , mnm, n

这个问题的背景:这是一个关于星露谷 (Stardew Valley) 中最佳酒桶布局的问题,星露谷是一款很棒的 Steam 游戏。你需要在一个房间内放置尽可能多的酒桶(黑色方块),房间形状为nnmn尽可能多地移动,但同时要留出一条路径(白色方块)供您移动。如果桶与您水平、垂直或对角相邻,您可以操作它。我们给底部的中点上色,因为毕竟我们需要一扇门来盖这所房子。根据 Stardew Valley wiki,当m = 11 , n = 9=11n=9m = 11, n = 9,答案应该是 32(67 桶),当m = 17 , n = 12=17n=12m = 17, n = 12答案应该是 67 (137 桶)。

以下情况被认为是最佳的m = 11 , n = 9=11n=9m = 11, n = 9m = 17 , n = 12=17n=12m = 17, n = 12由星露谷玩家创作。

\endgroup

1

  • \begingroup
    类似:
    \endgroup


    – 


最佳答案
3

\begingroup

为了证明nnn是的倍数333在这种情况下,考虑一次增加一个方格的白色空间网络。每个新的白色方格最多可以333新的方格可以进入(原始方格除外),因为其他的666已经可以从你到达它的前一个白色方块访问。因此要添加三千33k可访问的方块(黑色或白色)需要添加至少k白色方块。

我们从白色方形渲染开始我们的网络666正方形可以访问,因此可以覆盖nnmn我们需要添加一个额外的n 6n6 mn-6正方形,需要额外的13n 213n2\frac13 mn-2白色方块,总共13n 113n1\frac13 mn-1所示的布置实现了该界限,因此是最佳的。

这提供了13n 113n1\lceil \frac13 mn\rceil-1白色方块,无论mnnn,而且这始终是可以实现的。


实际上,我还需要证明每个方块都可以通过最佳排列访问:这很容易,因为如果存在不可访问的方块,则某些方块必须与可访问区域接壤,这意味着有一个方块可以只用一个白色方块访问(即净000黑色方格)。通过反复进行此操作,我们会找到一种排列方式,其中每个方格都是可访问的,并且至少具有同样高的容量。

\endgroup

0

\begingroup

我将稍微概括一下你的问题。将房子的“门槛”定义为与门相邻的地板方块。你指定门槛应该位于底行的中间;我将给出一种当门槛是任何边缘方块(角落除外)时有效的策略。

定理:对于一栋m行和nnn列中,成功放置酒桶的最少白色方块数是13n 113n1\lceil \tfrac13mn\rceil-1

证明:不失一般性,假设门槛位于南墙。

我将根据以下剩余内容,通过几种情况来说明这一策略:mnnn模数333。此外,我只会展示一个例子,并希望能够推广到更大的mnnn显然,其剩余部分与示例相同。请注意,图中未显示门槛方块;您可以删除南墙上任何非角落的桶,并将其设为门槛。

这些排列是最优的,这可以从中看出。更直接地,你可以看到,当你在这些排列中一次添加一个白色方块时,你总是让三个新方块“可访问”,用 Zoe 的话来说。由于 Zoe 的证明表明你每次最多可以让三个新方块可访问,因此这些是最优的。

案例 0: m 0模式3 0模式3m\equiv 0\pmod 3nnn随意的。

 # # # # # # #
 # . . . . . #
 # . # # # # #
 # . # # # # #
 # . . . . . #
 # # # # # # #

案例 1.0: m 1模式3 1模式3m\equiv 1\pmod 3n 0模式3 n0模式3n\equiv 0\pmod 3

 # # # # # # # # #  
 # . # # . # # . #
 # . . . . . . . #
 # . # # # # # # #
 # . # # # # # # #
 # . . . . . . . #
 # # # # # # # # #

案例 1.1: m 1模式3 1模式3m\equiv 1\pmod 3n 1模式3 n1模式3n\equiv 1\pmod 3

 # # # # # # # # # # 
 # . # # . # # . . #
 # . . . . . . . . #
 # . # # # # # # # #
 # . # # # # # # # #
 # . . . . . . . . #
 # # # # # # # # # #

案例 1.2: m 1模式3 1模式3m\equiv 1\pmod 3n 2模式3 n2模式3n\equiv 2\pmod 3

 # # # # # # # # # # #  
 # . # # . # # . # . #
 # . . . . . . . . . #
 # . # # # # # # # # #
 # . # # # # # # # # #
 # . . . . . . . . . #
 # # # # # # # # # # #

案例 2.0: m 2模式3 2模式3m\equiv 2\pmod 3n 0模式3 n0模式3n\equiv 0\pmod 3

 # # # # # # # # #
 # . # # . # # . #  
 # . # # . # # . #
 # . . . . . . . #
 # . # # # # # # #
 # . # # # # # # #
 # . . . . . . . #
 # # # # # # # # #

案例 2.1: m 2模式3 2模式3m\equiv 2\pmod 3n 1模式3 n1模式3n\equiv 1\pmod 3

 # # # # # # # # # #
 # . # # . # # . . #  
 # . # # . # # . # #
 # . . . . . . . . #
 # . # # # # # # # #
 # . # # # # # # # #
 # . . . . . . . . #
 # # # # # # # # # #

案例 2.2: m 2模式3 2模式3m\equiv 2\pmod 3n 2模式3 n2模式3n\equiv 2\pmod 3

 # # # # # # # # # # #
 # . # # . # # . . . #  
 # . # # . # # . # # #
 # . . . . . . . . . #
 # . # # # # # # # # #
 # . # # # # # # # # #
 # . . . . . . . . . #
 # # # # # # # # # # #

\endgroup

\begingroup

简单的情况就是你已经展示的情况,nnn是的倍数333。 你有n3n3\frac n3每排都有过道,每排都有22m-2白色方块。除了最上面一行,其他行中间只有一个白色方块,所以你有n32 +2 n31 =n31n32+2n31=n31\frac n3(m-2)+\frac {2n}3-1=\frac {mn}3-1白色方块。这和你给出的图表一致。

什么时候nnn比 的倍数小一333我看不出有什么比从你的一张图片中删除最下面一行更好的方法。你现在有n + 13n+13\frac {n+1}3过道22m-2正方形和2n 232n23\frac {2n-2}3中间过道有更多方块n + 132 +2n 23n+132+2n23\frac {n+1}3(m-2)+\frac {2n-2}3白色方块。

什么时候nnn比 的倍数大一333这非常令人沮丧。你必须删除另一行几乎满的行。

所有这些都假设m足够大于nnn。 如果nnn足以大于m垂直过道比水平过道更好。我留给你去思考这个问题和交叉点。现在最简单的情况是m是的倍数333

\endgroup

0