Can you find the TRICK ?

1. Aug 27, 2010

remaan

1. The problem statement, all variables and given/known data

The 251 Course Sta has built n > 0 super-ultra-ecient hybrid cars, but due to various energy crises,
we can only a ord n gallons of fuel. Because of this, we tted each hybrid car with a tank big enough
to hold one gallon of fuel. Each hybrid car uses fuel at the rate of a thousand miles per gallon. Also,
each hybrid car can freely exchange fuel with any hybrid car next to it. We want to see how far from
Pittsburgh we can send a single hybrid car.
Given the experimental nature of the project, the cars are completely expendable{the only criterion that
matters is the furthest distance one of these cars can reach.
(a) [6 Points] Prove a lower bound (as a function of n) for the maximum possible distance given n
cars and n gallons of fuel.
(b) [8 Points] Now prove an upper bound (again as a function of n) for the maximum possible
distance some car can reach.

2. Relevant equations

3. The attempt at a solution

When plugging the numbers, I found that there is a pattern, specially that it is given in the problem that upper & lower bounds must be within a multiplicative factor of 4 of each other.

The pattern was :
2^0 which is 1 = 1000 miles
2^1 which is 2 = 1000 + 1000/2
2^2 which is 4 = 1000 + 1000
2^3 which is 8 = 1000 + 1000 + 1000/2

So, the lower & upper bounds for this case is : n + n/2
* but we divide by 2 whenever the power is odd ( I mean for the last term).

Am I in the right direction ?

2. Aug 28, 2010

lanedance

so you've assumed each car is paired & when the cars are 1/2 full a car is dumped & teh other filled

I think you can do a little better than that & also end up a simple formula for any n

the way to think it is that the cars all consume full, so you're best of getting rid of cars as soon as possible, without wasting any of their fuel

for example in the 4 car case after you have travelled 1/4(x1000mi), you can dump one car & use all of its remaining fuel to fill the others

this strategy leads longer max distance of 2&1/12(x1000mi),

Last edited: Aug 28, 2010
3. Aug 28, 2010

remaan

Yes, but don't you think that both mine & yours will work -
But yours will give the lower bound and mine will give the upper bound ?

Besides, is there a way to prove that ??

Thanks

4. Aug 28, 2010

remaan

besides, don't you think that your suggested strategy conflicts with note that says :
Upper and lower bounds must be within a multiplicative factor of 4 of each other.

5. Aug 28, 2010

lanedance

where does that note come from? Its not in the orginal question. I'm don't even really understand what is meant by a lower bound here?

I think the strategy I have given will get you the furthest possible distance

6. Aug 28, 2010

remaan

Maybe I forgot to write it in the first time, however it is there in the original question.

And, yes : we are required to find the max. distance. However, the problem says "lower bound for the max. dis." for part (a)

and " upper bound for the max. distance " for part (b).

Do you think that a) and b) will have the same answer ?

7. Aug 28, 2010

remaan

???
Any help ??

8. Aug 29, 2010

lanedance

I think we've done the upper bound in my other post, not too sure what is meant by the lower bound here, sorry

9. Aug 31, 2010

remaan

Hello
I think that after plugging numbers, we can see that this is a harmonic series
and therefore what we are about to do is finding these bounds for the harmonic series.
What do you think ?
Any hints ??

10. Aug 31, 2010

lanedance

yeah i also got a harmonic series

you could evaluate the upper & lower reimann sums/integrals as bounds for the maximum distance

11. Aug 31, 2010

remaan

but when we do the limited integrals, we define the limits,
however, here there isn't any limit, so how would I start ??
Any extra hint ?

12. Aug 31, 2010

lanedance

what do you mean there isn't any limit?

the series is
$$\sum_{k=1}^n \frac{1}{k}$$

now think of integrals that bound this above & below, if in doubt draw it

13. Aug 31, 2010

remaan

But what about using the tree approach or the enrolling to figure out the limits ?