题目：
求具有下述性质的最小正整数 \(k\)：
若将 \(1,2,\cdots,k\) 中的每个数任意染成红色或蓝色，记红色的数从小到大依次为 \(a_1,a_2,\cdots,a_n\)，蓝色的数从小到大依次为 \(b_1,b_2,\cdots,b_m\)，下述两个条件至少满足一个：
- 存在九个互不相同的数 \(i_1,i_2,\cdots,i_9\)，满足 \(a_{i_1} + a_{i_2} + \cdots + a_{i_8} < a_{i_9}\)。
- 存在十个互不相同的数 \(i_1,i_2,\cdots,i_9\)，满足 \(b_{i_1} + b_{i_2} + \cdots + b_{i_9} < b_{i_{10}}\)。
我的解答：
设红色的数集合为 \(R\)，蓝色的数集合为 \(B\)，\(s_R = \sum_{j = 1}^8 a_j\)，\(s_B = \sum_{j=1}^9b_j\)，原限制等价于或者 \(s_R < a_n\)，或者 \(s_B < b_m\)。
考虑合法的 \(k\) 组成的集合的补集，则题目所求为补集最大元素加一，限制转化为存在一种染色方案，使得 \(s_R \le a_n\) 且 \(s_B \le b_m\)。
不妨设 \(b_9 < a_8\)，则只需求
\[\max_{b_m \le s_B 且 a_n \le s_R} \{b_m,a_n\} = \max_{b_m \le s_B} \{b_m, \max \{s_R\} \} \]不妨设 \(B\) 已满足 \(b_m \le s_B\)，则 \(\forall j \in [b_9 + 1, b_m - 1] \cap \mathbf{N^*}\)，若 \(j \in B\)，则 \(B\) 依然满足条件。
考虑下述染色方法：将 \([b_9 + 1, s_B]\) 中的所有数染成蓝色，然后将最小的 \(8\) 个数未被染色的数染成红色，最后将 \([a_8 + 1, s_R]\) 中的所有数染成红色。显然这样的染色使 \(b_m\) 取到了上界 \(s_B\)。
假设 \([1, b_9]\) 中有 \(l\) 个数被染成红色，则 \(a_{l+1} + a_{l+2} + \cdots + a_{8} \le (b_m + 1) + (b_{m} + 2) + \cdots + b_{m} + (8 - l)\)。故上述染色方法使 \(s_R\) 取到了上界。
设 \(b_8 = x, s_B = y\)，则上式化为
\[\max \{ s_B, \frac{x(x + 1)}2 - y + (17-x)y + \frac{(17-x)(18-x)}{2}\} \]其中 \(45 \le y \le 9x - 36, 9 \le x \le 16\)。
求最大值即可，对于 \(b_9 > a_8\)，同理，最终最大值为 \(407\)，故答案为 \(407 + 1 = 408\)。
标签：le,max,染色,染成,oier,cdots,红色,2023,高联 From： https://www.cnblogs.com/DCH233/p/17705985.html