Everyone who lives in a city (that has cars for hire) has probably
experienced this: several of you pack into a taxi, and you give the
driver a laundry list of stops to make. You're the first person out,
and the meter reads $n (or substitute your local currency). How much should
you contribute? Given that the primary purpose of sharing the taxi is
to split the cost of the fare, what is an equitable strategy for doing
it?

Before we go leaping into the arithmetic, we have to define what a
"fair" method is, so we start from first principles. Assume
the fare at the first stop is **n**. Obviously the full **n** is
too much to contribute: if there is only one more stop left and it is two
blocks away, the second person contributes almost nothing. What we would
like, then, is a system where riders contribute for only the portion
of the ride that they enjoy.

OK, so **method #1**: if there are (say) 3 stops, and the meter reads
a, b, and c respectively when each of the three riders gets out, then
each rider should pay the fraction of the fare equal to the ride he or
she enjoyed divided by the sum of the fares for the rides everyone enjoyed
(the total person-cost). Since the total fare is c (the meter amount at
the last stop), the first rider would pay the fraction a/(a+b+c) of c,
or ac/(a+b+c). The second rider would pay bc/(a+b+c) and the third would
pay c^2/(a+b+c). Great -- we're done.

This is fair by our operative definition, but unfortunately it is **totally
and utterly impractical**. It involves arithmetic that most people
would find hard to do in their heads, especially after they've had a few
beers (Try it: *a*=5.25, *b*=7.60, *c*=12.45.
What's *bc*(*a*+*b*+*c*)?),
which may be why they're taking a taxi home in the first place. Furthermore,
unless this is the kind of ride you do on a regular basis with the same
stops, *all of the quantities aren't known* until the last person gets
out, so it is not even possible to do the calculation without estimating
the quantities. What would be better is something fair, where all the
quantities are known when you pay, and which is relatively practical.

**So method #2 (more practical)**: As a participant in this process,
all you have to remember to do before your stop is (1) hold on to the
money that the person who gets out at the previous stop gives to you, and
(2) note the amount on the meter when that happens. Then when your stop
comes:

- take whatever money was given to you by the previous person and
*contribute
the same amount* with your money. You now have twice as much money in
your hand.
- look at the meter. Subtract from it the meter amount you were asked
to remember from when the last person got out (this is obviously 0 if you
are the first stop), and then divide by the number of riders left (including
you). Add this amount to the money already in your hand (if any).
- give this big wad o'cash to the next person scheduled to get out, reminding
them to note the amount on the meter.
- get out of the taxi, secure in the knowledge that you have paid your
fair share.

The process repeats for all passengers, and the last person pays the
driver the full fare.

**Why this works**: Consider that another, perhaps better operative
definition of fairness is that at any given time, a passenger should be
splitting the cost of the ride with the number of people in the car. That
means that for N people when person A gets out and the meter reads *a*,
he or she should contribute *a*/*N*. When B gets
out, the contribution should be *a*/*N* (for the
first segment) + (*b* - *a*)/(*N* -
1) (for the second segment). It's easy to see that this is equivalent to
the algorithm described above.

**What it looks like: **It's interesting to look at the differences
between these two methods for various types of rides. Here's what each passenger
pays for a 4-stop ride with relatively evenly-spaced stops:

#left fare Method 1 Method 2
------ ---- -------- --------
4 5 1.92 1.25
3 10 3.85 2.92
2 17 6.54 6.42
1 20 7.69 9.42

And here it is for stops where each is twice as far as the previous one:

#left fare Method 1 Method 2
------ ---- -------- --------
4 2 1.07 0.50
3 4 2.13 1.17
2 8 4.27 3.17
1 16 8.53 11.17

**Note** that this is still probably too cumbersome to actually
use in the real world (people tend to split cabs using bills, without resorting
to fumbling with change, which introduces errors in the recursion), but
as a toy problem it is quite interesting because it hinges as much on
the operative definition of "fair" and the need to have information
at specific times as it does the mathematics.