wu :: forums « wu :: forums - Gas Stations » Welcome, Guest. Please Login or Register. Nov 28th, 2023, 6:50pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: SMQ, Eigenray, Grimbal, Icarus, william wu, towr)    Gas Stations « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Gas Stations  (Read 2586 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

Andrew Ooi
Guest

 Re: Gas Stations   « Reply #2 on: Apr 21st, 2003, 10:04pm » Quote Modify Remove

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

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »