V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zealot0630
V2EX  ›  程序员

过年没事出道题大家玩玩

  •  
  •   zealot0630 · 2019-02-09 14:45:28 +08:00 · 6468 次点击
    这是一个创建于 2099 天前的主题,其中的信息可能已经有所发展或是发生改变。

    求证:任意有理数能表示为有限个 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 条附言  ·  2019-02-09 15:31:44 +08:00
    原文描述有点问题,修正:

    求证:任意正有理数能表示为有限个 1/n 之和,n 不能重复使用
    54 条回复    2019-02-12 09:43:03 +08:00
    whwq2012
        1
    whwq2012  
       2019-02-09 15:00:57 +08:00 via Android
    有理数的定义就是非无限不循环小数。非无限不循环小数包括有限小数和无限循环。有限不循环肯定可以表示为多个 1/n 想加,无限循环小数可以表示为某个分数,既然可以表示为分数那肯定可以表示为多个 1/n 相加了。

    思路应该是这样的吧,不过我也不会用数学语言表示,数学太菜了。。
    across
        2
    across  
       2019-02-09 15:03:41 +08:00
    让我思考下。
    10/7 不是无理数吗····
    across
        3
    across  
       2019-02-09 15:05:58 +08:00
    @across 掏出计算器看了下,原来是循环的。
    zealot0630
        4
    zealot0630  
    OP
       2019-02-09 15:06:31 +08:00
    忘记说了 n 不能重复啊 就是

    2/7 = 1/7 + 1/7

    这种不算,必须是不同的分母
    LGA1150
        5
    LGA1150  
       2019-02-09 15:13:46 +08:00 via Android
    @across #2 任何有理数均可以表示为分数 a/b 形式( a b 为整数,b≠0 )
    DOLLOR
        6
    DOLLOR  
       2019-02-09 15:17:12 +08:00
    @across
    整数和分数统称为有理数。也就是说,所有分数都是有理数。
    sdijeenx
        7
    sdijeenx  
       2019-02-09 15:17:41 +08:00
    楼主是不是对极限的应用有点误会?
    就算 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
        8
    hsfzxjy  
       2019-02-09 15:29:39 +08:00 via Android
    你不说能不能重复,p/q 不就是 p 个 1/q 之和么
    thedrwu
        9
    thedrwu  
       2019-02-09 15:33:10 +08:00 via Android
    0 和负数不能
    zealot0630
        10
    zealot0630  
    OP
       2019-02-09 15:34:41 +08:00
    @sdijeenx 题目不需要极限,都说了有限个的,而且是等于,不是约等于
    hxndg
        11
    hxndg  
       2019-02-09 15:35:36 +08:00 via Android
    我只想到了一个递推式的证明,从 n 到 n+1。没仔细验证,看看别人想法🙃🙃
    xml123
        12
    xml123  
       2019-02-09 15:37:04 +08:00 via Android
    这不就是埃及人表示分数的方法吗
    zealot0630
        13
    zealot0630  
    OP
       2019-02-09 15:42:58 +08:00
    @xml123 还真不知道 涨见识了 埃及人 2000 年前掌握的知识 这里有几个人能证明出来呢
    stevenashmvp10
        14
    stevenashmvp10  
       2019-02-09 15:43:47 +08:00
    思考
    感觉要用抽屉原理,但是抽屉原理不满足题目需求吧,不可能都是 1/n 啊,应该是有重复的啊
    sdijeenx
        15
    sdijeenx  
       2019-02-09 15:45:43 +08:00
    哦哦原来是这个意思~如果数字重复的话可以先取两个整数 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
        16
    zealot0630  
    OP
       2019-02-09 15:48:56 +08:00
    @sdijeenx 不能重复的哦 能重复的话 n/m = 1/m + ... + 1/m (n 个 1/m) 就可以了
    hxndg
        17
    hxndg  
       2019-02-09 15:49:28 +08:00 via Android
    @stevenashmvp10
    还行,每个数字都是可以继续拆开的。
    sdijeenx
        18
    sdijeenx  
       2019-02-09 15:51:28 +08:00
    @zealot0630 先搞定允许重复的情况找下规律ಥ_ಥ(如果 LZ 允许重复的话问题已经解决了)
    sdijeenx
        20
    sdijeenx  
       2019-02-09 15:57:32 +08:00
    @thedrwu 没错就是这个可以结贴了ಥ_ಥ
    billwsy
        21
    billwsy  
       2019-02-09 15:59:26 +08:00
    @thedrwu 居然是个算法题,我还以为是个数学题。。。
    itskingname
        22
    itskingname  
       2019-02-09 16:00:31 +08:00 via iPhone
    实际上,对于一个数 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
        23
    eccstartup  
       2019-02-09 16:01:13 +08:00 via Android
    我觉得这道题的突破口,在于你能把 5 表示成不重复的 1/n 之和
    zealot0630
        24
    zealot0630  
    OP
       2019-02-09 16:02:09 +08:00
    @thedrwu 下面俩答案只证明了小于 1 的有理数,并没有证明所有有理数可以,虽然也是证明的关键步骤,但是前面还少了一些步骤
    sdijeenx
        25
    sdijeenx  
       2019-02-09 16:03:51 +08:00
    @eccstartup 5=5/1=25/5
    Cbdy
        26
    Cbdy  
       2019-02-09 16:05:11 +08:00 via Android   ❤️ 1
    这是一个非常容易的构造性证明题,在我看懂题目的五秒钟之后我就证出来了,我稍后把答案写一下
    zealot0630
        27
    zealot0630  
    OP
       2019-02-09 16:06:35 +08:00
    @Cbdy 对的 只要贪心就能构造出来
    eccstartup
        28
    eccstartup  
       2019-02-09 16:19:21 +08:00 via Android
    @sdijeenx 并不是不重复的 1/n 之和
    geelaw
        29
    geelaw  
       2019-02-09 16:21:37 +08:00   ❤️ 2
    只考虑正数,因为 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
        30
    pod  
       2019-02-09 16:24:53 +08:00
    我也以为是数学题。。。下意识就以为是极限数列题了
    zealot0630
        31
    zealot0630  
    OP
       2019-02-09 16:28:58 +08:00
    @geelaw 好思路 但是好像有漏洞 你需要替换 a 俩-1 个 1/n 和 1/m,如果这两个分解后出现重复项,这个重复项就是 2a-2 次,并不小于 a。你这个小于 a 的条件是新出来的所有项和其他地方出来的不能重复,你并没有证明这一点
    geelaw
        32
    geelaw  
       2019-02-09 16:31:10 +08:00
    @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
        33
    zealot0630  
    OP
       2019-02-09 16:34:41 +08:00
    @geelaw 打个比方 你 1/2 和 1/6 继续分解 出来的项很可能重复 这方法并不可行 关键步骤无法证明
    hsfzxjy
        34
    hsfzxjy  
       2019-02-09 17:03:19 +08:00 via Android
    @thedrwu #19 按这个答案 2/5=1/5+1/5,同时没解决大于一的情况
    geelaw
        35
    geelaw  
       2019-02-09 17:07:32 +08:00
    @zealot0630 #33 翻了一下论文,这也是可以修复的,然而修复似乎不是很平凡 https://doi.org/10.2307%2F2688508
    Cbdy
        36
    Cbdy  
       2019-02-09 17:18:03 +08:00 via Android
    我刚刚把我的思路翻译成数学语言,发现是错的。。蛋疼
    binux
        37
    binux  
       2019-02-09 17:27:50 +08:00
    @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
        38
    hsfzxjy  
       2019-02-09 17:38:19 +08:00 via Android
    @binux 这样不一定有限终止
    Kirscheis
        39
    Kirscheis  
       2019-02-09 18:36:53 +08:00 via Android   ❤️ 1
    证明思路很简单,首先级数发散可以说明对任意大的正数都能保证有限项达到,然后贪婪法构造可以说明必定可以不重复项无限逼近,最后不等式缩放一下说明有限终止
    eccstartup
        40
    eccstartup  
       2019-02-09 20:25:30 +08:00 via Android
    @Kirscheis 这是不对的,无法证明有限项即可逼近
    aijam
        41
    aijam  
       2019-02-09 21:12:10 +08:00
    @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
        42
    zealot0630  
    OP
       2019-02-09 21:25:19 +08:00 via Android   ❤️ 1
    @aijam 下面那个新答案就是我刚才去写的
    aijam
        43
    aijam  
       2019-02-09 21:28:02 +08:00
    @zealot0630 哈哈,一样啦
    gabon
        44
    gabon  
       2019-02-09 22:17:06 +08:00 via Android
    反证吗,假设一个数 m/n 不可以这样构造,然后证明是可以这样分解的。
    Kirscheis
        45
    Kirscheis  
       2019-02-09 22:18:04 +08:00 via Android
    @eccstartup 我不是说了吗,最后要用不等式说明算法是有限终止的,怎么就无法证明了。。

    我在外面玩没法细说,你写出两项来简单缩放一下就看出来怎么证明了。。这个算法可以保证每次迭代得到的新分数的分子总是单调下降的,因为分子是个正数而且是整数,所以对任意大的起点必定是有限终止的
    SHawnHardy
        46
    SHawnHardy  
       2019-02-10 10:53:03 +08:00
    @across 有理数集对加、减、乘、除四则运算是封闭的
    macg0406
        47
    macg0406  
       2019-02-11 00:39:07 +08:00 via Android
    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
        48
    zealot0630  
    OP
       2019-02-11 04:31:54 +08:00
    @macg0406 这个证明是错的,你只用到了所有分母为 2^p*3^q 的项,然而即使把这些项全部加起来,极限是存在的,极限为 1/[(1-1/2)(1-1/3)]=3 (用等比求和公式),就是说>3 数的都无法表示,即使是 3 也需要无穷多项。
    macg0406
        49
    macg0406  
       2019-02-11 12:57:26 +08:00 via Android
    @zealot0630 是错了,1/n 分解成 1/(n+1) +1/n(n+1) 应该就可以了。
    zealot0630
        50
    zealot0630  
    OP
       2019-02-11 15:22:39 +08:00
    @macg0406 是可以,但是你无法证明其可以,比如 100,要一直分解,直到分解到约 1/e^100 才终止。你很难证明这个分解一定终止,数学是严谨的,你必须证明第四步一定会在有限步终止
    zhiqiang
        51
    zhiqiang  
       2019-02-11 15:42:06 +08:00
    p/(pq+x) = 1/(q+1) + (p-x)/((pq+x)(q+1))

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

    大于 1 的数,可以先 1+1/2+1/3 一直下去,直到剩余数足够小,然后重复上面步骤。
    zhiqiang
        52
    zhiqiang  
       2019-02-11 15:42:58 +08:00
    修改一个笔误。

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

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

    大于 1 的数,可以先 1+1/2+1/3 一直下去,直到剩余数足够小,然后重复上面步骤。
    mobaui
        53
    mobaui  
       2019-02-11 16:16:30 +08:00
    你们在说什么?我自闭了
    sunziren
        54
    sunziren  
       2019-02-12 09:43:03 +08:00
    你们到底在说什么?我也自闭了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5466 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 06:49 · PVG 14:49 · LAX 22:49 · JFK 01:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.