CMO 2023 Day1T1

\(n=2^{2024}\) 时最优方案为 \(2,2,\cdots ,4\) 此时 \(\lambda_0=\frac{1}{1012}\) 则 \(\lambda_{\min}\geq \lambda_0\)。对于 \(\lambda =\frac{1}{1012}\) 构造，令 \(n=\prod p_i\)，\(p_i=n^{a_i}\) 其中 \(p\) 均为素数。那么问题转化为：

\(\sum a_i=1\)，其中 \(a>\frac{1}{1012}\) 的要单独分组 \(a\leq \frac{1}{1012}\) 可以若干个分一组，但是要满足一组内的 \(\sum a\leq \frac{1}{1012}\)。

充分性给出贪心构造策略：若存在 \(a_x+a_y\leq \frac{1}{1012}\) 那么将 \(x\) 组和 \(y\) 组合并成一个新的组，其大小为 \(a'=a_x+a_y\)，若有多个合法的任选两个进行合并，直到不能合并为止，此时一定有组数 \(m\leq 2023\)，即得到一个合法方案。

证明：若 \(m\geq 2024\)，此时考虑 \(a_1\leq a_2\leq a_3\leq\cdots\leq a_m\)，其中 \(a_1+a_2>\frac{1}{1012}\)，那么一定有 \(a_2>\frac{1}{2024}\)，则 \(a_3,a_4,\cdots,a_m\) 均 \(>\frac{1}{2024}\) ，那么

与 \(\sum a=1\) 的条件不符，故 \(m\leq 2023\)。