深入探究大楼丢鸡蛋问题(胡扯版)

发布于

这篇博客已过时

最新版

题意

有一个 $N$ 层的大楼,你有 $M$ 个鸡蛋。每个鸡蛋的硬度都是相同的。碎鸡蛋不能用来测试。你要求出 至少扔多少次才能保证测出鸡蛋的硬度。
假设你在第 $x$ 层扔下鸡蛋,如果鸡蛋碎了,说明鸡蛋硬度不能承受在 $x$ 层扔下。如果没碎则说明鸡蛋硬度能承受在 $x$ 层扔下。

题解

动态规划解法

首先,我们可以看到网上的讨论,这是一道动态规划问题。
记 $f_{i, j}$ 表示用 $i$ 个鸡蛋测 $j$ 层高的楼的最少扔的次数。
首先,我们可以枚举一个 $k$,表示这次鸡蛋在第 $k$ 层扔。
那么就会有两种情况:

  1. 鸡蛋碎了,鸡蛋硬度在 $k$ 层以下,并且损失一个鸡蛋。所以 $f_{i, j} = 1 + f_{i - 1, k - 1}$。
  2. 鸡蛋没碎,鸡蛋硬度在 $k$ 层以上,并且没有损失鸡蛋。所以 $f_{i, j} = 1 + f_{i, j - k}$。
  3. 由于是求最坏情况,所以要取两者的最大值。而又由于我们可以决定在哪一层扔鸡蛋,所以我们在所有的 $k$ 中取最小值。 于是式子就是这样:
    $$f_{i, j} = \min\limits_{i = 1}^j\max\left{f_{i - 1, k - 1}, f_{i,
    j - k}\right}$$

然后我们发现复杂度有点高,尝试优化。
其实我们发现,随着 $k$ 的增加,$f_{i - 1, k - 1}$ 单调不减,$f_{i, j - k}$ 单调不增。所以 $\max\left\{f_{i - 1, k - 1}, f_{i, j - k}\right\}$ 的最小值在两函数交点处。所以我们可以二分求出这个交点。
此时复杂度降至 $\mathcal O\left(MN \log n\right)$

/*
 * Please submit with C++14! It's best to use C++20 or higher version.
 * By rbtree (https://rbtr.ee)
 * Apparition (n@rbtr.ee)
 * DO OR DIE
 */

#include <cmath>
#include <cstdio>
#include <cstring>
#define AS 3 +

using namespace std;
using tp = long long;

constexpr tp Hat_M = 30, Hat_N = 1e5;

tp f[AS Hat_M][AS Hat_N];

signed main() {
  tp m, n;
  scanf("%lld%lld", &m, &n);
  memset(f, 0x3f, sizeof f);
  for (tp i = 0; i < Hat_N; ++i) f[1][i] = i;
  for (tp i = 0; i < Hat_M; ++i) f[i][0] = 0;
  for (tp i = 0; i < Hat_M; ++i) f[i][1] = 1;
  for (tp i = 2; i <= m; ++i) {
    for (tp j = 2; j <= n; ++j) {
      tp l = 1, r = j;
      while (l <= r) {
        tp mid = l + r >> 1, a = f[i - 1][mid - 1], b = f[i][j - mid];
        if (a > b) r = mid - 1;
        else l = mid + 1;
      }
      f[i][j] = min(f[i][j], max(f[i - 1][r - 1], f[i][j - r]) + 1);
    }
  }
  printf("%lld\n", f[m][n]);
  return 0;
}

//*/

推通项解法

我们先求出 $M = 2$ 时的通解,再求出 $M = 3$ 时的通解,先找找规律。

MN结果
211
210014
210000141
210000001414
210000000014142

发现了吗?$f_{2, n}$ 居然等于 $\sqrt{2 \cdot n}$!接下来我们求 $M = 3$ 时的通解。

MN结果
3100019
31000000182
310000000001818

这次的规律没那么明显了,肉眼不可见。于是我就到 wolframalpha 上查了一下,$\sqrt[3]6 \approx 1.8171205928321396588$,与上面的表这个十分接近,但又不完全一致。所以这时可以发现
,其实在 $M = 2$ 时 $f_{2, n}$ 可能也只是接近 $\sqrt{2 \times n}$。

所以 $M = 3$ 时,$f_{3, n}$ 近似等于 $\sqrt[3]{6 \cdot n}$

目前肉眼看不出什么规律来。所以再求 $M = 4$ 时的通解。

MN结果
31000023
3100000000222
310000000000002214
31000000000000000022135

这下完了,wolframalpha 上也查不到关于 2.2135 的信息。但是我突然发现,$M = 2$ 时这个常数是开 $2$ 次根,$M = 3$ 时这个常数是开 $3$ 次根,那 $M = 4$ 时是不是要开 $4$ 次根了?所以把 2.2135 四次方,得到 $24.00590622$,非常接近 $24$。
所以现在 $M = 4$ 时的解也求出来了:$f_{4, n}$ 近似等于 $\sqrt[4]{24 \cdot n}$。

这下可以看出规律了吧。这个常数等于 $\sqrt[M]{M!}$。

所以 $f_{m, n}$ 近似等于 $\sqrt[M]{NM!}$。

用这个公式验证了几个 $M$ 较大的情况,发现确实很接近,但还是有一些误差。

动脑子推通项解法

怎么个丢法是最优的呢?考虑 $2$ 个蛋的情况下,扔 $x$ 次最多能检测多少层楼。
第一次扔的时候:
如果碎了,那么接下来就要一层一层试,要扔 $x - 1$ 次
如果没碎,就变成了次数为 $x - 1$ 的子问题了,此时再扔的楼层数变成了 $2x - 1$,在这种情况下碎和不碎两种情况下需要再扔的次数是相等的,已经是最好的扔法了,继续,可以得到,扔 $x$ 次时,最高可以检测到的楼层数为:
$$\sum\limits_{i = 1}^x i = \frac{x(1 + x)}2$$
那如果要检测 $100$ 层楼,又 $\frac{x(1 + x)}2 \geq 100$,解得 $x = 14$,是对的。
所以解得,两个蛋,$k$ 层楼时,最优的丢鸡蛋次数是
$$x = \left \lceil \frac{\sqrt{8k + 1} - 1}2 \right \rceil$$

接下来考虑 $3$ 个蛋的情况,同样的方法,发现扔 $x$ 次时,最高可以检测到的楼层数为:
$$\frac{x^3 + 5x}6$$
所以解得,三个蛋,$k$ 层楼时,最优的丢鸡蛋次数是
$$\large x = \left \lceil \frac{\sqrt[3]{\sqrt3\sqrt{243k^2+125}+27k}}{3^{\frac23}} - \dfrac5{\sqrt[3]3\sqrt[3]{\sqrt3\sqrt{243k^2+125}+27k}} \right \rceil$$
(放心,没写错)

接下来考虑 $4$ 个蛋的情况,用同样的方法可以推出。
为了方便接下来推式子,我们把“扔 $n$ 次时,最高可以检测到的楼层数”写成组合数的形式:
两个蛋:$\binom{n + 1}2$
三个蛋:$\binom n1 + \binom n2 + \binom n3$
四个蛋:$\binom n4 + \binom n2$

OEIS 上搜到的数列的解释是:由 $n - 1$ 个超平面形成的 $k$ 维空间中的区域数。
也就是说,有 n 层楼,k 个鸡蛋,答案将是 由 $n - 1$ 个超平面形成的 $k$ 维空间中的区域数。

形式化的,通解是($n$ 层楼,$k$ 个鸡蛋):

  1. 如果 $k \geq 5$,$x \geq \sum\limits_{i = 0}^n\sum\limits_{j = 0}^k\binom ij$
  2. 如果 $k = 2$,$x = \left \lceil \frac{\sqrt{8k + 1} - 1}2 \right \rceil$
  3. 如果 $k = 3$,$\large x = \left \lceil \frac{\sqrt[3]{\sqrt3\sqrt{243k^2+125}+27k}}{3^{\frac23}} - \dfrac5{\sqrt[3]3\sqrt[3]{\sqrt3\sqrt{243k^2+125}+27k}} \right \rceil$
  4. 如果 $k = 4$,$x \geq \sum\limits_{i = 0}^n\left(\binom i4 + \binom i2\right)$

4 条评论

  1. bykem · 2023-01-05 11:01

    tql

    1. yq 回复 bykem · 2023-03-03 20:26

      %%%%%%

  2. Orz012 · 2023-01-05 04:57

    tql

  3. Lightwhite · 2023-01-04 12:30

    tql

发表评论