[OlymLSec_20160109CBDR] Derangement of Cars in a Roundabout

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 before university level.

     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

     For more information regarding derangements, please refer to here and here.

Heuristics Used

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