Problem / Question
Introduction
Some
enthusiastic student posted this “deranged” question on Facebook. It is taken from the Singapore Math Kangaroo Contest. The question involves derangements, which does not appear in any syllabus in Singapore
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
