2.7 Modular Arithmetic

The modulo operation—denoted as $x\%y$ or $x\bmod y$—finds the remainder of division of number $x$ by another number $y$. For simpicility, we only consider the case where $y$ is a positive integer. For example, $5\%3=2$. An intuitive property of modulo operation is 24that if $x_1\%y=x_2\%y$, then $(x_1-x_2)\%y=0$. From this property we can also show that $x\%y$, $(x+1)\%y$, $\cdots$, and $(x+y-1)\%y$ are all different numbers.

Prisoner problem

One hundred prisoners are given the chance to be set free tomorrow. They are all told that each will be given a red or blue hat to wear. Each prisoner can see everyone else’s hat but not his own. The hat colors are assigned randomly and once the hats are placed on top of each prisoner's head they cannot communicate with one another in any form, or else they are immediately executed. The prisoners will be called out in random order and the prisoner called out will guess the color of his hat. Each prisoner declares the color of his hat so that everyone else can hear it. If a prisoner guesses correctly the color of his hat, he is set free immediately; otherwise he is executed.

They are given the night to come up with a strategy among themselves to save as many prisoners as possible. What is the best strategy they can adopt and how many prisoners can they guarantee to save?¹⁴

Solution: At least 99 prisoners can be saved.

The key lies in the first prisoner who can see everyone else’s hat. He declares his hat to be red if the number of red hats he sees is odd. Otherwise he declares his hat to be blue. He will have a 1/2 chance of having guessed correctly. Everyone else is able to deduce his own hat color combining the knowledge whether the number of red hats is odd among 99 prisoners (excluding the first) and the color of the other 98 prisoners (excluding the first and himself). For example, if the number of red hats is odd among the other 99 prisoners. A prisoner wearing a red hat will see even number of red hats in the other 98 prisoners (excluding the first and himself) and deduce that he is wearing a red hat.

The two-color case is easy, isn’t it? What if there are 3 possible hat colors: red, blue, and white? What is the best strategy they can adopt and how many prisoners can they guarantee to save?¹⁵

Solution: The answer is still that at least 99 prisoners will be saved. The difference is that the first prisoner now only has 1/3 chance of survival. Let’s use the following scoring system: red=0, green=1, and blue=2. The first prisoner counts the total score for 25the rest of 99 prisoners and calculates $s\%3$. If the remainder is 0, he announces red; if the remainder is 1, green; 2, blue. He has 1/3 chance of living, but all the rest of the prisoners can determine his own score (color) from the remainder. Let’s consider a prisoner $i$ among 99 prisoners (excluding the first prisoner). He can calculate the total score ($x$) of all other 98 prisoners. Since $(x+0)\%3$, $(x+1)\%3$, and $(x+2)\%3$ are all different, so from the remainder that the first prisoner gives (for the 99 prisoners including $i$), he can determine his own score (color). For example, if prisoner $i$ sees that there are 32 red, 29 green and 37 blue in those 98 prisoners (excluding the first and himself). The total score of those 98 prisoners is 103. If the first prisoner announces that the remainder is 2 (green), then prisoner $i$ knows his own color is green (1) since only $104\%3=2$ among 103, 104 and 105.

Theoretically, a similar strategy can be extended to any number of colors. Surely that requires all prisoners to have exceptional memory and calculation capability.

Division by 9

Given an arbitrary integer, come up with a rule to decide whether it is divisible by 9 and prove it.

Solution: Hopefully you still remember the rules from your high school math class. Add up all the digits of the integer. If the sum is divisible by 9, then the integer is divisible by 9; otherwise the integer is not divisible by 9. But how do we prove it?

Let’s express the original integer as $a=a_n10^n+a_{n-1}10^{n-1}+\cdots+a_110^1+a_0$. Basically we state that if $a_n+a_{n-1}+\cdots+a_1+a_0=9x$ ($x$ is a integer), then the $a$ is divisible by 9 as well. The proof is straightforward:

For any $a=a_n10^n+a_{n-1}10^{n-1}+\cdots+a_110^1+a_0$, let $b=a-(a_n+a_{n-1}+\cdots+a_1+a_0)$. We have $b=a_n(10^n-1)+a_{n-1}(10^{n-1}-1)+\cdots+a_1(10^1-1)=a-9x$, which is divisible by 9 since all $(10^k-1)$, $k=1,\cdots,n$ are divisible by 9. Because both $b$ and $9x$ are divisible by 9, $a=b+9x$ must be divisible by 9 as well.

(Similarly you can also show that $a=(-1)^na_n+(-1)^{n-1}a_{n-1}+\cdots+(-1)^1a_1+a_0=11x$ is the necessary and sufficient condition for $a$ to be divisible by 11.)

Chameleon colors

A remote island has three types of chameleons with the following population: 13 red chameleons, 15 green chameleons and 17 blue chameleons. Each time two chameleons with different colors meet, they would change their color to the third color. For example, if a green chameleon meets a red chameleon, they both change their color to blue. Is it ever possible for all chameleons to become the same color? Why or why not?¹⁶

Solution: It is not possible for all chameleons to become the same color. There are several approaches to proving this conclusion. Here we discuss two of them.

Approach 1. Since the numbers 13, 15 and 17 are “large” numbers, we can simplify the problem to 0, 2 and 4 for three colors. (To see this, you need to realize that if combination $(m+1,n+1,p+1)$ can be converted to the same color, combination $(m,n,p)$ can be converted to the same color as well.) Can a combination $(0,2,4)$ be converted to a combination $(0,0,6)$? The answer is NO, as shown in Figure 2.3:

Actually combination $(1,2,3)$ is equivalent to combination $(0,1,2)$, which can only be converted to another $(0,1,2)$ but will never reach $(0,0,3)$.

Approach 2. A different, and more fundamental approach, is to realize that in order for all the chameleons to become the same color, at certain intermediate stage, two colors must have the same number. To see this, just imagine the stage before a final stage. It must has the combination $(1,1,x)$. For chameleons of two different colors to have the same number, their module of 3 must be the same as well. We start with $15=3x$, $13=3y+1$, and $17=3z+2$ chameleon, when two chameleons of different colors meet, we will have three possible scenarios:

So the pattern is preserved and we will never get two colors to have the same module of 3. In other words, we cannot make two colors have the same number. As a result, the chameleons cannot become the same color. Essentially, the relative change of any pair of colors after two chameleons meet is either 0 or 3. In order for all the chameleons to become one color, at least one pair’s difference must be a multiple of 3.