22nd CanMO 1990 Problem 2 n(n + 1)/2 distinct numbers are arranged at random into n rows. The first row has 1 number, the second has 2 numbers, the third has 3 numbers and so on. Find the probability that the largest number in each row is smaller than the largest number in each row with more numbers. Solution
: 2 n /(n+1)! . Let the probability be p n . The largest number must go into the last row. The probability of that happening is n/( n(n+1)/2 ) = 2/(n+1). It is then of no consequence what other numbers go in the last row. But the (n-1)n/2 numbers that go in the other n-1 rows must meet the criterion for n-1. The probability of that happening is p n-1 . Hence p n = 2 p n-1 /(n+1). Also p 1 = 1. So by a trivial induction p n = 2 n /(n+1)! . 22nd CanMO 1990 © John Scholes jscholes@kalva.demon.co.uk 3 Aug 2002