求解：最远深入多远?

灵儿

考察队员要考察一片理想沙漠（单向一维），每个人可带10天粮食，如果大家同去同回，那么每人只能向内深入5日天的距离，现为保证一人走得更远，别的队员可以中间返回，现有10001人同去，问最远可深入多远？
    
    做两个假设：
    一、每个队员每个时刻都要进食，如果没了食物，那他马上就会死亡。
    二、每个队员都要活着回去。

注：最远深入距离用天表示，最远深入多少天所走的距离

www.ddhw.com

 

HF:

We can assume that all the travelers eat one particular person's food at a time. One person's food can allow 1001 people to travel 5/1001 units round trip. At that distance, the first person keep only enough food to return to the starting point and drop the remaining food for the other 1000 people's back trip. Similarly, the second person's food allow the remaining 1000 people to travel 5/1000 units (round trip) further...   So, by this plan, the last person can reach the distance of:www.ddhw.com 5*(1/1001+1/1000+1/999+...+1/1), approximately 37.43

灵儿

  谢谢HF:

灵儿

  我拿着答案去跟朋友炫耀去了

孜孜不倦@.

   ,注册一下吧，更方便，可以收发邮件等

www.ddhw.org---

 

 

灵儿

  我注册了 谢谢孜孜不倦

孜孜不倦@.

   不敢当@。@ 偶貌似什么都没做

www.ddhw.org---

 

 

Songmomo

It should be 10*(1/10002 + 1/10001 + 1/10000 + ... + 1/2).   www.ddhw.com

MomoSong

It should be 10*(1/10002 + 1/10001 + 1/10000 + ... + 1/2www.ddhw.com suppoes that maxmium distance is D(n-1) when members are (n-1). at case of n, we can get D(n) = 10/(n+1) + D(n-1) 2*10/(n+1) for nth member, and 10*(n-1)/(n+1) for other members thus D(n) = D(n-1) + 10/(n+1)        = D(n-2) + 10/(n+1) + 10/n        =...        = D(1) + 10/3 + 10/4 + ... + 10/n + 10/(n+1)        = 10*[1/2 + 1/3 + 1/4 + ... + 1/n + 1/(n+1)] n = 1   D(1) = 5.0 n = 2   D(2) = 8.333 n = 3   D(3) = 10.833 ... n = 10001   D(10001) = 87.872 www.ddhw.com

孜孜不倦@.

很好的答案，注册一下吧，欢迎常来   www.ddhw.org---

灵儿

  

HF:

It is not very clear to me how did you get the induction formula. Can you describe how you arrange the trips when N = 2? www.ddhw.com

Songmomo

N = 1, very easy to understand. N = 2 When the second member went to the point of third of 10 days, he gave the third of 10 days foods to the first member, and remained the other 10/3 days foods for himself returning, so the first member could go 10/3 + 5 = 8.333 day. and he still could get the enough food at 10/3 days distance for returning the starting. your answer is 7.5 day. www.ddhw.com

HF:

www.ddhw.com At the 10/3-days point, the total amount of food for both person is: 40/3. The second person need 10/3 to get back to base, so at that point, the first person has only 10-days of food.  If he goes 5 days further, he only have enough food to go back to the 10/3-days point, not the starting point.  www.ddhw.com

Songmomo

The second person can wait the first member to give him the 10/3-days foods at 10/3-days point. In your answer, the point is 10/4-days point, 10/4 + 5 = 7.5. My answer is 10/3 - 10/4 = 5/6 = 0.8333 further than yours. N = 2 A -- the first member B -- the second member (1)at 10/3-days ponit     10/3-days foods  B -> A  thus     A's foods = 10-days     B's foods = 10/3-days then starting point <- B , A -> going further. (2) A -> 10/3 + 5 = 8.333 point, then A returning.www.ddhw.com (3) at 10/3-days point, B waits A and gives A 10/3-days foods. B can start from the starting point while A arrives at (10/3 + 5) *2/3 = 50/9-days  point.   www.ddhw.com

HF:

<(3) at 10/3-days point, B waits A and gives A 10/3-days foods. B can start from the starting point while A arrives at (10/3 + 5) *2/3 = 50/9-days  point.>     I don't think that is what the the original question about, the original question is: 现为保证一人走得更远，别的队员可以中间返回，现有10001人同去，问最远可深入多远www.ddhw.com It didn't say that after a person returning to the base, he can grab more food and go back to the field. If multiple returns are allowed, then the question is trivial, and the exploration can reach any distance by just one person: he just keeps going back and forth between, say, starting point and the 1 day-distance point, store enough food at that point. Then repeat this process from 1 day distance to 2 day distance, and so on...     www.ddhw.com

Songmomo

每个人可带10天粮食，如果大家同去同回，那么每人只能向内深入5日天的距离，现为保证一人走得更远，别的队员可以中间返回，现有10001人同去，问最远可深入多远？ It seemd that the above wasn't given the condition that any person could store foods at any point.

HF:

True.  So it is up to the question provider to clearify. www.ddhw.com

HF:

If we assume that  storing of food is not allowed, but multiple re-entering is. In this case, I don't think your method works in general -- the distance between the 'points' are not even, so when N>2, at some time and some point, either the provider of food has to wait for the receiver of food or vice verser -- as a result, the exploration can not go that far as you described.  If you are not convinced, try N=3...   Your induction works if we change the assumption (1) from 一、每个队员每个时刻都要进食，如果没了食物，那他马上就会死亡。 to: A teamate  consumes food when he walks, but not when he stands still.   www.ddhw.com

Songmomo

We assume the following (1) No-storing food, and multiple re-entering is OK. (2) member will die at once if food ends. N = 3 at A3 = 10/4  P3 gives 2/4-days foods -> P2, P1, then returns. www.ddhw.com at B3 = 10/4 + 10/3 = 70/12  P2 gives 1/3-days foods -> P1, then return to A3 point, P3 will wait P2 and 20/4-days foods ensures hime return to starting poin. at C3 = 70/12 + 5 = 130/12, P1 returns to  B3 point, thus P1, P2 return to starting point. let's calculate how far P1 and P2 can go. at A2 = 10/3 P3 gives P2 10/3-days food, thus P2 has 10-days foods. P2 still has 30/4-days food at B3 point, B3-A2 = 10/4, do you have any wuestion? at that time P1 has and P2 both has 30/8-days foods, www.ddhw.com what days can they return? A2=70/12-30/8 = 25/12 at A2 point, P1 will give them, 10/4-days foods, P1, P2, P3, every one has 10/4-days foods, Can they return to starting point?    www.ddhw.com

HF:

Thanks for the detailed explanation. I think you are right that your scheme works for N = 3. However, I still feel it does not work for general case. Here is my argument: For N people, the exploration according to your scheme (assume it works,  that everyone return to base alive) reach the distance of D = 10(1/(N+1)+...+1/2) Now, let's consider at the time that the first person reach the final point, the total food consumed by the crowd at that moment: D*N The total amount of food they carry with them when they set off: 10*Nwww.ddhw.com The amount of food that is transported into the field by the Nth person:  He can make one round trip in  2*(10/(N+1)) days, so in D days, he can make D/(20/(N+1)) round trips, so the total amount of food he bring into the field is: 10*(D/(20/(N+1)) = 1/2*D*(N+1) So, at time D, the total supply of food is 10*N + 1/2*D*(N+1) Since D~log(N), as N large enough, 10*N + 1/2*D*(N+1)  www.ddhw.com     本贴由[HF:]最后编辑于：2008-2-28 10:21:1

MomoSong

I think that it can be proved by the same step in the case of N. k = 2, 3, was proved. Let's Pn = explorer within N members.www.ddhw.com k = N-1, the Pn-1 can reache at the point D(n-1) = 10(1/n + 1/(n-1) + ...+1/2) k = N, the Pn can reach at point D(n) = 10/(n+1) + D(n-1), then return to the point R(n-1) = D(n) - 10/2 = 10(1/(n+1) + 1/n + ...+1/3), the Pn-1 can also reache the point  R(n-1), and Pn-1 has how many foods at the point the D(n-1) - R(n-1) = 10[1/n - 1/(n+1) + 1/2 - 1/3] = 10[1/n(n+1) + 1/6], makes Pn, Pn-1 to go 10[1/2n(n+1) + 1/12]-days.  www.ddhw.com repeat the above step R(n-2) = R(n-1) - 10[1/2n(n+1) + 1/12] D(n-2) - R(n-2) = D(n-2) - D(n) + 10/2 +  10[1/2n(n+1) + 1/12]                        = -10/(n+1) - 10/n + 10/2 + 10[1/2n(n+1) + 1/12]www.ddhw.com                        = 10/2 + 10/12 + 10[1/2n(n+1) - (2n+1)/n(n+1)] > 0   (n>4) it means that Pn, Pn-1 can return to the point R(n-2) < D(n-2), also R(n-3) < D(n-3),... is there has any problem? For this problem, we considered the different condition, and I assumed my own conditions only to ensure Pn can reache the farthest. You are also right. N = ∞ we say bye-bye to Pn because he goes forever.  www.ddhw.com At last, I thanked you so much for discussing with me, and good advice. hope to meet you here often. please visit the following: http://projecteuler.net/index.php?section=problems&show=all I think that you can do well, good luck. May I ask you a question? Are you living in American? Your English is perfect. forgive me if something wrong.   www.ddhw.com