Results 1 to 2 of 2

Math Help - Proving by induction

  1. #1
    Member
    Joined
    Sep 2010
    Posts
    96

    Proving by induction

    Can anyone help me get started on this math problem? I understand what the problem is purposing and I already know that it is indeed true, but how do I prove it?

    Suppose there is a circular auto track that is one mile long. Along the track there are n > 0
    gas stations. The combined amount of gas in all gas stations allows a car to travel exactly one
    mile. A car has a gas tank that will hold a lot more than needed to get around the track once, but it starts out empty.
    Show that no matter how the gas stations are placed, there is a starting point for the car such
    that it can go around the track once (clockwise) without running out of gas.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member MacstersUndead's Avatar
    Joined
    Jan 2009
    Posts
    291
    Thanks
    32

    Re: Proving by induction

    Without loss of generality, let us label the gas stations a_1, a_2, ... a_n, where a_1 holds the most amount of gas a_2 holds the second most amount, and so on. I'm only focusing on the 'worst' case as well, in other words, that all the gas stations hold exactly the required amount to go around the track once.

    We are given that
    \sum_{i=1}^{n} a_i = 1

    We know that the base case, n=1, is true. If there is one gas station on the track, then we place the car right at the gas station.
    Then we can invoke the induction step that if we have n gas stations, then we can place the car somewhere on the track and it will go around the track once.

    Now we have to prove P(n+1), that is to say that if we have n+1 gas stations then we have to prove that we can place the car somewhere on the track and it will go around the track once. careful, however.
    For this step we can only assume
    \sum_{i=1}^{n+1} a_i = 1 (S1) not \sum_{i=1}^{n} a_i = 1

    However, we do know that by (S1) \sum_{i=1}^{n} a_i = 1 - a_{n+1}. However, since we ordered the gas stations we know that " a_{n+1} holds the least amount of gas amongst all the other gas stations." (S2)

    and from here I don't know how to be more rigorous to prove that this is enough to show that the car can go around the track exactly once... but at least it's a start.

    EDIT: I want to say something like "No matter where you put gas station a_{n+1}, the car will reach a_{n+1} with the amount of gas that it has stored on its trip." with proof invoking (S1), (S2) and our induction step assumption.
    Last edited by MacstersUndead; November 17th 2012 at 03:55 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving by induction
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 23rd 2012, 10:16 PM
  2. Proving Complete Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 10th 2011, 01:13 PM
  3. Proving a statement by Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 20th 2011, 02:57 AM
  4. proving (by induction)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 30th 2009, 04:50 PM
  5. Need help proving!! Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 06:38 PM

Search Tags


/mathhelpforum @mathhelpforum