(真题,难)每日一题 - 5 哈基米的最大期望 你老板家里有一群哈基米和叮咚鸡。…
- User
(真题,难)每日一题 - 5 哈基米的最大期望
你老板家里有一群哈基米和叮咚鸡。
每时刻「随机」有「一只」哈基米或叮咚鸡发出叫声,如果哈基米叫,就有一只叮咚鸡变成哈基米,反之亦然。在任意时刻(包括初始状态)他可将任意数量的叮咚鸡赶出家门。
为了最终家里有尽可能多的哈基米,他应该用什么样的策略赶走叮咚鸡?
提示与说明:
-
随机指的是所有的动物里面以等概率采样一只,每只动物叫的概率相同。
-
直接将所有叮咚鸡移除肯定不是最优,因为有可能有叮咚鸡变成哈基米。
-
存在最优策略。
-
考虑如何构造一个上鞅序列,上鞅指的是一个随机过程中下一时刻的期望值小于当前时刻的值。
-
Assistant
让我们一步步分析这个问题:
- 首先,让我们明确状态:
- 在任意时刻t,设有h(t)只哈基米,d(t)只叮咚鸡
- 总数n(t) = h(t) + d(t)
- 分析每一步的概率:
- 哈基米叫的概率:h(t)/n(t)
- 叮咚鸡叫的概率:d(t)/n(t)
- 分析期望变化:
- 如果哈基米叫(概率h/n),一只叮咚鸡变成哈基米,h增加1
- 如果叮咚鸡叫(概率d/n),一只哈基米变成叮咚鸡,h减少1
-
计算下一时刻哈基米数量的期望: E[h(t+1)] = h(t) + h(t)/n(t) × 1 + d(t)/n(t) × (-1) = h(t) + (h(t) - d(t))/n(t) = h(t) × (1 + 1/n(t)) - d(t)/n(t)
-
关键发现: 当h(t) > d(t)时,E[h(t+1)] > h(t) 当h(t) < d(t)时,E[h(t+1)] < h(t)
-
最优策略:
- 应该始终保持h(t) > d(t)的状态
- 具体来说,应该在每个时刻检查,如果d(t) ≥ h(t),就赶走足够多的叮咚鸡,使得剩余的叮咚鸡数量比哈基米少
- 最优策略具体实施:
- 如果当前d ≥ h,应该赶走d-h+1只叮咚鸡
- 这样可以保证剩余叮咚鸡数量比哈基米少1
- 之后的每个时刻都保持这个策略
这个策略是最优的,因为:
- 它保证了哈基米数量的期望是递增的
- 它在保持期望递增的同时,保留了尽可能多的叮咚鸡(给未来变成哈基米的机会)
- 它构造了一个上鞅序列,保证了最终哈基米数量的最大化
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.