3rd Mexico 1989 Problem B3 How many paths are there from A to B which do not pass through any vertex twice and which move only downwards or sideways, never up?
2 6 6! = 46080 Solution If the large triangle has side n and top vertex A, let a n be the number of ways of getting from A to the bottom row (the path stops as soon as it gets to the bottom row). Note that a n is also the number of ways of getting from A to the bottom left-hand vertex, because having reached the bottom row there is only one allowed path to the bottom left-hand vertex. Obviously, a 1 = 2. Now consider an+1. There are an ways to get to the bottom row but one. Now there is just one way of getting to any vertex on the bottom row and there are then 2 ways to get to the row below. So a n+1 = 2(n+1)a n . Hence a 6 = 2 5 6!a 1 = 2 6 6!. 3rd Mexican 1989 © John Scholes jscholes@kalva.demon.co.uk 25 February 2004 Last corrected/updated 25 Feb 04