2023阿里巴巴全球数学竞赛预选赛题/决赛部分题个人解 (三)

预选赛题 7.

这是最优停止问题，但是比赛的时候忙着赶论文，题都没看就润了。下面直接用动态规划来解决一般的 。

设  为正在考虑的候选者， 为其排名的随机变量， 为该候选者是否接受 offer 的随机变量。所有策略状态都可以用  表示，其中  为  的排名， 表示候选者是否接受 offer。

显然，若 ， 就不会被选为最优者，此时应该考虑 。设  是状态  下选到最优者的最大概率，则

其中  是状态  即为最优者的概率，显然当  时 ，否则 。当  时，问题的边界条件为当  时 ，否则 。

现在寻找  应当满足的递推关系（注意它和  无关）。

当  时，继续考虑第  个候选人所获得的概率比直接选择第  个候选人所获得的概率更大，此时最优策略应当为考虑第  个候选人，因此 。此时代入上式可得 ，代入递推式可得 。因此对第  个候选者而言，也应当继续考虑第  个候选人。

因此，最优策略满足如下条件：如果第  个候选人不会被选，则第  个候选者也不会被选；如果第  个候选人可以被考虑，那么第  个候选人也应当被考虑。

如果想在  状态选择第  个候选人，则 ，因此

其中  为使得  的最小  值。现在代入边界条件，就得到

综上所述，我们只需要考虑状态 ，此时选择第  个候选人当且仅当 。设  是第一个满足上述条件的 ，则最优策略即为从第  个候选人开始考虑发 offer，选择第一个  的候选人。

下面求出 。这也即寻找

由  不等式，

另一方面，

故

因此

故

两侧同取极限得

当  时，上述极限即趋于 。

决赛我选的主分析副应用与计算。现在看来选得还行。

分析题 1. 数列  满足

证明：对任意正整数  都有 。

没什么想法，就硬估计的。自然会想到利用归纳法，

再用  问题放缩。不过从  开始不太行，计算到  之后就可以了：

分析题 2. 设  是平面闭区域  上由连续函数构成的  维线性空间，证明：存在函数  使得

取  范数下的标准正交基 。则对任意 ，有 。

先考虑让 ，不难知道 ，故 。

另一方面，由于 ，则由积分中值定理可知存在  使得 。此时由  不等式可知 ，且等号显然可以取到。此时的  即满足题目条件。

总感觉以前做过这题，但是翻了翻还存着的 TD 没找着。