过年没事出道题大家玩玩

[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

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

[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 这是不对的，无法证明有限项即可逼近