Switch On
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?
Age
14 to 16
Challenge level
Problem
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?
If you liked this problem, here is an NRICH task that challenges you to use similar mathematical ideas.
Student Solutions
Clearly there must be at least two "on" switches.
If there are two "on" switches and three "off" switches then they can only be set in one way: "off","on","off","on","off".
Suppose there are three "on" switches and two "off" switches. Let's decide on the position of the "off" switches first and then fill in the gaps with the "on" switches.
We can put the "off" switches in the following places:
Positions $1$ and $3$,
Positions $1$ and $4$,
Positions $1$ and $5$,
Positions $2$ and $4$,
Positions $2$ and $5$,
Positions $3$ and $5$.
Therefore there are six ways to arrange three "on" switches and two "off" switches.
Suppose there are four "on" switches and one "off" switch. The "off" switch can be put in any position, so there are five possible ways to arrange these.
If there are five "on" switches there is exactly one way we can arrange these.
Therefore the total number of ways is $1+6+5+1=13$.
Alternatively you could represent the possibilities using a tree diagram.