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 (**1**st day in week) repeats every 2 days : (mod 2)

d(M) – 1 = 0 (mod 2)

=> d(M) = 1 (mod 2)

Similarly, Prof W (**3**rd 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, t****hus 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=7**

X = 10.7.**2** + 3.7.**1** + 3.10.**7** = 140 + 21 + 210

**X = 371 (mod 3.10.7) = 371 (mod 210) =161 (mod 210)**

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 = 371 (mod 12.5.7) = 371 (mod 420)**

Notice 2 | 420,

we can simplify the solution:

X = 371 (mod 420 ÷2) = 371 (mod 210)

**X = 161 (mod 210)**

(Source : Excellent Video on **CRT Techniques**)

**Easy CRT** :

(**Reference only: Revision**)

**CRT Definition**:

Reblogged this on Singapore Maths Tuition and commented:

Any short-cut method ? Yes, by L.C.M…

Reblogged this on Chinese Tuition Singapore.