Some of your friends with jobs out West decide they really need some extra time each day to sit in front of their laptops, and the morning commute from Woodside to Palo Alto seems like the only option. So they decide to carpool to work. Unfortunately, they all hate to drive, so they want to make sure that any carpool arrangement they agree upon is fair and doesn’t overload any individual with too much driving. Some sort of simple round-robin scheme is out, because none of them goes to work every day, and so the subset of them in the car varies from day to day. Here’s one way to define fairness. Let the people be labeled S = {p1, . . . , pk}. We say that the total driving obligation of pj would have driven, had a driver been chosen uniformly at random from among the people going to work each day. More concretely, suppose the carpool plan lasts for d days, and on the i-th day a subset Si ⊆ S of the people go to work. Then the above definition of the total driving obligation ∆j for pj can be written as ∆j = P i:pi∈Si 1 |Si| . 1 Ideally, we’d like to require that pj drives at most ∆j times; unfortunately, ∆j may not be an integer. So let’s say that a driving schedule is a choice of a driver for each day — that is, sequence pi1 , pi2 , . . . , pid with pit ∈ St — and that a fair driving schedule is one in which each pj is chosen as the driver on at most d∆je days. (dxe denotes the smallest integer that is greater than or equal to x.)

Prove that for any sequence of sets S1, · · · , Sd, there exists a fair driving schedule.