珍珠湾ART

标题: 圆周上停放着 N 辆相同的汽车 [打印本页]

作者: 野菜花 时间: 2005-3-22 04:15
标题: 圆周上停放着 N 辆相同的汽车

这些车的总油量恰好可以供一辆汽车绕行一周。证明不管这些车停的位置和各车的油量如何，必有一辆车，可以利用本身和其它汽车的油绕行一周。

作者: 怀疑 时间: 2005-3-22 11:27
标题: 归纳证明

N=1 时命题显然成立。

假设N=k 时命题成立，考察Ｎ＝ｋ＋１．此时必有一辆车Ａ，车上的油够它跑到下一辆Ｂ。　把Ｂ取消，把Ｂ　里油放到Ａ里，回到　Ｎ＝ｋ　的情形：此时必有一辆车　Ｃ可绕一周；　Ｃ　在原先　ｋ＋１　的配置里也可跑一周。

作者: fzy 时间: 2005-3-22 17:59
标题: non inductive proof

Let us define a function on the circle: Start at any point, the value is the gasolin left in the car. (Negetive value allowed.) After each point, the value is increased by the amount of gasolin at that point. This function reaches its minimum at some point. That point is the starting point.

作者: 野菜花 时间: 2005-3-22 20:50
标题: 回复：归纳证明

没想到这题还能用归纳法证明，想得很妙，但还有一点想不明白，如果 C 就是 A，而 C 的方向不是 A 到 B 的方向， A 加上 B 的油可以转一圈，可是没有 B 的油就可能在某一点有问题，你说呢？

作者: 野菜花 时间: 2005-3-22 20:53
标题: 回复：non inductive proof

I believe your idea is correct, but would you tell it in a little more details? I could not see why your starting point must work.

作者: fzy 时间: 2005-3-22 22:00
标题: 回复：回复：non inductive proof

This function is 0 at its start point, (at 0+, it is the amount stored at the point - Our function is right continuous ) and it is back to 0 when it comes back to the same point. If we change the start point, the new function is the same shape but differs by a constant, so the new start point is 0. If we choose the minimum point to be our start point, the function is always non-negative. So we can have enough gas to come back.

作者: 怀疑 时间: 2005-3-22 22:41
标题: 如果分方向好像不对吧。

我是假定它们都同一方向的。假设可以两个方向（反时针，顺时针），考虑一个例子，共有两辆车，分别装能跑半圈的油，但 A 需要跑 3/4 圈才能到B，而B因为方向不同，也需要跑 3/4 圈。显然不行。

作者: 野菜花 时间: 2005-3-22 23:56
标题: Great! [@};-][@};-]

对，我们对题目理解有点不同，我以为汽车掉头的油忽略不计，任何方向都可以，所以我就有以上问题。但即使用我这样理解，在你证明中先固定一个方向就 PERFECT 了。归纳法证明很妙，又容易理解！

作者: 野菜花 时间: 2005-3-22 23:59
标题: Goooood! [@};-][@};-]

Goooood!

欢迎光临珍珠湾ART (http://www.zzwav.com/)