过年没事出道题大家玩玩

[zealot0630]

求证：任意有理数能表示为有限个 1/n 之和，比如

2 = 1/1 + 1/2 + 1/3 + 1/6

4/5 = 1/2 + 1/4 + 1/20

10/7 = 1/1 + 1/3 + 1/11 + 1/231

任何有理数，包括很大的整数，也包括很小的分数

原文描述有点问题，修正：

求证：任意正有理数能表示为有限个 1/n 之和，n 不能重复使用

[whwq2012]

有理数的定义就是非无限不循环小数。非无限不循环小数包括有限小数和无限循环。有限不循环肯定可以表示为多个 1/n 想加，无限循环小数可以表示为某个分数，既然可以表示为分数那肯定可以表示为多个 1/n 相加了。

思路应该是这样的吧，不过我也不会用数学语言表示，数学太菜了。。

[across]

让我思考下。
10/7 不是无理数吗····

[across]

@across 掏出计算器看了下，原来是循环的。

[zealot0630]

忘记说了 n 不能重复啊 就是

2/7 = 1/7 + 1/7

这种不算，必须是不同的分母

[LGA1150]

@across #2 任何有理数均可以表示为分数 a/b 形式（ a b 为整数，b≠0 ）

[DOLLOR]

@across
整数和分数统称为有理数。也就是说，所有分数都是有理数。

[sdijeenx]

楼主是不是对极限的应用有点误会？
就算 LZ 是对的那也应该设这样：
2 ≈ 1/1 + 1/2 + 1/3 + 1/6
4/5 ≈ 1/2 + 1/4 + 1/20
10/7 ≈ 1/1 + 1/3 + 1/11 + 1/231

就拿某个被玩坏的数例子：
∑(n=1,∞)n = -1/12
但是
1+2+3+4+5+6+7+...+999999+999999999999999 ≠ -1/12

[hsfzxjy]

你不说能不能重复，p/q 不就是 p 个 1/q 之和么

[thedrwu]

0 和负数不能

[zealot0630]

@sdijeenx 题目不需要极限，都说了有限个的，而且是等于，不是约等于

[hxndg]

我只想到了一个递推式的证明，从 n 到 n+1。没仔细验证，看看别人想法🙃🙃

[xml123]

这不就是埃及人表示分数的方法吗

[zealot0630]

@xml123 还真不知道 涨见识了 埃及人 2000 年前掌握的知识 这里有几个人能证明出来呢

[stevenashmvp10]

思考
感觉要用抽屉原理，但是抽屉原理不满足题目需求吧，不可能都是 1/n 啊，应该是有重复的啊

[sdijeenx]

哦哦原来是这个意思～如果数字重复的话可以先取两个整数 a,b，那么：
a=(a*b)/b，然后对 a*b 分解指数，并将得到的结果尝试组合成分别相加=a*b 的式子。
再举个栗子：
a=6,b=3, a*b=18=2*3^2
6=18/3=(1+6+2+9)/3=(1+3+3+2+3+3+3)/3=1/3+3/3+3/3+2/3+3/3+3/3+3/3 = 1/3+1/1+1/1+2/3+1/1+1/1+1/1

[zealot0630]

@sdijeenx 不能重复的哦 能重复的话 n/m = 1/m + ... + 1/m (n 个 1/m) 就可以了

[hxndg]

@stevenashmvp10
还行，每个数字都是可以继续拆开的。

[sdijeenx]

@zealot0630 先搞定允许重复的情况找下规律ಥ_ಥ（如果 LZ 允许重复的话问题已经解决了）

[thedrwu]

https://math.stackexchange.com/questions/1925131/how-can-i-prove-that-every-rational-number-can-be-expressed-as-the-sum-of-1-n

[sdijeenx]

@thedrwu 没错就是这个可以结贴了ಥ_ಥ

[billwsy]

@thedrwu 居然是个算法题，我还以为是个数学题。。。

[itskingname]

实际上，对于一个数 x

x = x / 2 + x / 2

此时，把第二个 x / 2 继续除以 2：

x = x / 2 + x / 4 + x / 4

然后，右边的 x / 4 又可以继续拆分。

所以，对每一项都这样操作，不仅可以除以 2，还可以除以 3，除以 5，除以 7，除以任何一个质数。总是能够构造出多个 1/n 的形式。

[eccstartup]

我觉得这道题的突破口，在于你能把 5 表示成不重复的 1/n 之和

[zealot0630]

@thedrwu 下面俩答案只证明了小于 1 的有理数，并没有证明所有有理数可以，虽然也是证明的关键步骤，但是前面还少了一些步骤

[sdijeenx]

@eccstartup 5=5/1=25/5

[Cbdy]

这是一个非常容易的构造性证明题，在我看懂题目的五秒钟之后我就证出来了，我稍后把答案写一下

[zealot0630]

@Cbdy 对的 只要贪心就能构造出来

[eccstartup]

@sdijeenx 并不是不重复的 1/n 之和

[geelaw]

只考虑正数，因为 0 是平凡的，负数可以用相反数的分解把每项分母换成相反数解决。

从 a/b = 1/b + ... + 1/b 开始用 1/n = 1/(n+1) + 1/(n(n+1)) 反复替换即可。

具体来说，假设目前的式子里面 1/n(1) 重复 t(1) 次…… 1/n(m) 重复 t(m) 次，则把 t(k)-1 个 1/n(k) 用上面的式子替换，则重复次数最多的 1/n 重复的次数减少 1。起初重复最多的 1/n 重复的次数是 a，所以在 a 步批量替换之后就没有重复的了。

[pod]

我也以为是数学题。。。下意识就以为是极限数列题了

[zealot0630]

@geelaw 好思路 但是好像有漏洞 你需要替换 a 俩-1 个 1/n 和 1/m，如果这两个分解后出现重复项，这个重复项就是 2a-2 次，并不小于 a。你这个小于 a 的条件是新出来的所有项和其他地方出来的不能重复，你并没有证明这一点

[geelaw]

@geelaw #29 Oops 似乎有点问题，但似乎可以修复，利用 1=1/2+1/3+1/6，每次把每个 1/n 都替换为 1/(n+1)+1/(n(n+1))，这样可以保证永远不重复，这就证明了 1 可以表示为分母任意大的一堆不同的 1/n 之和，从而任意的 1/k 都可以表示为分母任意大的一堆不同的 1/n 之和（前面的式子乘 1/k 即可）。

先用 a/b = 1/b + ... + 1/b

把第二个 1/b 表示为分母大于 b 的一大堆 1/n 的和，这样修改之后用到的最大分母是 b(1)。
把第三个 1/b 表示为分母大于 b(1) 的一大堆 1/n 的和，这样修改之后用到的最大分母是 b(2)。
如此继续

[zealot0630]

@geelaw 打个比方 你 1/2 和 1/6 继续分解 出来的项很可能重复 这方法并不可行 关键步骤无法证明

[hsfzxjy]

@thedrwu #19 按这个答案 2/5=1/5+1/5，同时没解决大于一的情况

[geelaw]

@zealot0630 #33 翻了一下论文，这也是可以修复的，然而修复似乎不是很平凡 https://doi.org/10.2307%2F2688508

[Cbdy]

我刚刚把我的思路翻译成数学语言，发现是错的。。蛋疼

[binux]

@zealot0630 比如你 1/1, 1/2, 1/3 ... 1/n 都用过了，现在剩下 k/l (k < l)， 你只需要继续 k/l - 1/(n-1) - 1/(n-2) ... 1/(n-m) 直到 k'/l' 小于 1/(n-m)。你继续分解 k'/l' 一定不会重复

[hsfzxjy]

@binux 这样不一定有限终止

[Kirscheis]

证明思路很简单，首先级数发散可以说明对任意大的正数都能保证有限项达到，然后贪婪法构造可以说明必定可以不重复项无限逼近，最后不等式缩放一下说明有限终止

[eccstartup]

@Kirscheis 这是不对的，无法证明有限项即可逼近

[aijam]

@zealot0630 #24
> 下面俩答案只证明了小于 1 的有理数，并没有证明所有有理数可以，虽然也是证明的关键步骤，但是前面还少了一些步骤

H(n) = 1/1 + 1/2 + ... + 1/n，由于 H(n)发散，对任意一个有理数 x，总能找到 H(n) <= x <= H(n+1)。
如果任意等号成立，则平凡解。
否则，有 H(n) < x < H(n+1)，则 0 < x - H(n) < 1/(n+1)。
已证明 x - H(n)可以被表示，且这个数比 1/(n+1)小所以不会和 H(n)里的任意一项重复。
再加上 H(n)就是 x 了。

[zealot0630]

@aijam 下面那个新答案就是我刚才去写的

[aijam]

@zealot0630 哈哈，一样啦

[gabon]

反证吗，假设一个数 m/n 不可以这样构造，然后证明是可以这样分解的。

[Kirscheis]

@eccstartup 我不是说了吗，最后要用不等式说明算法是有限终止的，怎么就无法证明了。。

我在外面玩没法细说，你写出两项来简单缩放一下就看出来怎么证明了。。这个算法可以保证每次迭代得到的新分数的分子总是单调下降的，因为分子是个正数而且是整数，所以对任意大的起点必定是有限终止的

[SHawnHardy]

@across 有理数集对加、减、乘、除四则运算是封闭的

[macg0406]

1. 任意 m/n 都可以分解成 m 个 1/n
2. 对任意的 1/n 都可以分解成 1/2n + 1/3n + 1/6n

任意正有理数都可以分解成有限个 m1/n1 + m2/n2 + ... + mk/nk，即 m1 个 1/n1 项, m2 个 1/n2 项，... , mk 个 1/nk 项
3. 对于 mk 大于 1 中最大的 nk, 可以将 mk/nk，可以分解为 1/nk + (mk-1)*(1/2nk + 1/3nk + 1/6nk)，考虑到相同分母合并(不约分)，分母为 2nk, 3nk, 6nk 的项的数目小于等于 mk(前面假设大于 nk 的项的数目最多为 1), 该步骤可以在分母小于 nk 的项不变的情况下使 nk 变大过 mk 变小，因此该步骤有穷。
4. 重复步骤 3，直到所有相同分母项的个数都为 1。

如 3= 3/1
=1/1+2/2 +2/3 +2/6
= 1/1 +2/2 +2/3 +1/6 +1/12 +1/18 +1/36
= 1/1 + 2/2 +1/3 + 2/6 + 1/9 +1/12 +2/18 +1/36
= 1/1 + 2/2 +1/3 + 2/6 + 1/9 +1/12 +1/18 +2/36 + 1/54 +1/108
= 1/1 +2/2 +1/3 + 2/6 + 1/9 +1/13 +1/18 +1/36 +1/54 +1/72 +1/108+1/144
....

[zealot0630]

@macg0406 这个证明是错的，你只用到了所有分母为 2^p*3^q 的项，然而即使把这些项全部加起来，极限是存在的，极限为 1/[(1-1/2)(1-1/3)]=3 （用等比求和公式），就是说>3 数的都无法表示，即使是 3 也需要无穷多项。

[macg0406]

@zealot0630 是错了，1/n 分解成 1/(n+1) +1/n(n+1) 应该就可以了。

[zealot0630]

@macg0406 是可以，但是你无法证明其可以，比如 100，要一直分解，直到分解到约 1/e^100 才终止。你很难证明这个分解一定终止，数学是严谨的，你必须证明第四步一定会在有限步终止

[zhiqiang]

p/(pq+x) = 1/(q+1) + (p-x)/((pq+x)(q+1))

小于 1 的分数，可以分解，使得分子越来越小，直到变为 0，结束。

大于 1 的数，可以先 1+1/2+1/3 一直下去，直到剩余数足够小，然后重复上面步骤。

[zhiqiang]

修改一个笔误。

p/(pq+x) = 1/(q+1) + (p-x)/((pq+x)(q+1))，其中 0<x<p。

小于 1 的分数，可以分解，使得分子越来越小，直到变为 1，结束。

大于 1 的数，可以先 1+1/2+1/3 一直下去，直到剩余数足够小，然后重复上面步骤。

[mobaui]

你们在说什么？我自闭了

[sunziren]

你们到底在说什么？我也自闭了