第3讲 调整与操作问题 上海市延安中学 羡学超.doc

2011年协作体夏令营系列讲座(三)调整与操作问题上海市延安中学 羡学超在国内外各级数学竞赛中，常常有调整和操作变换问题，调整是组合构造的一种常用手段，我们所构造的对象，常常需要同时满足多个条件，此时可先构造一个初胚，使之满足部分条件，进而对其中一些元素进行适当调整，使之逐步满足题设的所有条件。操作变换问题的操作过程实际上是一个变换过程，但是操作规则通常无法表达为明显的递推公式，使得操作变换问题往往不需要太多的数学知识，但灵活性、技巧性又很高，对开拓解题思路，增强思维能力有很大的帮助。下面我们研究几个具体实例。例1 朱丽叶和约翰玩一个含有张卡片的游戏每张卡片上都有一个正整数，将这些卡片排成一排，且每张卡片上的数字都可以看到两人轮流以下面的方式取卡片：每一轮，每个人要么取走最左面的卡片，要么取走最右面的卡片每个人最后总分为他在这轮后所取的所有卡片上的数字之和证明：若约翰先取卡片，他总能使其最后总分不少于朱丽叶的最后总分（2008荷兰国家队选拔考试）例2 甲、乙两人玩下面的游戏甲先开始规定：他们轮流写非负整数对，使得对于任意前面写过的数对，要么，要么若谁被迫写，则谁输（1）证明：游戏在有限次操作后结束；（2）问：谁有获胜策略？ （2009白俄罗斯）例3 在平面直角坐标系中，最初在点处有一只跳蚤随后他进行了次跳跃，每一次都沿东、西、南、北四个方向之一(即坐标轴方向) 第次跳跃的长度为（）求证：对于每种不同的跳法，跳蚤最终到达的位置互不相同（2009意大利）例4 对于满足的实数定义运算现有一个项数为的实数列，其所有项均满足，从中任取两项除去，并将的值添在的后面，这样得到的新数列的项数就减少了1重复该操作直至仅剩一项（1）求证：最后剩下一项的值与每一步操作中所取的两项无关；（2）若中的项的取值范围变为，且中恰有一项为1，结论又将如何？（2007加拿大）例5一名学生在个环形排列的方格中各写了正数，然后他擦掉这些数，并写下与每个数相邻的两个数的几何平均数求证：存在一个方格，其内的数没有被变大 （2005斯洛文尼亚）例6甲、乙两人各有一枚棋子分别放在的棋盘左下方第一格和右下方第一格内玩游戏游戏规则是：甲、乙两人轮流在棋盘上沿水平或垂直方向移动一步棋子，甲先开始求证：经过有限次移动，无论乙如何移动棋子，甲的棋子总能和乙的棋子相遇强化练习题1有两堆小石头，若从第一堆搬100块到第二堆，则第二堆石头数变为第一堆石头数的两倍；反之，若从第二堆搬若干块到第一堆，则第一堆石头数将变为第二堆石头数的6倍，则第一堆至少有_块小石头2有盒火柴摆成一圈，然后作如下调整：若连续4盒火柴棍数之和为奇数，则其中每盒都拿去一根火柴棍，否则每盒都放一根火柴棍，而且每连续4盒火柴均恰好作一次这样的调整之后，盒火柴棒总数不变（1）若，且这8盒火柴棍数分别为1，2，3，4，5，6，7，8，求这些火柴盒经过8次调整后的火柴数，并验证火柴棒总数是否有不变？（2）求证：是4的倍数 3设有一个正边形（1）。两人按如下法则做游戏：轮流在该正多边形内画对角线；每人每次画一条新的（以前没有画过的）对角线，而它恰好与已画出的偶数条对角线相交(交点在正多边形内)；凡无法按照要求画出对角线者即为负方：问：谁有必胜策略？ （摘自2010年协作体）4设23个不同正整数的和为4845，求这23个正整数的最大公约数的最大值 5某电影院的座位共有排，每排有座，票房共出售张电影票由于疏忽，售出去的票中有些号是重的不过可以让所有观众适当就座，使每位观众都有一个座位，且每位观众所坐位置的排号和座号中至少有一个与他所持的票上对应的号码相同求证：在上述适当的安排中，存在一种安排方法，使至少一人所作位置的排号和座号与他所持票上的排号和座号都完全相同（1991独联体）第三讲 参考答案 2011-7-191解：设从左至右的张卡片分别为对用数学归纳法证明：约翰若是想拿到“”和“”其中之一，这件事总能做到（1）时，命题显然成立（2）假设时，命题成立考虑张卡片若约翰想得到奇数号卡片，则他先拿，此时朱丽叶只能拿或若朱丽叶拿的是，则经过这两次取卡片后，对应一个新序列，由假设可知，约翰可拿走奇数位的，故它可取走全部奇数位的若朱丽叶拿的是，则经过这两次取卡片后，对应一个新序列，由假设可知，约翰可拿走偶数位的，故它可取走全部奇数位的 同理可证约翰想得到偶数号卡片的情况 进而命题得证 由于每张卡片上的数字事先都可以看到，故约翰可事先计算奇数位和偶数位上的数字之和，依据结果取卡片，从而保证他最后总分不少于朱丽叶最后总分例2解（1）假设可以进行无限次操作设写出的数对分别为， 则对于所有的，存在正整数、，使得，对于任意，则有或，矛盾因此，只有有限个满足条件（2）甲获胜第一次操作甲选若乙选数对，则甲选 注意到甲每次操作后，由于对应着变换，于是可能的数对构成的集合没有改变，而乙每次操作后，可能的数对构成的集合改变了，因此，甲总能不取例3证明：设，是跳蚤经过的点对于任意的（），有，即跳蚤跳跃次之后，其位置一定在正方形内，且的四个顶点分别为、因此，点应在平移之后的正方形内，平移的方向是沿、这四个向量之一沿四个方向平移之后得到四个正方形，而这四个正方形的内部是没有交集的，因此第次跳跃之后的位置完全确定了跳跃的方向例4（1）证明：首先证明运算保持对任意的（）都有事实上，由及可知因此，运算可以只进行下去由，得又=，=，可知=即运算满足交换律和结合律由于最后剩下的一项是中的个数关于的运算，因此最后的值与每次操作选取哪两项无关（2）对于每一个，因此1总会在这变化着的数列中，直到最后只有一项，且最后剩下的一项为1例5证明：反证法假设原命题不成立，即所有方格的数都变大，不妨设原来个数为，操作后新数为，其中 由假设知，于是，矛盾因此，原命题得证例6证明：甲的策略如下：记为甲、乙分别移动步后，棋子所在的行和列围成的长方形甲移动棋子的方向是使得的长边变短设、分别为甲乙各移动步后的长与宽易知按照甲的策略，甲乙分别移动一步后，有或，所以长方形周长不增且半周长为奇数，即长方形长宽不相等这样，甲可以按照自己的策略移动由于棋盘有界，一定可以减少，当时，甲乙相遇，命题得证习题参考答案：1解：设第一堆为块，第二堆为块，则，解得，所以为11的倍数且，故的最小值为10，相应的最小值为1702解:（1）调整后的火柴棒棍数分别为：1，2，3，4，5，6，7，8，那么火柴棒的总数不变；（2）盒火柴摆成一圈，把每连续4盒火柴进行一次调整，则共需进行次调整设其中有次需要“拿出”4根火柴，有次需要“放入”4根火柴，则次调整后火柴总数变化了由于总数不变，则，即下面证明为偶数用反证法，设为奇数设为第次调整后，调整过的4个火柴盒的火柴棍个数之和，令由于调整中有次火柴数为奇数，每次拿掉4根后，和仍然为奇数，那么这些的和为奇数又调整中有次火柴数为偶数，每次放入4根后，和仍然为偶数，那么这些的和为偶数，所以为奇数另一方面，对于每个原来的火柴盒，与它相关的调整有4次，所以这个盒子在中被加了4次，且每次调整后盒中的火柴数或者加1，或者减1，即盒中的火柴数的奇偶性改变了，所以每个盒子在中被加了2次奇数，2次偶数，则每个盒子在中的部分为偶数，故为偶数，与上述为奇数矛盾所以为偶数，则为4的倍数3解：将先开始的人称为甲，后开始的人称为乙。如果为奇数，则乙有取胜策略；而若为偶数，则甲有取胜策略。由于正多边形的边数为奇数，所以对于任何一条对角线来说，都是在它的一侧有奇数个顶点，在另一侧有偶数个顶点。因此每一条对角线都与偶数条其它对角线相交。假设到某个时刻，游戏不能再进行下去，那此时每一条未画出的对角线都与奇数条已画出的对角线相交，也与奇数条未画出的对角线相交。这样的情况只能出现在未画出的对角线的条数为偶数的时刻。事实上，如果我们对每一条未画出的对角线都数一数与它相交的未画出的对角线的条数。那么每一条未画出的对角线都被数了两次，所以总和应当为偶数；但若未画出的对角线的条数为奇数，那么总和就是奇数个奇数的和，为奇数，由此产生矛盾。所以未画出的对角线的条数为偶数。如此一来，如果多边形中的对角线的总数为奇数，即为偶数，那么应当甲可取胜；若为偶数，即为奇数，那么应当乙可取胜。4.解：设23个不同正整数分别为，且，令，由题意知，即，因为互不相同，所以是互不相同的正整数，所以，从而，所以下面构造，使4845=即因为，故可在“23”上添加一个9，即去掉23，换为32于是可构造如下实例：，故的最大值为175.证明：由题设票有重号，破坏了票座之间的一一对应，必有数票对一座，也至少必有一座无票与之对应我们先考虑这种情形：让所有观众根据题设规则全部就座，并把这时的位置称为各人的“原来位置”，下面我们进行调整我们从位观众中任选一名观众（编号为第一号），如果他恰好同时坐对了排号和座号，（称这样的位置为持票人“自己的位置”，下同），则命题得证若不然，我们请第一号观众根据所持票号坐到“自己的位置”，同时请出了坐在该位置上的被编为“第二号”观众，如此下去，一直请到“第号”观众为止此时，第一号观众“原来位置”还空着，“第号”观众还未就座对于自然数，我们可以这样要求：或者“第号”