[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

[H2_Expository] Integration by Parts and the “d(etail)” Heuristic

Product Rule for Integration?

     How do we integrate a product of two functions e.g. find   ò x sin x dx ?   Unlike differentiation, there are not that many general rules (e.g. the Chain Rule, the Product Rule and the Quotient Rule) that we can use for integration.  However “Integration by parts” is similar to and can be obtained from the differentiation Product Rule

Applying Integration by Parts

     But how do we use the formula?  Before you do anything, analyse and classify the functions first.  You need to choose something for the  “u”  and  something for the “dv”  or  “^dv/_dx”.  For your choice of the “^dv/_dx” part, you can use the “d(etail)” heuristic as a guide.

     “e” is for exponential functions:      e.g. e^2x, 3^x.

     “t” is for trigonometric functions:   e.g. tan x, sin 3x, cos 2x.

     “a” is for algebraic functions:         e.g. 3x³, constants, 4x – x².

     “i” is for inverse functions:             e.g. sin^-1 x, tann^-1 5x.

     “l” is for logarithmic functions:      e.g. ln x, lg x, log₂ x.

  

Here are some examples of choices for  “^dv/_dx”  and  “u” using the “d(etail)” heuristic.

Integral	Analysis	dv/dx	u
ò x sin x dx	x  is algebraic, sin x  is trigonometric, t comes before a	sin x	x
ò e-x cos x dx	e-x  is exponential, cos x  is trigonometric, e comes before t	e-x	cos x
ò x tan-1 x dx	x  is algebraic, tan-1 x  is inverse, a comes before i	x	tan-1 x
ò ln x dx = ò (ln x)(1) dx	1  is algebraic, ln x  is logarithmic, a comes before l	1	ln x

The above is actually equivalent to “liate” for the choice of  u, which is taught by many lecturers trained in American universities.  Once you have chosen  v,  the other part u  is automatically chosen,  and vice versa.  But personally, I think “d(etail)” is easier to remember: 

If you forget the details, just remember “d(etail)”!

I shall now illustrate the working of the first example with different styles of presentation.

Presentation 1 (for beginners – using “u” and “v” explicitly)

Presentation 2 (intermediate – using “pre-integration”)

With sufficient practice, the integration can be written down quickly as follows:-

Presentation 3 (advanced – for speed)

 

Remarks

     The “d(etail)” heuristic is a special one that is invented for Integration by Parts.  Like all heuristics, it is just a guideline or rule-of-thumb.  It works most of the time, but not all the time.  If you find that this does not work, you need to try different combinations of  u  and  dv.  The part chosen for “^dv/_dx” should be more easily integrable, or at least, you already know its integral.  After doing the by parts procedure, you should end up with an integral not more complicated than the original one.

Definite integrals

 

Suitable Levels

* GCE ‘A’ Levels H2 Mathematics

* revision for IB Mathematics HL

* Advanced Placement (AP) Calculus BC

* other syllabuses that involve integration by parts

* any precocious or independent learner who loves calculus