题目 求具有下述性质的最小正整数$k$：若将$1,2,\cdots,k$中的每个数任意染为红色或者蓝色, 则或者存在$9$个不同的红色的数$x_1,x_2,\cdots,x_9$满足$x_1+x_2+\cdots+x_8 < x_9,$ 或者存在$10$个互不相同的蓝色的数$y_1,y_2,\cdots,y_{10}$满足$y_1+y_2+\cdots+y_9 < y_{10}.$
解析 先想个容易想到的构造, 将$1,2,\cdots,45$染为蓝色, $46,47,\cdots,396$染为红色, 不符合题目要求, 因此$k_{\min}\geq397.$
因此我们待定$k_{\min}=a\geq397.$ 尝试证明$k=a$时, 对于任何染色都能找到满足题意的$\{x_i\}$或$\{y_i\}.$ 用反证法, 假设不成立, 则存在染色, $S$是$1,2,\cdots,k$中所有蓝色数, $T$为所有红色数, 依照反证假设, 则$S$中最小$9$元大于等于$S$的最大元, $T$中最小$8$元大于等于$T$的最大元, 若$|S|\leq 10,$ 则$T$中最大元$\geq a-10,$ $T$中最小$8$元均$\leq 18,$ 则有$18\times 8\geq a-10,$ 显然矛盾, 同理$|T|\leq 9$时可推出矛盾. 因此我们可以要求$|S|\geq 11,$ $|T|\geq10.$ 设$S$中最小$9$元为$z_1,z_2,\cdots,z_9,$ $T$中最小$8$元为$w_1,w_2,\cdots,w_8.$ 显然有$z_9\geq9,$ $w_8\geq8.$ 分两种情形讨论.
$1^{\circ}$ $a\in T,$ 若$z_9\geq17,$ 则$|\{1,2,\cdots,17\}\cap S|\leq 9,$ 则$|\{1,2,\cdots,17\}\cap T|\geq8,$ 则$w_1,w_2,\cdots,w_8$均小于$17.$ 这显然与$w_1+w_2+\cdots+w_8\geq a$矛盾. 故$z_9\leq 16,$ 此时, \begin{align*}
\{1,2,\cdots,z_9\}=\{z_1,z_2,\cdots,z_9\}\cup\{w_1,w_2,\cdots,w_{z_9-9}\}
\end{align*}
而对于$i\in[z_9-8,8],$ 有$
w_i\leq \max S+(i-z_9+9)
$
因此
\begin{align*}
a+\max S\leq& z_1+z_2+\cdots+z_9+w_1+w_2+\cdots+w_8\\= &1+2+\cdots+z_9+w_{z_9-8}+w_{z_9-7}+\cdots+w_{8}\\\leq&\dfrac{z_9(z_9+1)}{2}+(17-z_9)\max S+\dfrac{(17-z_9)(18-z_9)}{2}.
\end{align*}
因此
\begin{align*}
a\leq&\dfrac{z_9(z_9+1)}{2}+(16-z_9)\max S+\dfrac{(17-z_9)(18-z_9)}{2}\\\leq&\dfrac{z_9(z_9+1)}{2}+(16-z_9)(z_1+z_2+\cdots+z_9)+\dfrac{(17-z_9)(18-z_9)}{2}\\\leq&\dfrac{z_9(z_9+1)}{2}+(16-z_9)(9z_9-36)+\dfrac{(17-z_9)(18-z_9)}{2}=-8z_9^2+163z_9-423.
\end{align*}
对于最后的二次函数, $z_9=10$是距离对称轴最近的整数, 故此时取最大值$407.$ 希望这里能推出矛盾, 故$a\geq408.$
$2^{\circ}$ $a\in S,$ 若$w_8\geq17,$ 则$|\{1,2,\cdots,17\}\cap T|\leq 8,$ 则$|\{1,2,\cdots,17\}\cap S|\geq9,$ 则$z_1,z_2,\cdots,z_9$均小于$17.$ 这显然与$z_1+z_2+\cdots+z_9\geq a$矛盾. 故$w_8\leq 16,$ 此时, \begin{align*}
\{1,2,\cdots,w_8\}=\{w_1,w_2,\cdots,w_8\}\cup\{z_1,z_2,\cdots,z_{w_8-8}\}
\end{align*}
而对于$i\in[w_8-7,9],$ 有$
z_i\leq \max T+(i-w_8+8)
$
因此
\begin{align*}
a+\max T\leq& z_1+z_2+\cdots+z_9+w_1+w_2+\cdots+w_8\\= &1+2+\cdots+w_8+z_{w_8-7}+z_{w_8-6}+\cdots+z_{9}\\\leq&\dfrac{w_8(w_8+1)}{2}+(17-w_8)\max T+\dfrac{(17-w_8)(18-w_8)}{2}.
\end{align*}
因此
\begin{align*}
a\leq&\dfrac{w_8(w_8+1)}{2}+(16-w_8)\max S+\dfrac{(17-w_8)(18-w_8)}{2}\\\leq&\dfrac{w_8(w_8+1)}{2}+(16-w_8)(w_1+w_2+\cdots+w_8)+\dfrac{(17-w_8)(18-w_8)}{2}\\\leq&\dfrac{w_8(w_8+1)}{2}+(16-w_8)(8w_8-28)+\dfrac{(17-w_8)(18-w_8)}{2}=-7w_8^2+139w_8-295.
\end{align*}
对于最后的二次函数, $w_8=10$是距离对称轴最近的整数, 故此时取最大值$395,$ 此时矛盾.
因此取$a=408$可以使得上面的证明成立. 因此我们希望给出$k=407$时不合题意的构造. 在证明中我们
得到此时应有$a\in T,$ $z_9=10,$ $\max S=9z_9-36=54,$ $w_2=55,$ $w_3=56,$ $\cdots,$ $w_8=61.$ 进而可以容易地得到构造.
即将$1,55,56,57,\cdots,407$染为红色, $2,3,4,\cdots,54$染为蓝色, 则蓝色数中最小的$9$个$2+3+\cdots+10=54,$ 红色数中最小的$8$个$1+55+56+\cdots+61=407.$ 故$k=407$不符合题意. $k\leq 407$依然按照此法染色, 知亦不符合题意.
因此可以容易地完成本题的解答. $k$的最小值为$408.$