3n students are sitting in 3 rows of n. The students leave one at a time. All leaving orders are equally likely. Find the probability that there are never two rows where the number of students remaining differs by 2 or more.
Solution
Initially, we have n, n, n. It does not matter which student leaves first. We get n, n, n-1 (in some order). Now one of the students in the fuller rows must leave, which has probability 2n/(3n-1), giving n, n-1, n-1 (in some order). Now one of the students in the fullest row must leave, which has probability n/(3n-2) and gives n-1, n-1, n-1. Thus we have probability 6n3/(3n(3n-1)(3n-2) of getting from n, n, n to n-1, n-1, n-1. Continuing we have probability of 6n(n!)3/(3n)! of completing the job.
© John Scholes
jscholes@kalva.demon.co.uk
26 Nov 2003
Last corrected/updated 26 Nov 03