数学归纳法解一类计数问题

《数学归纳法解一类计数问题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、维普资讯http://www.cqvip.com12中等数学数学归纳法解一类计数问题方廷刚(成都市第七中学，610041)数学归纳法可应用于解决与正整数有关任取5的一个元素为t．由于5＼{t}的许多问题，包括一些较复杂的计数问题．用中与t之差的绝对值属于曰的元素至多有数学归纳法解计数问题时，“归纳过渡”常表2c+个，而2c：++1

2、方法进行问题的推广对每个1≤J．≤k，S＼{t，t2，⋯，t}中与tj之例1设5：{1，2，⋯，1000000}，A为5差的绝对值属于B的元素至多有2c+个，的一个恰包含101个元素的子集合．证明：在故S＼{tJ，t2，⋯，t}中至少与tl，t2，一’，t5中存在数t，t，⋯，t∞，使得下列集合中的一个之差的绝对值属于B的元素至多A={+tI∈A}，=1，2，⋯，100．有k·2C个．而中的任意两个都不相交．k‘2C：+1≤(m一1)·2C+(第44届IMO)≤(n一1)n(n+1)=n一n

3、存在与t1，t2，⋯，设正整数n(n≥2)，S={1，2，⋯，n}，At中的每一个之差的绝对值都不属于B的为5的一个包含n+1个元素的子集合．则元素，任取其一为t．对任意正整数m≤n，存在5的一个m元子根据数学归纳法原理，具有所述性质的集T={t，t，⋯，t}，使得下列集合集合T={t，t，⋯，t}存在．A，={+tjI∈A}，=1，2，⋯，，n．例2某市有n所中学，第i所中学派中的任意两个都不相交．出C名学生(1≤C≤39，1≤i≤n)到体育馆证明：考虑由A中两个不同元素的差的绝对值组成的集合B，则B中至多有c+个观看球赛，总人数ci：1899．

4、看台上每一元素．横排有199个座位，同一学校的学生必须坐若有t>f，使AnA≠，则存在0∈在同一排．问至少要安排多少个横排才能保A、b∈A，使0+t=b+f，故t一f=b一0证学生全部坐下?∈B；反之，若t—tj∈B，将上述过程逆过来由于1899=55×34+29，可知只用l0排可证AnA≠．不能保证学生全部坐下，易猜到用11排可保于是，“集合Aj={+tjI∈A}(．=1，证学生全部坐下，但要证明这个猜测却不太2，⋯，m)中的任意两个都不相交”等价于“容易．下面证明一个加强命题：中任意两个元素之差的绝对值均不属于B”．n对任何非负整数r，若学生总

5、数c≤下面归纳地构造出5的一个m元子集IlT={t1，t2，⋯，t}．170r+199，则只须安排不超过r+1个横排，维普资讯http://www.cqvip.com2005年第4期l3就能保证学生全部坐下．生所属学校，问题归结到r=的情形；证明：先按学生数从大到小的顺序将各(3)若31≤n+2≤33，且n+l≥34，贝06≥校编号为1，2，⋯，，即编号后对应的{c}构170．去掉第个横排及在该排就座的学生所成一个不增的数列．现按编好的顺序依次入属学校，问题归结到r=的情形；座：从第1排开始，第1所学校，第2所学校，(4)若31≤n+2≤n川≤33

6、，则第+1个⋯⋯．若第1排最后一所学校的学生不能全横排应排6所学校的学生，故学生数大于或坐在第1排，则干脆全退到第2排，⋯⋯，按等于6×31=186且小于或等于6×33=198．此规则先坐完全部学生．去掉第+1个横排及在该排就座的学生所记第}就座的学生数为6，，这些学生属学校，问题归结到r=的情形．所属的学校数为(易知xj>15)，该排第一所这就证明了r=+1时，结论仍成立．学校的学生数为n，则由上述坐法知6+从而，对任何非负整数r，所述结论成立．例2是命题r=10的情形．aj．+lI>200且≥xj．aj川可得≥200．例3女口果nl=1，n=+

7、n—l(2≤≤⋯i再由xj．I>5知≥167．)，则称n。，n，⋯，n为正规数．问：在集合{1，2，⋯，2001}中是一个正规数本身或若干又若n⋯≤30，则6，≥170；个不同正规数之和的数有多少个?若n，+l≥34，由6，≥xjaj+l仍有6，≥170．解：易知O,k：：c+。，这些正规下面用数学归纳法证明．二当r=0时，结论显然成立．数组成序列1，3，6，10，15，21，28，36，45，55，当r=1时，⋯．先检验其他数中能被正规数表示(即能写(1)若学生总数小于或等于199，结论成立；成若干个不同正规数的和)的数的情况：(2)若6．≥17

8、0，结论成立；小于6的正整数中，2和5不行，其他数(3)若6，=169且学生总数小于或等于都能被小于6的正规数表示；368