gjk@talcott.UUCP (06/14/85)
This problem was given to me by a friend (I know the answer to it): There is a one-way street with N parking spaces in a row on one side. N cars come along, one at a time. Each driver has chosen his favorite parking spot at random from the N spaces. He drives along until he reaches it and parks there if it is not taken. If it is taken, he continues down the road until he gets to the first free one he sees and parks there. If there are no free spots after his favorite one, he drives home and watches TV. Now the question: What is the probability that all N drivers will park in this parking lot? For example, if there are two cars, then both cars will park unless they've both chosen the second spot, so the probability of success is 3/4. And another, slightly harder question: Supposing that, instead of N cars, there are K, where K<N. What is the probability that all will park? -- Greg Kuperberg harvard!talcott!gjk "The eerily accurate drawing of Goetz showed the face of the 'before' figure in comic-book ads for body-building devices."-Time Magazine, April 8