2 中等数学
叙#活幼镙程鉼雇
初中数学竟赛中的组合最值仰题解法举例
钟志强
(四川省绵阳外国语学校,621000)中图分类号:〇157 文献标识码:A 文章编号:1005 - 6416(2020)06 - 0002 - 05
(本讲适合初中)
组合最值问题是指变量随组合结构的安
排方式不同而变化,适当安排这些对象可以
使某些结构取得最大值或最小值.这类问题
往往以整数、点、线、三角形、圆、集合等离散
对象为背景,与代数最值和几何最值(连
续变量最值问题)在思考方式上有很大的
不同.
组合最值问题处理三部曲:估计、证明、
构造,有时证明和构造可以合二为一.
(1 )估计:对变量的取值做出猜想估计,
猜想出最值的大概范围,估计出最大值或最
小值;(2) 证明;
(3) 构造:找到一种具体的安排方式,以
说明前面估计的最大值或最小值是能够达
到的.
即先找“界”(估计可能的最值),再通过
证明或构造说明等号能成立.
先举例说明解决该类问题的三个步骤.
例1已知〜<*2〈…<%7,且均为正整 数,h +a;2 +…+ :«7 = 158.求〜+a:2 +巧的最
大值.解估计A +心+ 6的最大值为60.
先证明:尤1 +巧+ %矣60.
假设h +*2 +*3多61.则
(«3 ~2)+ (x3 -1) + A:3 +X2 +X3 ^61
收稿日期:2020 - 05 - 06=> x3 ^22
=> x4 +x5 +x6 +x7
+1 + + 2 + 3 +4
= 4x3 + l〇5:4 x 22 + 10 =98
=> X{ + x2 + ''• + X-J=(a:! + x2 +^c3)+ (a:4 +ac5 + x6 +x-j)
彡61 +98 =159,
与已知等式矛盾.故〜备60,即々+ + ;t3的最大
值为60.
再构造说明60可以取到.
取丨1 = 19,丨2 = 20,丨3 = 21 ,丨4 = 22,
丨5 =23,丨6 =24,尤7 =29.
则;^ + ;*2 + 巧=60.
到底是只需构造一例还是需严格证明,
要看题目的描述.若题目要求是存在性的,则
构造一例即可;若题目要求是任意性的,则需
严格的证明,也需构造.
组合最值问题,在初中阶段大体有如下
一些处理方法,下面举例说明.
1构造抽屉
例2记正整数m的各位数字之和为
S(m),比如 S(2 017) = 2 +0 +1 + 7 = 10•现
从1,2,…,2 017这2 017个正整数中任意取
出n个不同的数,都能在这n个数中找到八
个不同的数%,a2,…,a8,使得
…= S(a8)
.2020年第6期3
则正整数n的最小值是( ).[U(A)185 (B)187 (C)189 (D)191
(2017,全国初中数学联赛四川赛区决
赛)解注意到,1,2,…,2 017这2 017个
正整数中,数字之和的最小值为1,最大值为 28.
易知,数字之和为1的有1、1〇、1〇〇、 1 _这四个数;数字之和为2,3,…,26的数
的个数均不少于八个;数字之和为27的仅有
999、1 899、1 989、1 998这四个数;数字之和
为28的仅有1 999这一个数.
故数字之和为2,3,…,26的各取七个,
其余数字之和的数全取,不满足条件.从而,ra彡4 + 7 x 25 + 4 + 1 +1 =185.
又由抽屉原理,知n = 185时,符合条件.
因此,正整数n的最小值是185,选(A).
2逐步调整
例3已知n个正整数〜,〜…八满足
〜+*2 +…+ ;»:„ = 2 020•求这re个正整数乘
积•••;»:„的最大值.
(根据2008年全国初中数学竞赛天津初
赛题改编)解设的最大值为M.
由题意,知M中的每一个1(七>1)(/ =
1,2,…,n),若其中有乂 5=4,可将;k;分成\ -
2和2两个数,考虑其乘积,有
(x{ - 2)x2 =xi + (xt -4)
于是,所有这样不小于4的正整数七
分成^-2和2两个数后,其和不变,但乘积
变大.从而,在M中不可能出现不小于4的正
整数.故乂 =2或3•这表明,M可写成2P x 39
的形式.又因为2+2+2=3 +3,但23 <32,艮P在
乘积中用两个3替代三个2,乘积更大,所以,/>矣2.又 2 020 =3 x672 +2 +2,贝IJ 心…、的
最大值为22x3672.
3极端原理
例4 (1)在4x4的方格表中,先把部
分格染成红色,然后划去2行和2列.若无论
怎么划,都至少有一个红色的小格没有被划
去,则至少要染多少个小格?证明你的结论.
(2)若把(1)中的“4 x4的方格表”改成
“ra xra(/i多5)的方格表”,其他条件不变,贝!J
至少要染多少个小格?证明你的结论.[2]
解设染m个红格.
(1)当m矣4时,一定能全划去.
当m=5时,由抽屉原理,知必有一行至
少有两个红格,则先划去这一行,剩下的红格
至多有三个,能被全划去.
当m =6时,由抽屉原理,知必有一行至
少有三个红格或至少有两行恰各有两个红
格.若有一行至少有三个红格,则先划去这一
行,剩下的红格至多有三个,必然能被全划
去;若至少有两行恰各有两个红格,则先划
去这两行,则剩下只有两个红格,也必能被全
划去.
当m =7时,如图1的染法符合条件.
故至少要染七个红格.
图1 图2(2)当m专4时,一定能被全划去,当
/I = 5时,构造如图2的染法符合条件.
故至少要染五个红格.4中等数学
4分类讨论
例5图3是由圆组成的一个五环,请
将数字1,2,…,9填入五环中的9个空白处, 使得每一个圆中所填的数的和都相等•求这
个相等的和的最大值和最小值.[3]
解设图3中的数字和为则 5S = (a + b)+(b+c + d) +
(d + e +f) + (f+g +h) + (h +i)
= (a+b+c + d + e +f + g + h + i) +
(b+d+f+h)
=(1 +2 + •■■ +9)+ (b +d +f +h)
=45 + (b + d +f + h).
于是,6+d+/+/i能被5整除.
而6+(/+/+/i的最大值为6 +7 +8 +9
=30,最小值为 1 +2 +3 +4 =10,故 6 +/ + /i
的值可能为1〇、15、20、25、30.(\)^ b+d+f+h =30 0t,S = 15,gp
b + d +f + h =6 +1 + 8 + 9,
此时,包括9的圆环至少有一个圆环内数字
和超过15,故S = 15不合题意.
(2)当 6+(/+/+& =25 时,S = 14,此时, b+d+f+h=S+l+ 6+ 4
=9+ 7+ 5+ 4= 9+ 7+ 6+ 3
=9 +8 +6 +2,
如图4,存在一种填法,使得
b + d +f +h =9 +1 + 6+3.故S的最大值为14.
(3)当6+4+/ + /1=1+2+3+4 = 10时,
S = 11,此时,存在一种填法如图5.
5不等式控制
例6如图6,将1,2,…,10这十个数分
别填入图6的十个圆圈内,
使任意连续相邻的五个圆
圈内的数的和均不大于某
一个整数M.求M的最小
值并完成你的填图.[4] 图6
解设满足已知条件的数依次为:%,
a2,”.,ai。.则ax + a2 + a3 + a4 + a5
0,2 + ^3 + ^4 ^5 + ^ Af ,
炫10 +汉1 +炫2 ++炫4故 5 ( + a2 + …+ 〇丨。)< 10M
5 xlO xll 2^10M
=> M^27. 5.
而M为整数,于是,A/的最小值为28.
将1,2,…,10分成如
下的两组:10,7,6,3,2;
9,8,5,4,1,
依次填入图中即得图7.
例7已知n个正整数a,a2,…,
足:1 < a, < a2…< an < 2 009,且其中任意
n - 1个数的算术平均数均为正整数.求/I的
最大值.2020年第6期5
解设〇i,a2,…,an中去掉a;后的Ti-l
个数的算术平均数为6,.(i = 1,2,…,》),即, (a, +a2 + +an)-aibi =-------------—-j-----------------.n — l
于是,对1 均有
从而,(n _ 1)丨(a; - a;).
由\ - \ ^为正整数,知n - l Ti-l
(n-l) I23 x251.
由 an - %
=(Hi)+(an-i -2)+…+ (〇2-A )^(n-l)+(ra-l) + ,*> + (/i-l)
=(n - l)2,
得(n-l)2<2 008.
于是,矣45.
又(n-l) I23 x251,从而,n矣9.
下面构造说明n = 9可以取到.
^a, = 8x0 + 1, a2 = 8x1 +1,
a8=8x7 + I,a9=8x251 +1,
这9个数满足题设要求.
综上,n的最大值为9.
6正难则反(反面或反证)
例8从1,2,…,2 004中任选A:个数,
使得所选的A个数中一定可以找到能构成
三角形边长的三个数(这里要求三角形三边 长互不相等).则满足条件的A的最小值为
解原问题等价于“在1,2,…,2 004中
选左-1个数,使其中任意三个数都不能成为
三边互不相等的一个三角形三边的长•求灸
的最大值.”为使&达到最大,可选加人之数
等于已得数组中最大的两数之和,这样得: 1,2,3,5,8,13,21,34,55,89,144,233,
377,610,987,1 597, ①共16个数.对符合上述条件的任意数组,
a2,…,,显然总有不小于①中的第t•个
数.故
解得bl7.
因此A的最小值为17.
例9在一串数%,%,…,〇„中,任何连
续五项之和均为负数,而任何连续九项之和
均为正数.试问力的最大值是多少?并证明
你的结论.[5](2〇15,全国初中数学邀请赛)
解当有13项时,按如下方式排列:
al,a2,…,a9 ;
赘• • •赘 fl10 5
a3,a4,…,all ;
a4,a5,…,fl12 ;
a5,a6,…,fl13.考虑计算该表中所有数的和M
由已知,其中每行数之和为正,从而,M>0.
又数表中每一列之和为负,从而,M <0.
矛盾.
这表明,满足要求的数串至多有12项.
再构造如下一串数:-4, -4, -4,15, -4, -4, -4, -4,15,
-4, -4, -4.
验证知这12项满足题目要求.
故满足题目要求的《的最大值为12.
练习题
1.已知正整数/I满足:从1,2,…,2 020
中任取〃个两两互素的正整数,其中都必有
一个为素数.求《的最小值.
提不n的最小值为16.
2•若从1,2,…,n中任取五个两两互素
的不同的整数A,a2,…,%,其中总有一个整
数为素数,求〃的最大值.提示若049,取整数1、22、32、52、
72,