$n$ 项正整数列 $x_1,x_2,\cdots ,x_n$ 的各项之和为 $2009$，如果这 $n$ 个数既可分为和相等的 $41$ 个组，又可分为和相等的 $49$ 个组，求 $n$ 的最小值．
【难度】
【出处】
2009年全国高中数学联赛江西省预赛
【标注】
【答案】
略
【解析】
设分成的 $41$ 个组为 $a_1,
A_2,\cdots ,A_{41}$，每组中的各数和皆为 $49$，称这种组为 $A$ 类组；而分成的 $49$ 个组为 $B_1,B_2,\cdots ,B_{49}$，每组中的各数和皆为 $41$，称这种组为 $B$ 类组．
显然，每个项 $x_k$ 恰好属于同一个 $A$ 类组和一个 $B$ 类组，即同类组之间没有公共项．
如果两个组 $A_i,B_j$ 中有两个公共项 $x_r,x_t$，则可以将这两个数合并为一个项 $x_r+x_t$，这样可使 $n$ 值减少，故不妨设每对 $A_i,B_i$ 至多有一个公共项．
今用点 $u_1,u_2,\cdots ,u_{41}$ 分别表示 $A_1,A_2,\cdots ,A_{41}$，而点 $v_1,v_2,\cdots ,v_{49}$ 表示组 $B_1,B_2,\cdots ,B_{49}$．如果组 $A_i,B_i$ 有公共项，则在相应的点 $u_i,v_j$ 之间连一条边，于是得到二部图 $G$，它恰有 $n$ 条边和 $90$ 个顶点．
下面证明 $G$ 是连通图．
如果图 $G$ 的最大连通分支为 $G'$，其顶点数少于 $90$．设在分支 $G'$ 中，有 $a$ 个 $A$ 类顶点 $u_{k_1},u_{k_2},\cdots ,u_{k_a}$ 和 $b$ 个 $B$ 类顶点 $v_{s_1},v_{s_2},\cdots ,v_{s_b}$，其中$$a+b<90,$$则在相应的 $A$ 类组 $A_{k_1},A_{k_2},\cdots ,A_{k_a}$ 和 $B$ 类组 $B_{s_1},B_{s_2},\cdots ,B_{s_b}$ 中，$A$ 类组 $A_{k_i}$ 中的每个数 $x_j$ 都要在某个 $B$ 类组 $B_{s_j}$ 中出现；而 $B$ 类组 $B_{s_i}$ 中的每个数 $x_j$ 也都要在某个 $A$ 类组 $A_{r_j}$ 中出现（否则将有边与分支外的顶点连结，发生矛盾），因此 $a$ 个 $A$ 类组 $A_{k_1},A_{k_2},\cdots ,A_{k_a}$ 中各数的和应等于 $b$ 个 $B$ 类组 $B_{s_1},B_{s_2},\cdots ,B_{s_b}$ 中各数的和，即有$$49a=41b,$$由此得$$41|a , 49|b,$$所以$$a+b\geqslant 41+49=90,$$矛盾．
因此 $G$ 是连通图，于是图 $G$ 至少有 $90-1=89$ 条边，即 $n\geqslant 89$．
另一方面，我们可实际构造一个具有 $89$ 项的数列 $x_1,x_2,\cdots ,x_{89}$，满足本题条件．
例如，取$$\begin{split}&x_1=\cdots =x_{41}=41,\\&x_{42}=\cdots =x_{75}=8,\\&x_{76}=\cdots =x_{79}=7,\\&x_{80}=\cdots =x_{83}=1,\\&x_{84}=x_{85}=6,\\&x_{86}=x_{87}=2,\\&x_{88}=5,x_{89}=3,\end{split}$$于是，每个 $A$ 类组可由一个 $41$，一个 $8$，或者由一个 $41$，添加一对和为 $8$ 的项组成，这样共得 $41$ 个 $A$ 类组，每组各数的和皆为 $49$．
为了获得和为 $41$ 的 $49$ 个 $B$ 类组，可使 $x_1,x_2,\cdots ,x_{41}$ 各成一组，其余的数可以拼成八个 $B$ 类组：$\{8,8,8,8,8,1\}$ 的组四个，$\{8,8,8,8,7,2\}$ 的组两个，$\{8,8,8,8,6,3\}$ 的组一个，$\{8,8,7,7,6,5\}$ 的组一个，故 $n$ 的最小值为 $89$．
A_2,\cdots ,A_{41}$，每组中的各数和皆为 $49$，称这种组为 $A$ 类组；而分成的 $49$ 个组为 $B_1,B_2,\cdots ,B_{49}$，每组中的各数和皆为 $41$，称这种组为 $B$ 类组．
显然，每个项 $x_k$ 恰好属于同一个 $A$ 类组和一个 $B$ 类组，即同类组之间没有公共项．
如果两个组 $A_i,B_j$ 中有两个公共项 $x_r,x_t$，则可以将这两个数合并为一个项 $x_r+x_t$，这样可使 $n$ 值减少，故不妨设每对 $A_i,B_i$ 至多有一个公共项．
今用点 $u_1,u_2,\cdots ,u_{41}$ 分别表示 $A_1,A_2,\cdots ,A_{41}$，而点 $v_1,v_2,\cdots ,v_{49}$ 表示组 $B_1,B_2,\cdots ,B_{49}$．如果组 $A_i,B_i$ 有公共项，则在相应的点 $u_i,v_j$ 之间连一条边，于是得到二部图 $G$，它恰有 $n$ 条边和 $90$ 个顶点．
下面证明 $G$ 是连通图．
如果图 $G$ 的最大连通分支为 $G'$，其顶点数少于 $90$．设在分支 $G'$ 中，有 $a$ 个 $A$ 类顶点 $u_{k_1},u_{k_2},\cdots ,u_{k_a}$ 和 $b$ 个 $B$ 类顶点 $v_{s_1},v_{s_2},\cdots ,v_{s_b}$，其中$$a+b<90,$$则在相应的 $A$ 类组 $A_{k_1},A_{k_2},\cdots ,A_{k_a}$ 和 $B$ 类组 $B_{s_1},B_{s_2},\cdots ,B_{s_b}$ 中，$A$ 类组 $A_{k_i}$ 中的每个数 $x_j$ 都要在某个 $B$ 类组 $B_{s_j}$ 中出现；而 $B$ 类组 $B_{s_i}$ 中的每个数 $x_j$ 也都要在某个 $A$ 类组 $A_{r_j}$ 中出现（否则将有边与分支外的顶点连结，发生矛盾），因此 $a$ 个 $A$ 类组 $A_{k_1},A_{k_2},\cdots ,A_{k_a}$ 中各数的和应等于 $b$ 个 $B$ 类组 $B_{s_1},B_{s_2},\cdots ,B_{s_b}$ 中各数的和，即有$$49a=41b,$$由此得$$41|a , 49|b,$$所以$$a+b\geqslant 41+49=90,$$矛盾．
因此 $G$ 是连通图，于是图 $G$ 至少有 $90-1=89$ 条边，即 $n\geqslant 89$．
另一方面，我们可实际构造一个具有 $89$ 项的数列 $x_1,x_2,\cdots ,x_{89}$，满足本题条件．
例如，取$$\begin{split}&x_1=\cdots =x_{41}=41,\\&x_{42}=\cdots =x_{75}=8,\\&x_{76}=\cdots =x_{79}=7,\\&x_{80}=\cdots =x_{83}=1,\\&x_{84}=x_{85}=6,\\&x_{86}=x_{87}=2,\\&x_{88}=5,x_{89}=3,\end{split}$$于是，每个 $A$ 类组可由一个 $41$，一个 $8$，或者由一个 $41$，添加一对和为 $8$ 的项组成，这样共得 $41$ 个 $A$ 类组，每组各数的和皆为 $49$．
为了获得和为 $41$ 的 $49$ 个 $B$ 类组，可使 $x_1,x_2,\cdots ,x_{41}$ 各成一组，其余的数可以拼成八个 $B$ 类组：$\{8,8,8,8,8,1\}$ 的组四个，$\{8,8,8,8,7,2\}$ 的组两个，$\{8,8,8,8,6,3\}$ 的组一个，$\{8,8,7,7,6,5\}$ 的组一个，故 $n$ 的最小值为 $89$．
答案
解析
备注
