Han Xin Counts Soldiers: my notes on a 6 minute Ma Yuchun video.

Han Xin was a famous general in the Han empire, but Ma Yu Chun's story seems apocryphal. Once when Han Xin was in a precarious position pursued by enemy Chu forces, he was unsure of how many of his troops remained. To count them he asked the soldiers to line up in rows of three and learned there were two left over, then they lined up in rows of five and three were left over, finally they lined up in rows of seven and two were left over. Then he calculated his troop strength as 1073, much greater than the Chu forces which they then defeated. How did he conclude that he had 1073 soldiers?

In Sunzi Suanjing, the mathematical classic of Sunzi, written sometime in the third to fifth century CE, the same problem in the Hanxin Counts Soldiers is posed in less dramatic language: if we have an unknown number of somethings but when we count them by threes there is a remainder of 2, when we count by fives there is a remainder of 3, and when we count by sevens there is a remainder of 2, How many things are there?

In mathematical language, we have three equations in x: x÷3≡2; x÷5≡3; x÷7≡2. Solve for x.

We can rewrite these equations in terms of terms of auxiliary variables a, b, and c: x=3a+2; x=5b+3; x=7c+2.

One way to solve this is to use enumeration to find the smallest as, bs, and cs that solve the equation:

x÷3≡2 (or x=3a+2) has the smallest solutions: 2, 5, 8, 11, 14, 17, 20, 23, 26, ….

Similarly, x÷5≡3 (or x=5b+3) has the smallest solutions: 3, 8, 13, 18, 23, 28, ….

And, x÷7≡2 (or x=7c+2) has the smallest solutions: 2, 9, 16, 23, 30, ….

Since 23 is the smallest solution in each enumeration, it is the smallest solution.

Ma Yu Chun also shows that we can use the smallest solution of the first two equations, namely, 8 as the least common multiple of 3 and 5. This yields the combined requirement of solutions to x÷15≡8 (or x=15d+8). Enumerating these solutions gives 8, 23, 38, …. Similarly we find that 23 matches the third enumeration of x÷7≡2 (or x=7c+2) with the combination of the first two.

There is a better way which Ma Yu Chun calls the contruction method. Let's look for common multiples s of 5 and 7 which have remainder 1 when divided by 3. That is what numbers s (35d for d=1,2,…) such that s÷3≡1. By enumeration we find that 35≡2 (mod 3), but s=70≡1 (mod 3). Since we really wanted numbers whose remainder on division by 3 is 2, we double 70 to 140 which we now know must be a common multiple of 5 and 7 which is congruent to 2 on division by 3.

Alternatively, we can look for common multiples of 3 and 7 whose remainder on division by 5 is 1. We immediately find t=21≡1 (mod 5). Since we wanted a remainer of 3 modulo 5, we multiply 21*3=63.

Again, we can look for common multiples of 3 and 5 whose remainder on division by 7 is 1. We immediately find h=15≡1 (mod 7). Since we wanted a remaineder of 2 modulo 7, we multiply 15*2=30.

So 2s+3t+2h=233 is a solution for x in our system of equations.

We can find the smallest solution by subtracting multiples of the least common multiple of 3, 5, and 7 (which is 105). 233-105=128 and 128-105=23. Since we cannot subtract 105 from 23 and remain positive, 23 is the smallest solution as we learned from our enumeration above.

Since 23+10*105=1073, this is a plausible way in which Han Xin could have calculated that he had 1073 soldiers. But he also might have had only 548 soldiers or even only 443 soldiers. Did he really use mathematics here?

From the free on-line course: Combinatorial Mathematics with Ma Yuchun of Tsinghua University

Lecture: Week 6, Inclusion-Exclusion Principle and Pigeonhole Principle, Pigeonhole Principle, Hanxin counts soldiers