\begingroup

有一个三维网格（三个方向都是半无限的）。网格的每个单元格最多包含一只鸭子。你可以从单元格中移除一只鸭子，但前提是该单元格上方的单元格、右侧的单元格和前方的单元格都是空的。如果你确实从单元格中移除了一只鸭子，你必须放置三只鸭子，分别放在前面提到的三个空单元格中。

最初，网格中最底部、最左边、最后面的格子中只有一只鸭子。你能在有限步内清空图中所示的格子（包括其后面的隐藏格子）吗？

来源：受到的启发。

\endgroup


最佳答案
2

\begingroup

给定网格中鸭子的任意配置，

通过对所有已占用单元格的值求和来为其分配分数3− n3−n3^{-n}， 在哪里nnn是该单元格到初始角落单元格的曼哈顿距离。

我们可以得出四个主要观察结果：

  1. 初始得分为3− 0= 13−0=13^{-0}=1。

  2. 得分是不变的：用鸭子得分代替3− n3−n3^{-n}和333鸭子每次得分3− （n + 1 ）3−（n+1）3^{-(n+1)}不会改变总分。

  3. 网格中所有单元格的可能得分总和为

    ∑我= 0∞∑j = 0∞∑k = 0∞3− （i + j + k ）=∑我= 0∞3−我∑j = 0∞3−j​∑k = 0∞3−k​=（∑我= 0∞3−我）3=（11 −3− 1）3=二十七8。∑我=0∞∑杰=0∞∑钾=0∞3−（我+杰+钾）=∑我=0∞3−我∑杰=0∞3−杰∑钾=0∞3−钾=（∑我=0∞3−我）3=（11−3−1）3=二十七8。

    \begin{align}\sum_{i=0}^\infty\sum_{j=0}^\infty\sum_{k=0}^\infty3^{-(i+j+k)}&=\sum_{i=0}^\infty3^{-i}\sum_{j=0}^\infty3^{-j}\sum_{k=0}^\infty3^{-k}\\&=\left(\sum_{i=0}^\infty3^{-i}\right)^3\\&=\left(\frac1{1-3^{-1}}\right)^3\\&=\frac{27}8.\end{align}

  4. 所示单元格可能的总得分为1 ⋅3− 0+ 3 ⋅3− 1+ 6 ⋅3− 2=831⋅3−0+3⋅3−1+6⋅3−2=831\cdot3^{-0}+3\cdot3^{-1}+6\cdot3^{-2}=\frac83。

根据这些观察，

任何配置中显示的单元格全部为空的得分最多为二十七8−83=1724< 1二十七8−83=1724<1\frac{27}8-\frac83=\frac{17}{24}<1，因此不可能清空从最初的鸭子开始所示的单元格。

\endgroup

\begingroup

首先，我们为每个单元格分配一个“权重”

的13d13d\frac{1}{3^d}， 在哪里ddd是该像元与左下角后角的曼哈顿距离。

将鸭子从距离较远的单元格移出钾钾k，因此重量1 /3钾1/3钾1/3^k，将产生三个距离为千+一钾+1k+1和重量1 /3千+一1/3钾+11/3^{k+1}，因此在鸭子移动的情况下总重量保持不变。

最初，我们有111重量单位。因此，要将所有鸭子移出给定区域，我们需要

找到给定区域外的一组单元格，其权重总和为 1。对于任何给定距离内的所有单元格钾钾k，我们有千+一钾+1k+1底层对角线上的细胞，钾钾k第二层的细胞，最终111单元格千+一钾+1k+1第层。因此，距离钾钾k是

1 + 2 + … + k + ( k + 1 ) =​​∑我= 0千+一我=（k + 1 ）（k + 2 ）21+2+。。。+钾+（钾+1）=∑我=0钾+1我=（钾+1）（钾+2）2

1 + 2 + … + k + (k+1) = \sum_{i=0}^{k+1} i = \frac{(k+1)(k+2)}{2}
它们的总重量是（k + 1 ）（k + 2 ）2 ⋅3钾（钾+1）（钾+2）2⋅3钾 \frac{(k+1)(k+2)}{2 \cdot 3^k} ，因此给定区域之外的所有单元格的总权重为

1033+1534+2135+二十八36+ … =​​∑我= 3∞（i + 1 ）（i + 2 ）2 ⋅3我1033+1534+2135+二十八36+。。。=∑我=3∞（我+1）（我+2）2⋅3我

\frac{10}{3^3} + \frac{15}{3^4} + \frac{21}{3^5} + \frac{28}{3^6} + … = \sum_{i=3}^{\infty} \frac{(i+1)(i+2)}{2 \cdot 3^i}
并移动整个重量111在给定区域之外，该总和需要大于111。

现在，一些代数：

两个连续项的比率是林我→ ∞（i + 1 ）（i + 2 ）2 ⋅3我（一）（一+ 1 ）2 ⋅3（i − 1 )=林我→ ∞我+2​3我=林我→ ∞13+23我=13林我→∞（我+1）（我+2）2⋅3我（我）（我+1）2⋅3（我−1）=林我→∞我+23我=林我→∞13+23我=13 \lim_{i\to\infty} \frac{\frac{(i+1)(i+2)}{2 \cdot 3^i}}{\frac{(i)(i+1)}{2 \cdot 3^(i-1)}} = \lim_{i\to\infty} \frac{i+2}{3i} = \lim_{i\to\infty} \frac{1}{3}+\frac{2}{3i} = \frac{1}{3}小于111因此，通过比率检验，该序列收敛到某个和年代年代S.现在，让

年代=∑我= 3∞（i + 1 ）（i + 2 ）2 ⋅3我= 3∑我= 3∞（i + 1 ）（i + 2 ）2 ⋅3我+ 1= 3∑我= 4∞我(我+ 1 )2 ⋅3我=3∑我= 4∞（i + 2 ）（i + 1 ）−2 （i + 1 ）​2 ⋅3我= 3 (小号−10二十七−∑我= 4∞我3我−∑我= 4∞13我）= 3 (小号−10二十七−112−154） =3秒−1712⟹二​=1712⟹年代=1724< 1年代=∑我=3∞（我+1）（我+2）2⋅3我=3∑我=3∞（我+1）（我+2）2⋅3我+1=3∑我=4∞我（我+1）2⋅3我=3∑我=4∞（我+2）（我+1）−2（我+1）2⋅3我=3（年代−10二十七−∑我=4∞我3我−∑我=4∞13我）=3（年代−10二十七−112−154）=3年代−1712⟹2年代=1712⟹年代=1724<1

S = \sum_{i=3}^{\infty} \frac{(i+1)(i+2)}{2 \cdot 3^i} = 3 \sum_{i=3}^{\infty} \frac{(i+1)(i+2)}{2 \cdot 3^{i+1}} = 3 \sum_{i=4}^{\infty} \frac{i(i+1)}{2 \cdot 3^i} = \\ 3 \sum_{i=4}^{\infty} \frac{(i+2)(i+1) – 2(i+1)}{2 \cdot 3^i} = 3 \left(S – \frac{10}{27} – \sum_{i=4}^{\infty} \frac{i}{3^i} – \sum_{i=4}^{\infty} \frac{1}{3^i}\right) = 3\left(S – \frac{10}{27} – \frac{1}{12} – \frac{1}{54}\right) = 3 S – \frac{17}{12} \implies 2 S = \frac{17}{12} \implies S = \frac{17}{24} < 1
因此，给定区域外的权重小于 1，不可能清除该区域中的鸭子。

\endgroup