Chinese Remainder Theorem (韩信点兵) “The Problem of 6 Professors”

How to formulate this problem in CRT (Chinese Remainder Theorem, aka “韩信点兵” dated since 3rd century in China.) ?

Let d = week days {1, 2, 3, 4, 5, 6, 7} for {Monday (Prof M), tuesday (Prof t), Wednesday (Prof W), Thursday (Prof T), Friday (Prof F), saturday (Prof s), Sunday (Prof S)}

d : 1 2 3 4 5 6 [7] 1 2 3 4 5 6 [7] 1 2
M: m 0 m 0 m 0 [m] ==> fell on 1st sunday
t: – t 0 0 t 0 [0 ] t 0 0 t 0 0 [t ] ==> fell on 2nd sunday
W: – – w 0 0 0 [w] 0 0 0 w 0 0 [0] ==> fell on 1st sunday
T: – – – T T T [T] ==> fell on 1st sunday (TRIVIAL CASE!)
F: – – – – f 0 [0] 0 0 0 f 0 0 [0] 0 0 f 0 0 0 [0] 0 f 0 0 0 0 0 f [0] 0 0 0 0 f 0 [0] 0 0 0 f 0 0 [0] 0 0 f 0 0 0 [0] 0 f 0 0 0 0 [0] f 0 0 0 0 0 [f] ==> fell on 9th sunday
s: – – – – – s [0] 0 0 0 s 0 0 [0] 0 s 0 0 0 0 [s] ==> fell on 3rd sunday

The solution X (number of days counted from the first announcement by Monday professor “M”.) will be the first time all 6 professors simultaneously fall on the same Nth sunday, when ALL are compelled to omit a lecture.

[Hint]: Prof M starts on Monday (“décalage” / shift by 1 day in a week cycle), …Prof W on Wednesday (shift by 3 days in a week cycle) … a week has 7 days.

Prof M (1st day in week) repeats every 2 days : (mod 2)
d(M) – 1 = 0 (mod 2)
=> d(M) = 1 (mod 2)

Similarly, Prof W (3rd day in week) repeats at interval of 4 days : (mod 4)
d(W) – 3 = 0 (mod 4)
=> d(W) = 3 (mod 4)

Additionally, a “virtual” Prof S of Sunday (7th day in week) repeats at interval of 7 days: (mod 7)
d(S) – 7 = 0 (mod 7)
=> d(S) = 7 (mod 7) = 0 (mod 7)

The problem is reduced to solving the following 7 modular equations :

X = 1 (mod 2) … [1]
X = 2 (mod 3) … [2]
X = 3 (mod 4) … [3]
X = 4 (mod 1) = 4 ×1 = 0 (mod 1) … [4]
X = 5 (mod 6) … [5]
X = 6 (mod 5) = 1 (mod 5) … [6]
X = 0 (mod 7) … [7]

We can simplify them into only 3 equations (with co-prime mods) by elimination and combination rules.

Eliminate [4] which is trivial (useless) for any equation (mod 1).

X =3 (mod 4) .. (3) can be simplified :
since 2 | 4,
so X= 3 (mod 4÷2) = 3 (mod 2)
=> X = 1 (mod 2) which is same as (1).
=> eliminate (3), keep (1)

Similarly, equation (5):
X = 5 (mod 6) = 5 (mod 6 ÷2) = 5 (mod 3)
X = 2 (mod 3) which is same as (2).
=> eliminate (5), keep (2)

X = 1 (mod 2) … (1)
X = 6 (mod 5) = 1 (mod 5) … (6)
We can combine them by Easy CRT (since both same remainder 1):
X = 1 (mod LCM (2,5)) = 1 (mod 10) … (8)

Solve :
X = 2 (mod 3) …(2)
X = 1 (mod 10) … (8)
X = 0 (mod 7) … (7)

Check CRT Condition: 3, 10, 7 are co-primes pairwise, ie the pairs (3,10) (3,7) (10,7) are co-primes, thus we can apply CRT to solve [2], [8] & [7]:
Applying the CRT,
Mod: 3 10 7
Rem: 2 1 0
X = (10.7).u1 + (3.7).u2 +(3.10).u3 (mod 3.10.7)

(10.7).u1 = 70.u1 = (69+1).u1 = 2 (mod 3)
=> 1.u1= 2 (mod 3) => u1 =2
(3.7).u2 = 21.u2 = (20+1).u2 = 1 (mod 10)
=> 1.u2 = 1 (mod 10) => u2 = 1
(3.10).u3 = 30.u3 = (28 + 2).u3 = 0 (mod 7)
=> 2.u3 = 0 (mod 7) => u3=0
X = 10.7.2 + 3.7.1 + 3.10.0 = 140 + 21
X = 161 (mod 3.10.7) = 161 (mod 210)

\boxed {X = 161}

That is: On the (161 / 7 = ) 23rd Sunday when all 6 professors are simultaneously compelled to omit a lecture.

–2nd Method : —

If choose different [3] & [5] instead of [1] & [2]:

X = 3 (mod 4) … [3]
X = 5 (mod 6) … [5]
X = 6 (mod 5) = 1 (mod 5) … [6]
X = 0 (mod 7) … [7]
can be re-rewritten as:
X = -1 (mod 4) … [3]
X = -1 (mod 6) … [5]
X = 1 (mod 5) … [6]
X = 0 (mod 7) … [7]

[3] & [5] : LCM (4,6) = 12
By Easy CRT: X = -1 (mod 12 )
Finally, solve:
X = -1 (mod 12) … [9]
X = 1 (mod 5) … [6]
X = 0 (mod 7)… [7]
Apply the same CRT as above :
X = 161 (mod 12.5.7) = 161 (mod 420)
Notice 2 | 420,
we can simplify the solution:
X = 161 (mod 420 ÷ 2)
X = 161 (mod 210)

(Source : Excellent Video on CRT Techniques)

Easy CRT :

(Reference only: Revision)

CRT Definition:

Advertisements

2 thoughts on “Chinese Remainder Theorem (韩信点兵) “The Problem of 6 Professors”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s