从捡检桃问题谈起

41 从拣桃问题谈起从拣桃问题谈起 摘要 本文从民间流传的拣桃问题出发 联系数论中的有关问题 用初等方法再次证明了本文从民间流传的拣桃问题出发 联系数论中的有关问题 用初等方法再次证明了 Braner 与与 Zeile 的结果的结果 予西民间流传这样一个所谓的 拣桃问题 曰 路上桃子多 一步有一颗 老大头前过 两步拣一个 老二跟着走 三步一抻手 老三五步老四 七 老五拣桃步十一 兄弟五人拣过后 最长空隙是几何 从而为孩子们提供了拣石子作游戏的内容 问题的答案可由试验求得 还有个解法妙诀 最长空隙 为倒数第二个人拣桃步数的两倍 将此问题一般化 当人数增加为 6 7 8 k 个时 拣桃步数按素数的顺序 13 17 19 最长 kk pp和 1 空隙用 S 表示 按解法妙诀 最长空隙为 1 2 k pS 另外 文 1 提出 若为不大于的全体素数 能有多少个连续整数 它们当中的 k ppp 21k p 每一个 一定最少被这 k 个素数之一所整除 设连续整数个数为 R 最长空隙用 S 与其相差为 1 即 R S 1 文 1 中讲到 Braner 与 Zeile 在 1930 年证明了 若时 则最少必有个这样的43 k p12 1 k p 数 按拣桃问题解法妙诀 应该有个这样的数 12 1 k p 二者谁是谁非 经过艰辛的研究 最终否决了拣桃问题的普遍性 用初等的方法再次对 BZ 的结果进 行了证明 证明的思路 当时 记集合43 1 k p 按 BZ 的结果应有个连 43 37 31 29 23 19 17 13 11 7 5 3 214 2 1 ipP i 831412 续整数 当中的每一个 一定最少被这 14 个素数之一所整除 即集合 对于 B 82 2 1 0 i iNB 中的任意一个数 n 总存在一个 换句话说 依次用去除 B 中的每一个npPp ii 使得 14 2 1 ipi 数 对于 BZ 的结果就是说用 P 筛 B 一定会被全部筛筛掉被 就称若 mmm pnnpPpBn 000 掉 而没有剩余 如果筛不净 那么 BZ 的结果就是错误的 显然 N 为偶数 首先用去筛 由于 所以筛后得到集合2 1 pNp1 41 2 112 1 iiNB 建立映射 使 N 2i 1 与 i 对应 得到集合 显然这个映射是一一映射 41 2 1 i iF 因为用已经筛掉 B 中的所以偶数 所以考察用能否筛净 就转化成2 1 p 14 3 2 ipi 1 B 能否筛净 F 14 3 2 ipi 42 将 F 中的元素 以为模 划分成三个剩余类 记3 2 p 3 mod 2 inFnF i 当用去筛时 只能筛掉上述三个集合之一在 B 中的原象 所以只有三种可能 2 1 0 i3 2 p 1 B 将 F 中的元素 以为模 划分成五个剩余类 记5 3 p 5 mod 5 inFnF j 当用去筛时 只能筛掉上述五个集合之一在 B 中的原象 所以只有五种可能 4 3 2 1 0 i5 3 p 1 B 在 F 中 用筛后 32 pp 将出现十五种情况记 i 0 1 2 32jiij FFFM j 0 1 2 3 4 以下用去筛 只要有一种方式能筛净十五个集合中的一个 那么 BZ 14 5 4 lpl ij M 的结果就是正确的 以下用去筛 记表示集合的元素个数 14 5 4 lpl 11 M ij M ij M 由于 21 3914 41 93 38 35 33 32 30 29 27 24 2 20 18 17 15 14 12 9 8 5 3 2 9 14 36 31 26 2116 11 6 1 5 mod1 04 37 34 31 28 25 22 19 16 13 10 7 4 1 3 mod1 11 312111 3131 2121 M FFFM FnFnF FnFnF 以下对集合进行这样的处理 将中的元素 分别以为模划分成剩余类集 11 M 11 M 14 5 4 lpl 合 为方便计算引进一些记号 表示以为模余 k 的剩余类集合 表示的剩余类集 mod 11ll pknMnkpT l p l pM l p 合中元素个数最多的那个集合 表示其集合的元素个数 表示的剩余类集合中元 lM pf kpT ll p 素个数等于 k 的那些集合 表示其集合的个数 kpf lT 的以为模的剩余类集合都是单元素集 以为模的剩余类集合只有一 11 M43 41 1413 pp37 12 p 个二元集 即 又 其它都是单元集或空集 令 2 12 pfM 93 2 12 pM 121111 pMMM 因而对的讨论转化成对的讨论 11 M 11 M 19221 11 M 表一是的以的剩余类集合 凡是单元集和空集就没有列出 11 M 14 5 4 lpl P10 29P9 23P8 19P7 17P6 13P5 11P4 7 3 329 325 2418 3514 2712 2314 35 9 3812 358 273 203 2924 358 15 29 15 3814 3312 2917 303 149 23 30 15 325 185 27 383 17 24 38 20 3318 2918 32 9 358 305 12 33 12 389 2020 27 43 将的及列成表二 11 M l pM lm pf P4 7P5 11P6 13P7 17P8 19P9 23P10 29P11 3 1 P13 41P14 43 l pM 4322222111 lm pf 1174332 又 6 2 3 2 3 3 544 pTpTpT 如果能从的剩余类集合中中选出某个集合列 11 M 1 2 1 0 ll piipT 组成 使得 那么 BZ 的结果就是正确的 1 2 1 0 0 ll piipT 14 12 4 0 i i l ipTL LM11 第一 考察全由组成的集合列 显然 l pM 11 14 12 4 1920 MpM i i l 观察 1054 pMpMpM 为了直观起见 我们画出配合的树形图 若 1054 pMpMpM 则发生分枝现象 决定了分枝的枝数 加括号的数字1 1 kpfpf lTlM 或 kpfpf lTlM 和 表明与前面的数字发生了重复现象 称为重复元素 2 38 9 32 3 38 27 538 24 17 3 图一 由树形图知而 令7 1054 pMpMpM 11 14 12 6 i i l pM 14 12 4 i i l pML 则 LML 11 1918117 第二 考察组成的集合序列 虽然 2 5l pMpT和其它 然而由配合的树形图二 19 2 14 12 5 4 5 ii i l pMpT 104 pMpM和 38 9 32 3 38 24 17 3 图二 中 每枝上都有一重复元素 所以 而令5 104 pMpM 13 2 14 12 6 5 i i l pMpT 则 14 12 10 6 54 2 i i l pMpTpML LML 11 1918135 第三 考察考察组成的集合序列 虽然 3 5l pMpT和其它 19 3 14 12 4 6 5 i i l pMpT 44 然而由配合的树形图三中 每枝上都有一重复元素见图三 79105 pMpMpMpM 32 15 29 12 20 3 35 18 38 15 35 12 32 9 38 9 32 338 27 5 图三 而令8 1094 pMpMpM 10 3 14 14 13 11 8 6 5 L l pMpT 14 12 10 6 54 2 i i l pMpTpML 则 LML 11 1918108 我们考察了由表一中所有的剩余类集合列都不能充满似乎 BZ 的结论是错误的 我们对 11 M 十五个集合都进行了上述的讨论 发现都筛不净 我们的出发点是让每一个 4 3 2 1 0 2 01 jiMij P 都尽可能筛的元素最多 突出一点是让筛两个元素 12 p 当考察筛一个元素的情况 即的剩余类是单元素集时 重新对划分剩余类集合 37 12 p 12 p 11 M 得到表三 这时的剩余类集合都是单元素集或空集 141312 ppp P10 31P10 29P9 23P8 19P7 17P6 13P5 11P4 7 312 319 3220 3918 3514 2712 2314 35 2 333 3212 355 243 202 152 24 358 15 29 8 399 3815 388 275 393 293 142 9 23 3 0 14 3312 2917 305 27 383 17 24 38 15 325 1817 3918 32 20 3318 295 12 33 9 358 3020 27 12 389 20 45 和前面的作法一样 考虑全由组成的集合列 画出树形图 l pM1920 14 4 i l pM 图四 以下省略 38 24 17 3 38 12 35 9 33 20 18 5 30 17 29 3 15 2 27 14 32 15 29 12 39 5 20 3 35 18 33 14 27 8 24 5 39 20 38 15 35 12 32 9 38 9 32 3 31 2 39 8 33 2 38 27 5 35 24 2 30 23 9 2 6789101154 pppppppp 图四中的数主线的一枝上共有 18 个元素 各筛一个元素 所以共有 21 元 121314 ppp 素 正好等于 11 M 由树形图中看出主线的一枝上只有一个重复元素 令 14 4 l l LMpML 知 从而用初等方法再次证明了 BZ 的结论 我们的方法不仅可以证明 而且当时 还可以把这个具体的自然数段求出来 43 k p 把能筛净的 M 的集合列写出来 并且利用的逆映射 iiN 12 即在 B 中原象写出来 35 957 2365 2775 2943 577 15 69 47 3 59 45 17 3 12 13 17 19 23 29 31 11 7 18 529 1233 1438 1522 339 835 24 230 23 9 2 iN p i i 从而得到同余方程组 11 mod03 31 mod015 29 mod05 23 mod029 19 mod027 17 mod023 13 mod09 7 mod03 NN NNN NNN 又 2 mod0 5 mod01 3 mod01 NNN 由于只筛一个元素 不妨设 141312 ppp 43 mod053 41 mod039 37 mod033 NNN 将上述同余方程组整理得 43 mod33 41 mod2 37 mod4 31 mod16 29 mod24 23 mod17 19 mod11 17 mod11 13 mod4 11 mod8 7 mod4 5 mod4 3 mod2 2 mod0 NN NNN