Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/3/84; site talcott.UUCP Path: utzoo!watmath!clyde!bonnie!akgua!whuxlm!harpo!decvax!genrad!grkermi!panda!talcott!gjk From: gjk@talcott.UUCP Newsgroups: net.math Subject: The parking lot problem (combinatorics, really). Message-ID: <453@talcott.UUCP> Date: Fri, 14-Jun-85 16:51:18 EDT Article-I.D.: talcott.453 Posted: Fri Jun 14 16:51:18 1985 Date-Received: Mon, 17-Jun-85 03:17:36 EDT Distribution: net Organization: Harvard University Lines: 25 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