D%29 Combinatorics - Worksheet 3

Combinatorics Worksheet 3 – Recurrence Relations All SMC, BMO and Mentoring problems are © UKMT (www.ukmt.org.uk) 1. A rabbit is moving from the top-right corner to the bottom-left corner of a 5 x 5 grid. Each move, the rabbit can hop right, or hop down. The state can be defined in terms of two variables, the number of remaining squares right r, and the remaining squares down d. Since the right and down actions reduce r and d by 1 respectively, the recurrence is F(r,d) = F(r-1,d) + F(r,d-1), with base cases F(k,0) = F(0,k) = 1 for any k. Use this information to fill out the table for F values: r=4

r=3

r=2

r=1

r=0

d=4 d=3 d=2

1

d=1 d=0

1

1

2. Recall the frog problem in which a frog has n lily pads in front of it, and can either ‘hop’ on each step (onto the next lily pad) or ‘skip’ (jumping onto the pad 2 in front of it). Now let’s modify the problem such that the Lance the frog (on performance enhancing drugs) can jump ANY number of lily pads, including immediately to the end (but the jump must be at least one pad). a. Form a recurrence relation for the number of ways of getting to the end when there are n lily pads. b. By considering the lily pads each as slots, give an equivalent simple position-to-term formula for the number of ways the frog can get into the end. c. Hence, find the number of ways when there are 20 lily pads. 3. You have a bathroom of n by 2 units, and wish to tile it with 2 by 1 tiles. The diagram below indicates two possible tilings when n = 5. By considering the possible tilings (i.e. actions) at the end of the bathroom, form a recurrence relation. Hence find the possible number of

www.drfrostmaths.com

arrangements when n = 10.

4. (BMO Round 1) Twelve people are seated around a circular table. In how many ways can six pairs of people engage in handshakes so that no arms cross? (Nobody is allowed to shake hands with more than one person at once). [Hint: Focus on the possible actions of one particular person, and how this divides the table into 2 smaller but similar problems] 5. Optional: (BMO Round 1) A set of positive integers is defined to be wicked if it contains no three consecutive integers. We count the empty set, which contains no elements at all, as a wicked set. Find the number of wicked subsets of the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. [Hints: Let your state be where you’re considering the next available number to include (starting at 10 and going down), and make a key property of the state that you haven’t used the number immediately prior to the state (i.e. we’ve reset a ‘potential run’). Your actions are whether you include the next number in the set or not. But remember that for each action (or sequences of actions), each need to end up in a state where a run of consecutive numbers has been reset.]

www.drfrostmaths.com