1981-2018年全国高中数学联赛真题分类汇编含解析 16组合与构造
2017A三、（本题满分50分）将33?33方格纸中每个小方格染三种颜色之一，使得每种颜色的小方格的个数相等。若相邻两个小方格的颜色不同，则称他们的公共边为“分割边”。试求分割边条数的最小值。
★解析：记分割边的条数为L.首先，将方格纸按如图所示分成三 个区域，分别染成三种颜色，粗线上均为分割边，此时共有56条 分割边，即L?56。 下面证明L?56.
将方格纸的行从上至下依次记为A1,A2,?,A33,列从左至右依次记为
B1,B2,?,B33,行Ai中方格出现的颜色数记为n?Ai?，
列Bi中方格出现的颜色数记为n?Bi?，三种颜色分别记为c1，c2，c3， 对于一种颜色cj，设n?ci?是表示含有cj色方格的函数与列数之和.
Ai中含有cj色方格Bi中含有cj色方格?1，?1，记??Ai,cj???，同理定义??Bi,cj???，
A中不含c色方格B中不含c色方格0，0，ijij??则
??n?A??n?B????????A,c????B,c????????A,c????B,c????n?c?①
iiijijijijji?1i?1j?1j?1i?1j?1333333333由于染cj色的方格有?33?363个，设含有cj色方格的行有a个，列有b个，则cj色方格一定在这a行和b列的交叉方格中，因此ab?363.从而n?ci??a?b?2ab?2363?38 即n?ci??39.j?1,2,3,?②
由于在行Ai中有n?Ai?种颜色的方格，因此至少有n?Ai??1条分割边，同理在行Bi中有n?Bi?种颜色的方格，因此至少有n?Bi??1条分割边，于是，
132L???n?Ai??1????n?Bi??1????n?Ai??n?Bi???66??n?cj??66③
i?1i?1i?1j?13333333下面分两种情形讨论.
⑴当有一行或有一列全部方格同色时，不妨设有一行全为c1色，从而方格纸的33列中均含有c1的方
格，由于c1的方格有363个，故至少有11行中含有c1色方格。于是n?c1??11?33?44。④ 由①③④得L?n?c1??n?c2??n?c3??66?44?39?39?66?56
⑵没有一行或没有一列全部方格同色时，则对任意1?i?33，均有n?Ai??2，n?Bi??2，从而由②知，L???n?A??n?B???66?33?4?66?56
iii?133综上可知，分割边条数的最小值为56。
2017A四、（本题满分50分）。设m,n均是大于1的整数，m?n，a1,a2,?,an是n个不超过m的互不相同的正整数，且a1,a2,?,an互素。证明：对任意实数x，均存在一个i（1?i?n），使得
aix?2x，这里y表示实数y到它最近的整数的距离。
m(m?1)★证明：首先证明两个引理：
引理1：存在整数c1,c2,?,cn，满足c1a1?c2a2???cnan?1，并且ci?m，1?i?n. 由于a1,a2,?,an互素，即?a1,a2,?,an??1，有裴蜀定理，存在整数c1,c2,?,cn，满足
c1a1?c2a2???cnan?1。①
下面证明，通过调整，存在一组c1,c2,?,cn满足①，且ci?m，记S1?c1,c2,?,cn??ci?m?ci?0，
S1?c1,c2,?,cn??cj??m?cj?0。
如果S1?0，那么存在ci?m?1，于是aici?1，又a1,a2,?,an是大于1的整数，故由①可知，
///存在cj?0，令ci?ci?aj，cj?cj?ai，ck?ck（1?k?n，k?i,j），则 //c1/a1?c2a2???cnan?1，② 并且0?m?aj?ci/?ci，cj?c/j?ak?m， 、、/、、/所以S1c1,c2,?,cn?S1?c1,c2,?,cn?，S2c1,c2,?,cn?S2?c1,c2,?,cn?
????/ck/?ck（1?k?n，如果S2?0，则存在cj??m，因此有一个ci?0.令ci?ci?aj，c/j?cj?ai，
k?i,j），那么②成立，并且?m?ci/?ci,cj?c/j?0，与上面类似可以证明到：
、、/、、/S1c1,c2,?,cn?S1?c1,c2,?,cn?，S2c1,c2,?,cn?S2?c1,c2,?,cn?，即说明S1与S2均是非
????负整数，故通过有限次上述的调整，可以得到一组使得①成立，并且S1?S2?0结论获证。 引理2：①对任意的实数a,b，均有a?b?a?b；②对任意整数u和实数v，有uv?u?v；
由于对任意整数u和实数x，均有u?x?x，于是不妨设a,b????11?,?，此时a?a，b?b，?22?若ab?0，不妨设a?0?b，则a?b????11?,?，从而a?b?a?b?a?b?a?b 22??若ab?0，不妨设a,b同号，则当a?b?1?11?时，有a?b???,?， 2?22?11时，注意到总有a?b?，故
22此时a?b?a?b?a?b?a?b；当a?b?a?b?1?a?b?a?b；故①得证； 2又?y?y，由①知，②是成立的。
接下来回到原题，由结论①存在整数c1,c2,?,cn，满足c1a1?c2a2???cnan?1，并且ci?m，
1?i?n.于是，?ciaix?x，由引理2得x?i?1n?cax??ciii?1i?1nniaix?m?aix，
i?1n因此，maxaix?1?i?n1x③ mn若n?若n?2x1m?1x?，则由③知，maxaix?
1?i?nmnm?m?1?2m?1，则在a1,a2,?,an中存在两个相邻的正整数。不妨设a1,a2相邻，则2x2?2xm?m?1?。
x?a2x?a1x?a2x?a1x，故a2x与a1x中有一个不小于
综上，总存在存在一个i（1?i?n），使得aix?2x
m(m?1)
1981-2018年全国高中数学联赛真题分类汇编含解析答案16组合与构造
