在一个类似 2022×2022 的花园的每个方格中,最初都有一个高度为 0…
- User
在一个类似 2022×2022 的花园的每个方格中,最初都有一个高度为 0 的树,园丁和伐木工交替进行以下游戏,园丁首先开始:园丁选择花园中的一个方格,该方格上的每棵树以及周围至多八个方格中的所有树都会增长一单位,伐木工随后选择板上的四个不同方格,这些方格上正高的树都会减少一单位,称一棵树为雄伟的,如果其高度至少为 10 的六次方。确定园丁能够确保板上最终有 K 棵雄伟的树,无论伐木工如何操作,求最大的 K.
- Assistant
设花园是 2022×2022 的棋盘,所有树的初始高度均为 0
每一“回合”包括一次园丁行动和一次伐木工行动。
记
• H = 10⁶(雄伟的高度阈值)
• t 表示已经进行的回合数。————————
一、园丁一定能得到 5 棵雄伟树(下界)
————————
园丁始终选同一个格子 P。
这样每回合都有完全相同的 3×3 方阵 B 被全部 +1,B 中共 9 棵树。
第 t 回合结束后
– B 里的每棵树被加了 t 次;
– 伐木工一共只能砍 4t 次。若伐木工想让 B 中的一棵树的净高度 < t,
就得把那棵树砍至少 t 次。
4t 次砍伐最多只能“压住” 4 棵树
(4 棵×t 次 = 4t 次),
因此至少还有 9–4 = 5 棵树没有被“压住”,
它们的净高度恰为 t。当 t = H = 10⁶ 时,这 5 棵树的高度 ≥ H,皆成雄伟树。
所以园丁保证能得到 ≥5 棵雄伟树。————————
二、伐木工能够把雄伟树的数目永远限制在 5 棵(上界)
————————
记某棵树被加的总次数为 g(v),被砍的总次数为 c(v),
其当前高度为 h(v)=g(v)−c(v)。若 h(v) ≥ H,则必须有
c(v) ≤ g(v)−H+1 (1)伐木工的策略:
“始终砍当前高度最大的 4 棵树”。
下面证明:无论园丁怎样走,该策略都能确保雄伟树不超过 5 棵。- 计数思想
把所有格子按 g(v) 从大到小排序,记第 i 大为 v_i。
性质:对任何整数 k ≥ 0,同一时刻能满足 g(v) ≥ H+k 的格子数 ≤ 9。
原因:一个格子要想被加到 H+k,至少得被加 H+k 次;
而每回合只有 9 次加法,所以在前 H+k 回合里最多只有 9(H+k) 次加法,
能让 ≥ H+k 的格子数不超过 9。- 需要的“压制”次数
对 i ≥ 6(第 6 高以后)的格子,若要把它压到 < H,
至少要再砍 g(v_i)−(H−1) 次。
于是第 6 高及以后全部需要的砍伐总数为
Σ_{i ≥ 6} max(0, g(v_i) − (H−1))
= Σ_{k=0}^{T−H} (第 6 高及以后满足 g ≥ H+k 的格子数)
≤ Σ_{k=0}^{T−H} 4 (因为每一层至多 9 格,其中 5 可保留)
= 4(T−H+1) ≤ 4T (2)- 可行性
到第 T 回合伐木工一共正好拥有 4T 次砍伐,
式 (2) 说明用不超过 4T 次就能把排名第 6 及之后的树全部压到 < H。
因此无论园丁怎样加,伐木工总能确保“一次性”或“分批次”
把 6 号、7 号、… 的树压到阈值以下。
于是同时达到或超过 H 的树永远不超过 5 棵。
————————
三、结论
园丁无论如何都只能保证最终有 5 棵雄伟的树,而且 5 棵一定能保证。
故所求最大值K_max = 5 ✅
- 计数思想
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.