wu :: forums
« wu :: forums - Gas Stations »

Welcome, Guest. Please Login or Register.
Oct 4th, 2024, 5:47am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, SMQ, towr, Grimbal, william wu, Eigenray)
   Gas Stations
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Gas Stations  (Read 2611 times)
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Gas Stations  
« on: Sep 19th, 2002, 12:18pm »
Quote Quote Modify 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 Smiley), 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
*****





   
Email

Gender: male
Posts: 949
Re: NEW PUZZLE: GAS STATIONS  
« Reply #1 on: Sep 23rd, 2002, 8:14am »
Quote Quote Modify 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

Email

Re: Gas Stations  
« Reply #2 on: Apr 21st, 2003, 10:04pm »
Quote Quote Modify Modify Remove 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
*****





   
Email

Gender: male
Posts: 949
Re: Gas Stations  
« Reply #3 on: Apr 22nd, 2003, 1:56pm »
Quote Quote Modify 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: male
Posts: 4863
Re: Gas Stations  
« Reply #4 on: Apr 22nd, 2003, 4:56pm »
Quote Quote Modify Modify

Good solution - But I'm not sure I want Gaseous Pigeons near my car! Cheesy
 
(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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board