**Problem / Question**

**Introduction**

Some
enthusiastic student posted this “deranged” question on Facebook. It is taken from the Singapore Math Kangaroo Contest. The question involves Singapore before
university level.

*derangements*, which does not appear in any syllabus in
If the
problem involved a

*circular permutation*, the correct answer would have been (5 – 1)! = 4 × 3 × 2 × 1 = 24. But this is not a circular permutation, because the roads are distinguished by their different positions. If one rotates the roundabout, this would be considered a different pattern. If it were a*permutation*, the answer would have been 5! = 5 × 4 × 3 × 2 × 1 = 120. However, it is not a permutation, because the cars cannot go back to their original road in the opposite direction. That is what the Kangaroo phrase “drives less than one round” mean.
A

*derangement*is a some rearrangement in which things are not allowed to go back to their original position. If one has not learned the formula for derangements, how could this be solved?**Strategy**

We can consider simpler cases [H10] of the problem and build up the answer from
there. We may also split the problem
into two cases. [H11]

**Solution**

Let !

*n*denote the number of derangements if there are*n*cars and*n*road branches in the roundabout. [This is called the subfactorial of*n*.]
For

*n*= 1, !*n*= 0 because the car has no way but to go back on the original road.
For

*n*= 2, !*n*= 1 because the only way is for the two cars to swap.
For

*n*= 3: Car #1 has two choices: either road #2 or road #3. But it cannot end up swapping roads with any car, else the remaining car would have to go back to its original road, which is not allowed. So it is either #1 ® #2 ® #3 ® #1 or #1 ® #3 ® #2 ® #1. Therefore !3 = 2.
For

*n*= 4: Car #1 has 3 choices. For each of these choices, either it ends up (1) swapping roads with the other car, or (2) it does not swap.
Case (1): If it
swaps with the other car, then the remaining
2 cars will have !2 = 1 way.

Case (2): If car #1 goes
to some road but not swapping roads with it,
then the other 3 cars will have !3 = 2
ways to choose roads different from their original roads.

Therefore !4 =
3 × (!3 + !2) = 3 × (2 + 1) = 9.

For

*n*= 5: Car #1 has 4 choices.
Case (1): It swaps
with the other car. The remaining 3 cars
will have !3 = 2 ways.

Case (2): It does
not swap with any car. The other 4 cars
will have !4 = 9 ways.

Therefore !5 = 4
× (!4 + !3) = 4 × (9 + 2) = 44.

**Ans:**

**(B)**44.

**Remarks**

H02. Use a diagram / model (can be used for small number cases)

H03. Make a systematic list (can be used for small number cases)

H04. Look for pattern(s)

H05. Work backwards

H09. Restate the problem in
another way

H10. Simplify the problem

H11. Solve part of the problem

**Suitable Levels**

*****Lower Secondary Mathematics Competition

* University / College Combinatorics

* other syllabuses that involve derangements

* any precocious
or interested learner who is interested

## No comments:

## Post a Comment

Note: Only a member of this blog may post a comment.