21st CanMO 1989 Problem 1 How many permutations of 1, 2, 3, ... , n have each number larger than all the preceding numbers or smaller than all the preceding numbers? Solution
: 2 n-1 . Let the number of permutations be a(n). The last number must be 1 or n, for if it is k with 1  k. If the last number is n, then the preceding numbers satisfy the conditions for a permutation of 1, 2, ... , n-1. So there are a(n-1) permutations with last number n. Similarly, there are a(n-1) with last number 1. Hence a(n) = 2a(n-1). But a(2) = 2, so a(n) = 2 n-1 . 21st CanMO 1989 © John Scholes jscholes@kalva.demon.co.uk 21 June 2002