华杯赛初二辅导 第九讲 组合杂题
一、对策问题
同学们都熟悉“田忌与齐王赛马”的故事，这个故事给我们的启示是：田忌采用了“扬长避短”的策略，取得了胜利.
生活中的许多事物都蕴含着数学道理，人们在竞赛和争斗中总是玩游戏，大至体育比赛、军事较量等，人们在竞赛和争斗中总是希望自己或自己的一方获取胜利，这就要求参与竞争的双方都要制定出自己的策略，这就是所谓“知己知彼，百战不殆” .哪一方的策略更胜一筹，哪一方就会取得最终的胜利。
解决这类问题一般采用逆推法和归纳法.
例1 两个人做一个移火柴的游戏，比赛的规则是：两人从一堆火柴中可轮流移走1至7根火柴，直到移尽为止.挨到谁移走最后一根火柴就算谁输.如果开始时有1000根火柴，首先移火柴的人在第一次移走多少根时才能在游戏中保证获胜.
解析：先移火柴的人要取胜，只要取走第999根火柴，即利用逆推法就可得到答案.
设先移的人为甲，后移的人为乙.甲要取胜只要取走第999根火柴.因此，只要取到第991根就可以了（如乙取1根甲就取7根；如乙取2根甲就取6根.依次类推，甲取的与乙取的之和为8根火柴）.由此继续推下去，甲只要取第983根，第975根，??第7根就能保证获胜.
所以，先移火柴的人要保证获胜，第一次应移走7根火柴.
例2 有1987粒棋子.甲、乙两人分别轮流取棋子，每次最少取1粒，最多取4粒，不能不取，取到最后一粒的为胜者.现在两人通过抽签决定谁先取.你认为先取的能胜，还是后取的能胜？怎样取法才能取胜？
解析：从结局开始，倒推上去.不妨设甲先取，乙后取，剩下1至4粒，甲可以一次拿完.如果剩下5粒棋子，则甲不能一次拿完，乙胜.因此甲想取胜，只要在某一时刻留下5粒棋子就行了.不妨设甲先取，则甲能取胜.甲第一次取2粒，以后无论乙拿几粒，甲只要使自己的粒数与乙拿的粒数之和正好等于5，这样，每一轮后，剩下的棋子粒数总是5的倍数，最后总能留下5粒棋子，因此，甲先取必胜.
例3 在黑板上写有999个数：2，3，4，??，1000.甲、乙两人轮流擦去黑板上的一个数（甲先擦，乙后擦），如果最后剩下的两个数互质，则甲胜，否则乙胜.谁必胜？必胜的策略是什么？
解析：甲先擦去1000，剩下的998个数，分为499个数对：（2，3），（4，5），（6，7），??（998，999）.可见每一对数中的两个数互质.如果乙擦去某一对中的一个，甲则接着擦去这对中的另一个，这样乙、甲轮流去擦，总是一对数、一对数地擦，最后剩下的一对数必互质。所以，甲必胜.
例4 甲、乙两人轮流在黑板上写不超过10的自然数.游戏规则：不允许写黑板上已写过的数的约数.轮到谁无法写数时，就是输者.现甲先写，乙后写，问谁能获胜？需要什么对策？ 分析：仍然利用对称原理.抢先给对方制造一个对称.只要甲先写6. 解析：这里关键是第一次写什么数，总共只有10个数，可通过归纳试验.
甲不能写1，否则乙写6，乙可获胜；甲不能写3，5，7，否则乙写8，乙可获胜；甲不能写4，9，10，否则乙写6，乙可获胜.因此，甲先写6或8，才有可能获胜.
甲可以获胜.如甲写6，去掉6的约数1，2，3，6，乙只能写4，5，7，8，9，10这六个数中的一个，将这六个数分成（4，5），（7，9），（8，10）三组，当乙写某组中的一个数，甲就写另一个数，甲就能获胜.
解：甲先写6.乙还有4、5、7、8、9、10六个数可以选择.把他们分成三组（4,5）、（8,10）、（7,9）.乙写某组数中的一个时，甲就写同组数中的另一个，从而一定获胜.
例5 有一个3×3的棋盘以及9张大小为一个方格的卡片，9张卡片分别写有：1，3，4，5，6，7，8，9，10这几个数.小兵和小强两人做游戏，轮流取一张卡片放在9格中的一格，小兵计算上、下两行6个数的和；小强计算左、右两列6个数的和，和数大的一方取胜.小兵一定能取胜吗？
解析：由于4个角的数是两人共有的，因而和数的大小只与放在A，B，C，D这4个格中的数有关.
小兵要获胜，必须采取如下策略，尽可能把大数填入A或C格，尽可能将小数填入B格或D格.
由于1+10＜3+9，即B+D＜A+C，小兵应先将1放在B格，如小强把10放进D格，小兵再把9放进A格，这时不论小强怎么做，C格中一定是大于或等于3的数，因而小兵获胜.如小强把3放进A格，小兵只需将9放到C格，小兵也一定获胜.
例6 两个人轮流数数，每个人每次可以数1个、2个、3个，但不能不数.例如第一个数1、2，第二个接着往下数3，也可以数3、4，还可以数3、4、5.如此继续下去，谁先数到100，谁就算胜.请试一试，怎样才能获胜？
分析：要抢到100，必须抢到96.这时另一个人只能数97或97、98或数97、98、99，无法
数到100.如何才能抢到96呢？有必须抢到92.以此类推，得到一列数92、88、84、?、4. 只要抢到这些数中的任何一个，然后当对方报a个数时（1≤a≤3）时，就报（4-a）个数，这样就能抢到这个数列中的上一个数，直到抢到100.
但无论第一个人报什么数，第二个人都可以抢到4n（n=1、2?）因此第二个人就有必胜的策略.只有在第二个人产生错误时，第一个人才能获胜.
思考：如果将100改为101或99，其他条件都不变，先数的人能否获胜呢？（是否还是抢4呢？）
例7 有两堆火柴，一堆16跟，一堆11跟.甲乙两人轮流从中拿走1根或几根甚至一堆，但每次只能在某一堆中拿火柴，谁拿走最后一根谁取胜，问甲如何才能取胜？
分析：这是另一类对策游戏.我们先考虑特殊情况。当两堆中的火柴根数相同时，后取者只要根据先取者的取法，在另一堆中取相同的根数，就能保证取到最后一根。对一般情况可以化为特殊情况.
解：甲从16根的那堆中先取出16-11=5根，是两堆火柴根数相同。然后每次根据对手取得根数在另一堆中取相同的根数，是两堆火柴根数保持相等，直至取到最后一根火柴而获胜。 说明：当乙先取时，如果他不知道获胜的策略，那么甲可以利用已的错误取胜。
例8 一张3×10的长方形网格纸有30个小方格.甲乙两人轮流用剪刀沿方格纸直线剪一刀.（只能沿直线剪，否则为输）甲将一份分为两份，选送一份给乙；乙按要求剪一刀后，选一份再送给甲??如此重复进行，谁送给对方一个方格，谁就获胜.甲要想获胜，有何策略 ？ 分析：送给对方一个正方形的方格纸，这时后剪的都可以使图形再变成（更小的）正方形，知道取胜为止.
解：甲先剪下7×3的一块，把3×3的那块送给乙.乙只能剪成1×3和2×3的两块.若送给甲1×3的那块，正好使甲剪下1×2而获胜.若送给甲2×3的那块，那么甲再一刀剪成1×2和2×2的两块，把2×2的送给乙.乙只可能切成1×2的两块.其中一块送给甲，甲还是获胜.
同学们，这种方法你考虑到了吗？你会不会再遇到问题时，先动脑筋想办法. 例9 下图是一张由4×10个方格组成的棋盘，一人持白子置于A位，另一人持黑子置于B位.随后两个人轮流走子，每一次可以沿一条横线或一条纵线至少走一格，并要遵守下列游戏规则：
（1）不允许和对方的棋子在同一条直线上.
（2）不能越过对方棋子所在的直线。轮到谁无路可走，就算输.
B
C A 分析：为了找到规律，我们先从最简单的情况入手，以便找到获胜的策略. 解：如果棋盘只有一个方格，两子置于正方形的对角，谁先走谁输. B B B1 （1） A A1 A (2)
在22的棋盘上，先走者按规则只能走动一格，这时后者仍能走一格，变成(1)图中的形势， 因此，持白子的人第一步应沿长边移动6格到C点处，C与B是4×4的正方形对角（两个相对的顶点）然后不论黑子如何移动，白子均可移动，使他和黑子仍然处于一个较小的正方形的对角，直至变成1×1正方形，黑子认输.
总结：以上几例，实质上都是利用一种对称原理来解决的.只要抢先给对方制造一个对称图形，输的人一定是对方. 二、抽屉原理
把5个苹果放到4个抽屉中，必然有一个抽屉中至少有2个苹果，这是抽屉原理的通俗解释.一般地，我们将它表述为：
第一抽屉原理：把（mn＋1）个物体放入n个抽屉，其中必有一个抽屉中至少有（m＋1）个物体.
使用抽屉原理解题，关键是构造抽屉。一般说来，数的奇偶性、剩余类、数的分组、染色、线段与平面图形的划分等，都可作为构造抽屉的依据.
例1 从1到10这十个自然数中，任意取出6个数，其中至少有两个是倍数关系，试说明这是为什么.
解：我们把1到10的奇数及它们的倍数放在同一集合里，则可分为5个集合，它们是：｛1，
2，4，8，｝，｛3，6，｝，｛5，10｝，｛7｝，｛9｝. ∵要在5个集合里取出6个数，
∴至少有两个是在同一集合，而在同一集合里的任意两个数都是倍数关系. （本题的关键是划分集合，想一想为什么9不能放在3和6的集合里）.
例2 袋子中有黄、红、黑、白四种颜色的小球各6个，请你从袋中取出一些球，要求至少有3个颜色相同，那么至少应取出几个才有保证.
分析：我们可把4种球看成4个抽屉（4个集合），至少有3个球同颜色，看成是至少有一个抽屉不少于3个（有一个集合元素不少于3个）.
解：设至少应取出x个，用｛x｝表示不小于x的最小整数，那么
44｛x｝＝3， ∴2＜x≤3， 即8＜x ≤12， 最小整数值是9.
44答：至少要取出9个球，才能确保有三个同颜色.
例3 从1，2，3，?，100这100个数中任意挑出51个数来，证明在这51个数中，一定：（1）有2个数互质；（2）有2个数的差为50；（3）有8个数，它们的最大公约数大于1. 证明：（1）将100个数分成50组：
{1，2}，{3，4}，?，{99，100}.
在选出的51个数中，必有2个数属于同一组，这一组中的2个数是两个相邻的整数，它们一定是互质的.
（2）将100个数分成50组：{1，51}，{2，52}，?，{50，100}.
在选出的51个数中，必有2个数属于同一组，这一组的2个数的差为50。
（3）将100个数分成5组（一个数可以在不同的组内）： 第一组：2的倍数，即{2，4，?，100}； 第二组：3的倍数，即{3，6，?，99}； 第三组：5的倍数，即{5，10，?，100}； 第四组：7的倍数，即{7，14，?，98}；
第五组：1和大于7的质数即{1，11，13，?，97}.
第五组中有22个数，故选出的51个数至少有29个数在第一组到第四组中，根据抽屉原理，总有8个数在第一组到第四组的某一组中，这8个数的最大公约数大于1.