题目内容
(请给出正确答案)
[主观题]
给定任一个各位数字不完全相同的4位正整数,如果我们先把4个数字按非递增排序,再按非递减排序,然后用第1个数字减第2个数字,将得到一个新的数字。一直重复这样做,我们很快会停在有“数字黑洞”之称的6174,这个神奇的数字也叫Kaprekar常数。 例如,我们从6767开始,将得到: 7766 - 6677 = 1089 9810 - 0189 = 9621 9621 - 1269 = 8352 8532 - 2358 = 6174 7641 - 1467 = 6174 ... ... 现给定任意4位正整数,请编写程序演示到达黑洞的过程。 输入描述: 输入给出一个(0, 10000)区间内的正整数N。 输出描述: 如果N的4位数字全相等,则在一行内输出“N - N = 0000”;否则将计算的每一步在一行内输出,直到6174作为差出现,输出格式见样例,每行中间没有空行。注意每个数字按4位数格式输出。 测试数据2: 3 输出结果: 3000 - 0003 = 2997 9972 - 2799 =
答案
见解析 我们用 表示有限数集 X 中元素的算术平均. 第一步,我们证明,正整数的 n 元集合 具有下述性质:对 的任意两个不同的非空子集 A , B ,有 . 证明:对任意 , ,设正整数 k 满足 , ① 并设 l 是使 的最小正整数.我们首先证明必有 . 事实上,设 是 A 中最大的数,则由 ,易知 A 中至多有 个元素,即 ,故 .又由 的定义知 ,故由①知 .特别地有 . 此外,显然 ,故由 l 的定义可知 .于是我们有 . 若 ,则 ;否则有 ,则 . 由于 是 A 中最大元,故上式表明 .结合 即知 . 现在,若有 的两个不同的非空子集 A , B ,使得 ,则由上述证明知 ,故 ,但这等式两边分别是 A , B 的元素和,利用 易知必须 A = B ,矛盾. 第二步,设 K 是一个固定的正整数, ,我们证明,对任何正整数 x ,正整数的 n 元集合 具有下述性质:对 的任意两个不同的非空子集 A , B ,数 与 是两个互素的整数. 事实上,由 的定义易知,有 的两个子集 ,满足 , ,且 . ② 显然 及 都是整数,故由上式知 与 都是正整数. 现在设正整数 d 是 与 的一个公约数,则 是 d 的倍数, 故由②可知 ,但由K的选取及 的构作可知, 是小于 K 的非零整数,故它是 的约数,从而 .再结合 及②可知 d =1,故 与 互素. 第三步,我们证明,可选择正整数 x ,使得 中的数都是合数.由于素数有无穷多个, 故可选择 n 个互不相同且均大于 K 的素数 .将 中元素记为 , 则 ,且 (对 ), 故由中国剩余定理可知,同余方程组 , 有正整数解. 任取这样一个解 x ,则相应的集合 中每一项显然都是合数.结合第二步的结果,这一 n 元集合满足问题的全部要求.
![](https://lstatic.shangxueba.com/sxbcn/h5/images/tips_org.png)