Author |
Topic: Gas Stations (Read 2600 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Gas Stations
« on: Sep 19th, 2002, 12:18pm » |
 Quote  Modify
|
Suppose a race track in the shape of a simple close curve (i.e. it does not intersect itself), and suppose that distributed along it, in any way whatsoever, are N gas stations. Suppose that a race car needs L liters of gas to go completely around the track, and that the sum of the gas available at the N stations is exactly L.
Consider that the car cannot move without gas (independently of its momentum when it runs out  ), and that it has constant mileage (consumption of gas is directly proportional to the distance the car moves, and depends on nothing else).
Prove that there exists at least one gas station such that, starting from it, the car can do a full lap.
|
| « Last Edit: Nov 7th, 2002, 8:50am by Pietro K.C. » |
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PUZZLE: GAS STATIONS
« Reply #1 on: Sep 23rd, 2002, 8:14am » |
Quote Modify
|
I'll give a big hint here by rephrasing the question:
Define the gassifunction, gas(x,y): The gassifunction is the amount of gas the car would have after driving to position x, assuming that the car starts at position y. The gassifunction in general can take on negative values.
Given the gassifunction gas(x,y), prove that there exists a y0 so that gas(x,y0) >= 0 for all x.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Andrew Ooi
Guest
|
Got a possible algorithmic solution. Would this be acceptable?
Rule A: There is enough gas in stations to complete the circuit.
Solving C: Given rule A there is a station that you can start that will enable the circuit C to be completed.
1) There must be at least one station S which have enough fuel to get you to the next station along the circuit S' (Pigeon Gas Principle!) if rule A is obeyed for that circuit.
2) You can get a new shorter circuit C' with 1 less station by collapsing these two stations and removing the part of the circuit between the two stations, and leaving in that station the amount of gas in S + S' minus the gas used in traversing between the stations. The new circuit should satisfy rule A too.
3) WLOG, solving C' also obviously allows you to solve C by re-expanding out the 2 stations again.
4) By repeating step 1 & 2, we can collapse the circuit until we have 2 stations left (C2).
5) The one with enough fuel to get to the other station in the 2 station configuration is the one from which we can start to definitely be able to complete the circuit C2. By 3), it will also allow you to solve C by reexpanding.
Q.E.D.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Gas Stations
« Reply #3 on: Apr 22nd, 2003, 1:56pm » |
Quote Modify
|
Andrew,
That looks good to me! I guess you're effectively finding the one stretch of track that, until you collapse to just one gas station, can never be traversed. Starting right after this stretch lets you complete the circuit.
The only additional thing I would specify is that when you collapse the two gas stations, you remove S' and keep S. Otherwise, somebody might get confused as to which gas station is which when re-expanding.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Gas Stations
« Reply #4 on: Apr 22nd, 2003, 4:56pm » |
Quote Modify
|
Good solution - But I'm not sure I want Gaseous Pigeons near my car! 
(Sorry! I couldn't resist.)
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove