wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Gas Stations
        
(Message started by: Pietro K.C. on Sep 19^th, 2002, 12:18pm)

Title: Gas Stations
Post by Pietro K.C. on Sep 19^th, 2002, 12:18pm

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.

Title: Re: NEW PUZZLE: GAS STATIONS
Post by James Fingas on Sep 23^rd, 2002, 8:14am

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 y₀ so that gas(x,y₀) >= 0 for all x.

Title: Re: Gas Stations
Post by Andrew Ooi on Apr 21^st, 2003, 10:04pm

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.

Title: Re: Gas Stations
Post by James Fingas on Apr 22^nd, 2003, 1:56pm

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.

Title: Re: Gas Stations
Post by Icarus on Apr 22^nd, 2003, 4:56pm

Good solution - But I'm not sure I want Gaseous Pigeons near my car! :D

(Sorry! I couldn't resist.)