数学趣题2——关于车辆绕圈

pumpitup

原题大概是这样的：
沙漠里有1、2、3、……N，共N个加油站，首尾相连绕成一圈（1~2、2~3、……n~1）。
有一辆车要沿路绕行一圈（从i出发，顺时针或逆时针行驶直到回到i，i∈[1,2,……n]）。
每个加油站都存放一定的汽油，汽油的总量恰好够车辆绕行一圈。（可以考虑某个加油站没有油的情况，对题目没有影响，相当于加油站的数目少了一个而已）
原题的问题是：
选择哪个加油站作为出发点，可以完成绕行一圈的任务呢？




我的问题是，怎么证明这个点存在呢？也就是说，有没有可能，从任何一个点出发，小车会都在某两个点之间发生没有油的状况，从而不能完成绕行一圈的任务。如果没有可能，怎么证明之？

superacid

先把问题转化一下：
n个实数x1,x2,...,xn，它们的和非负。把这n个数一次写在一个圆上。
证明：一定存在一个k∈{1,2,...,n}，使得任何以xk为开头的连续若干个数的和都非负。

superacid

先找出连续的若干个数中和最小的那组(它总是能找到的)，不妨设为xk,...,xn
那么从1出发，沿着1→2→...→n→1的顺序一定可以回到起点

小明的马甲

找最小的部分和(x1+x2+..+xs)，则从s+1开头的连续若干个数的和都非负。。。

=====

额。。比ls慢了1分钟。。。

tm__xk

呃..都给人说了..

pumpitup

我建的模是，有下列正数x[1],y[1],x[2],y[2]……x[n],y[n]满足 所有x的和=所有y的和
要求证明必存在这样的i，满足x-y>=0,  (x-y)+(x[i+1]-y[i+1])>=0,  ……  ,(x-y)+(x[i+1]-y[i+1])+……+(x[n]-y[n])+(x[1]-y[1])+……+(x[i-1]-y[i-1]>=0

感觉和2L有点像啊　- -!
那就copy一下：再改动一下：

n个实数x[1],x[2],...,x[n]，它们的和0。把这n个数一次写在一个圆上。
证明：是否存在一个k∈{1,2,...,n}，使得从x[k]开始的任意个数字之和都非负。如果存在，如何找到这个k。

这样完备点了吧。但怎么证明呢？MS要用到反证法的？



[ 本帖最后由 pumpitup 于 2011-7-8 21:53 编辑 ]