数学吧 关注:932,295贴子:8,931,369

回复:挺好玩的一个题

只看楼主收藏回复

声明:这两天键盘坏了,用软键盘打字太累,等键盘修好在说


17楼2009-02-13 09:01
回复
    说一下吧,先给汽车足够多的油,这样从任意一个加油站开跑都可以跑一圈,画剩余油的函数图像,找最低点,这样汽车从这里不带油也能跑一圈,道理自己想吧,很简单。PS,10L做法完全正确


    18楼2009-02-13 11:35
    回复
      2025-12-30 23:14:00
      广告
      不感兴趣
      开通SVIP免广告
      • 211.137.58.*
      楼上的说法不对。
      你说的是如何找到起始站点。但并没证明是否存在这么一个站点使车能跑完一圈。
      也就是说你这个站点相对于其它站点来说是最优选择(如果它不行,其它站点更不行),但并不能证明从它开始就能跑完一圈。


      19楼2009-02-13 12:48
      回复
        • 121.9.248.*
        假设一个站要两升油,都是等距,那么开始的时候只有1升,跑都跑不完到下一站了


        20楼2009-02-13 21:29
        回复
          • 124.236.1.*
          那句话应该是“正着转不行就反着转”,加油站是可选择的,对不?


          21楼2009-02-13 23:24
          回复
            看了回贴,LZ是否有被围观的感觉..


            IP属地:广东22楼2009-02-14 10:50
            回复
              • 211.136.222.*
              呵呵…你这是数学体啊,先骑车把油都拿来然后再跑!


              23楼2009-02-14 10:58
              回复
                我来说几句,我能不能这样说
                假设,命题的否命题即
                一辆汽车不可以从某个加油站出发, 围着环形公路跑一圈.
                是真命题,那么我来举一个反例推翻它,就能说明
                一辆汽车可以从某个加油站出发, 围着环形公路跑一圈.
                这个观点是正确的啦!!
                那么我只要从油最多的一站出发就可以了。


                24楼2009-02-14 11:03
                回复
                  2025-12-30 23:08:00
                  广告
                  不感兴趣
                  开通SVIP免广告
                  反证法:设存在某种油站分布方式使能跑玩的策略不存在,由于油的总量恰好够汽车跑完一圈,所以至少存在两个站,汽车能从一个站跑到下一个站,好!我们就从这一站(记做A)出发一直往下跑,如果能一直跑会回来,自然OK!若不行,则在某一站将终止,把这些站的路段记做a,a段的油不够用,则a段以外的油必有剩余,……B站能跑到下一站,又从此出发,同样道理,若中断,则记为b,……,这个过程一直继续到A,若中间不能接上,则因每段的油量都不够用,但总量却够用,矛盾!
                  若最后那一步能接上A站,设最后一步的起始站为C站,于是先从C站开始我们的旅程……
                  这样命题成立!不知道理解我的意思了没有?


                  25楼2009-02-14 12:33
                  回复
                    我来说一下mega-kill的想法吧。这个想法比10楼的想法还要好,因为它可以找到一个解法。方法应该是对的,我也举了很多例子进行验证。
                    我们可以这样理解:每个站k给予一个数ak,为该站油量与到下一站需耗的油量的差。比如第三站存油5,到下一站耗油6,则a3=-1.
                    由题意,a1+a2....+an=0.
                    我们要证得是存在x,使ax,ax+a(x+1),ax+a(x+1)+a(x+2),。。。。。ax+a(x+1)+a(x+2)+。。。。。+an,ax+a(x+1)+a(x+2)+。。。。。+an+a1,
                    ax+a(x+1)+a(x+2)+。。。。。+an+a1+a2.....+a(x-1)均大于等于0。
                    再谈回mega-kill的想法。他的意思是找到一个站,开到此站时存油最少(不算该站将要加上的油)。那从这站出发,初始油量为0,接下去每站的油量都不会<0,即达到负值,应此可以环绕一圈。
                     然而,mega-kill在这里作了一个隐含的假设,因此导致我花了相当时间才发现关键所在:是否从任意一个站出发,油量最少的站都一致?要是从1出发,发现3站油最少,然后从3出发,发现4油最少,那mega-kill的想法就失去意义了。
                     幸好情况不是这样。假设从1站出发,在x站油量取到最小值即在a1,a1+a2,。。。。a1+a2+a3...+ax,。。。。a1+a2+a3....(an-1)+an=0中(1)a1+a2+a3....+ax<0最小,则有从a2出发的a2,a2+a3,a2+a3+a4,。。。。。a2+a3+.....+an+a1=0(1)中a2+a3......+ax最小,即同样在ax 取得最小值。
                    这个是可证的。如果(1)中最小的是a1+a2+a3....(an-1)+an=0,则显然从a1出发可跑完一圈,不然(2)中的最小值不是a2+a3+.....+an+a1=0就是a2+a3......+ax,于是任意从k出发,或者可以找到一种走法,或者最小站是固定的,而后者又可以推出存在走法。
                     PS:我这个证法说明某些情况下最小点未必固定,。也就是虽然可以走完,但楼主的方法未必适用。也许是作法疏漏或确实如此,我会进一步进行完善。


                    26楼2009-02-14 14:23
                    回复
                      楼上正确。


                      IP属地:德国27楼2009-02-14 14:48
                      回复
                        26L说的基本上就是我的意思,不过没那么麻烦吧,如果有一个加油站到不了,说明最开始加足够多油跑一圈的时候这个加油站剩的油比起点还少,矛盾。


                        28楼2009-02-14 21:36
                        回复
                          • 222.18.40.*
                          楼主,25楼的方法也很简便啊!


                          29楼2009-02-14 22:47
                          回复
                            25L办法确实不错


                            30楼2009-02-14 23:15
                            回复
                              2025-12-30 23:02:00
                              广告
                              不感兴趣
                              开通SVIP免广告
                              25L办法很好


                              32楼2009-04-05 20:18
                              回复