BMO 1967 Problem 11 The streets for a rectangular grid. B is h blocks north and k blocks east of A. How many shortest paths are there from A to B? Solution
: (h + k)!/( h! k! ). A shortest path must involve h moves north and k moves east, a total of h + k moves. So there is a (1, 1) correspondence between shortests paths and subsets size h taken from the set 1, 2, 3, ... , (h + k). [Move i is north if i is in the subset and east otherwise.] But there are (h + k) C h = (h + k)! /( h! k! ) such subsets. 3rd BMO 1967 (C) John Scholes jscholes@kalva.demon.co.uk 30 Aug 2000