【习题研讨】121. 2017 年上海初三数学竞赛中的一道屠场组合题 以及 一道高一集合问题:选数相差不等于 4 或者 7

是的子集， 中任意两个数的差都不等于  或 .  问 最多有多少个元素？ ，链接指向金荣生老师指导学生的习作（公众号：静复数学，大家请关注）. 这是一道经典老题，本质上是证明连续  个数中我们至多选出  个数可以使得任意两个数的差不等于  或者 .

本文试图说明它的一般情况，并且找一些类似的题目进行学习.

设  是两个互素的正整数，且 . 从数  开始，按照下列规则依次写数：

每次从  中任意选择一个数，将它加到刚写出的数上，或从刚写出的数中减去它，把所得的数写在后面. 每次写出的数必须是正整数，不超过 ，并且没有在此前出现过. 只要还能按照这些规则写出一个新数，就必须继续；直到无法继续时才停止.

例如，当  时，一种符合要求的写法是

证明：无论每一步如何选择，停止时恰好写出了  个数，最开始的  也计入其中.

把本题的运算看成模  的加减，这样就可以把  至  这连续  个数按顺序放在圆周上, 则加  与减  相当是同一个正向跳跃，减  与加  是同一个反向跳跃.

例如对本题来说，把  按顺时针顺序放在圆周上，, .  由于我们恰好有  个数，因此一个数  或者  在圆周上效果是一样的: 相当于从这个数顺时针跳  步或者逆时针跳  步到新的数上，我们把这种效果叫做步①.  和  的效果是一样的，顺时针跳  步或者逆时针跳  步，我们把这种效果叫做步②.

这样，一旦你第一步选择了步①，由于不能产生新数，因此那么接下来的所有的选择都得是步①；第一步选择步②的话，也是一样，接下来永远是步②.  根据  互素，并且  ,我们恰好  跳跃后，我们第一次回到了出发的位置，而此前所有跳到的位置都不重复（否则至少要  次以上跳跃才行）. 因此我们就得到了本题的证明.

记 . 把  按顺时针顺序排成一圈. 约定每次顺时针前进  个位置为正向跳跃，逆时针前进  个位置为反向跳跃，越过首尾时绕回圈内.

正向跳跃：能加  就加 ，否则减 ；因为 .

反向跳跃：能减  就减 ，否则加 ；因为 .

因此，范围限制把原来的四种运算恰好变成这两个跳跃方向. 又因 ，两个方向的落点不同.

暂时允许重复，从  开始始终正向跳跃. 若在前  个数中两次到达同一点，设两次之间跳了  次，，则 . 由于 ，必有 ，矛盾. 而跳  次恰好回到 . 所以，正向跳跃把全部  个数串成一个大环，反向跳跃就是沿这个大环倒着走.

回到不许重复的规则. 第一跳可以任选方向；此后，每到一个新数，大环上刚刚经过的邻居已经写过，不能退回. 只要没走完整个大环，另一个邻居就没有写过，必须继续. 走完整个大环后，两个邻居都已出现，才无法继续.

所以，停止时恰好写出  个数.

圆周上的周期问题不禁让人想到上海初中数学竞赛历史上最著名的一道问题了! 当年满分特别少（也可能没有满分，记不太清楚），全靠这题.

有  个红球和  个白球，每个球的质量都是正整数克. 红球的总质量与白球的总质量相等，并且每种颜色的总质量都小于  克.

证明：可以从红球和白球中各取出非空的一部分，且每种颜色都不取全部，使取出的红球与白球质量相等.

设每种颜色的总质量为  克，则  是正整数，且 .

把红球的质量依次记为 ，沿一个周长为  的圆，依次截取长度为  的圆弧. 这把圆分成  段，分点记为 . 每段弧对应一个红球. 同样，把白球质量依次记为 ，将另一个周长同为  的圆分成  段，分点记为 . 将两圆叠放，初始时取共同起点 ，使 . 约定两个圆都以顺时针为正方向，从共同起点  计量弧长；白圆也沿顺时针旋转，旋转量按模  理解.

因为每个球的质量都是整数，所以所有分点距各自起点的弧长都是整数. 要让某个白分点  与某个红分点  对齐，只需把白圆旋转一个整数长度的位置. 这种旋转量绕一圈后重复，因此只有  共  种可能.

红白分点的配对共有  种，而 . 由抽屉原理，必有两种不同配对 、 需要相同的旋转量. 于是一次旋转后，可以同时使  与  对齐、 与  对齐.

两对中的红分点必不相同，白分点也必不相同：一次旋转后，一个分点不可能与两个不同分点对齐. 所以，沿顺时针方向从  到  截出的红圆弧，与从  到  截出的白圆弧长度相等，且都严格介于  与  之间.

两段圆弧各对应一组完整的球，每组都非空、都不是该颜色的全部球，并且质量相等，命题得证.

算术对应：若  分别表示红、白球的前缀和位置，圆周上的对齐量就是  模  的余数. 若把白球沿反方向放置，对齐量则写成  模 ，对应来源解答所用的340个和.

将红球、白球的质量分别记为  和 ，记前缀和

设 ，则  是正整数，且 .

考虑 （，）这  个数. 它们除以  的余数只有  种，因此必有两个不同配对满足

同一组前缀和中，任意两项的差的绝对值都小于 ，所以这两个配对必有 、. 不妨设 ，则

分两种情况：

（1）若 ，则 ，故

即

（2）若 ，则 ，故

即

两种情况下，所取红球和白球均非空，且质量严格小于各色总质量 ，因此都没有取出全部球. 命题得证.

------