JMC 2006 Q17
17. In how many different ways can a row of five “on/off” switches be set so that no two adjacent switches are in the “off” position?
- A 5
- B 10
- C 11
- D 13
- E 15
Junior Mathematical Challenge 2006, Question 17. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: D 13
Clearly, there must be a minimum of two ‘on’ switches. Two ‘on’ switches and three ‘off’ switches may be set in only one way: ‘off’, ‘on’, ‘off’, ‘on’, ‘off’. Three ‘on’ switches and two ‘off’ switches may be set in six different ways. Four ‘on’ switches and one ‘off’ switch may be set in five different ways. Finally, five ‘on’ switches can be set in just one way. So there are 13 ways in all.
(Note: it is left as an exercise for the reader to show that if that there are n switches then the number of different ways in which they may be set so that no two adjacent switches are in the ‘off’ position is the (n + 2)th term of the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, …)
Solution © UK Mathematics Trust, from the JMC 2006 solutions.