Coloring the integers

The answers are $3, 0, 4, 4$ .

To start, we will begin with two lemmas.

Lemma 1 : If $A$ is a set of integers such that any two of them have difference that is in $S$ , then we need at least $|A|$ colors.

This is straightforward: if we use less than $|A|$ colors, then by Pigeonhole Principle , two integers in $A$ will have the same color. By definition of $A$ , these two integers have difference that is in $S$ , contradicting the property in the problem (two integers whose difference is in $S$ may not have the same color).

Lemma 2 : If no element in $S$ is divisible by $k$ , then we need at most $k$ colors.

To prove this, we simply need to exhibit one coloring satisfying this property. This is obtained by simply coloring every integer by its remainder modulo $k$ . Two integers that have the same color must then have difference that is divisible by $k$ , and thus not in $S$ by assumption, so our coloring is valid.

With these two lemmas, we can now find the answers to the first three problems.

First problem : We use Lemma 1 with $A = \{0, 1, 2\}$ to show that we need at least three colors. We use Lemma 2 with $k = 3$ to show that we need at most three colors. This completes the proof, showing that $f(S) = 3$ in this case.

Second problem : We use Lemma 1 with $A$ being the set of even integers. Yes, our $A$ is infinite, so we cannot complete it in any finite number of colors. Thus $f(S) = 0$ in this case.

Third problem : We use Lemma 1 with $A = \{0, 2, 5, 7\}$ to show that we need at least four colors. We use Lemma 2 with $k = 4$ to show that we need at most four colors. This completes the proof, showing that $f(S) = 4$ in this case.

Fourth problem : This is the only problem that is different in nature.

First, we exhibit a simple coloring with four colors. Color them as $\ldots, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 2, 2, 3, 3, 4, 4, \ldots$ . We can easily show that two integers of the same color will have a difference that is congruent to $0, 1, 7 \pmod 8$ , while elements of $S$ are congruent to $2, 3, 4, 5 \pmod 8$ , so no two integers of the same color will have a difference in $S$ .

Showing that we need four colors is more difficult. To do this, we will show that three colors is not enough.

Suppose it is enough. We first use Lemma 1 on $A = \{0, 2, 4\}$ to see that we need three colors, but more importantly, that $0, 2, 4$ are all of different colors. Thus, by changing the names of the colors, we may assume that $0, 2, 4$ gets the color red, green, blue in that order. Now, 6 must be red (because $6-2, 6-4 \in S$ , 2 is green, and 4 is blue), and 8 must be green (because $8-4, 8-6 \in S$ , 4 is blue, 6 is red). Then, 3 and 5 must both be blue (because $3-0, 8-3, 5-0, 8-5 \in S$ , 0 is red, 8 is green). But now 3 and 5 have the same color while their difference 2 is in $S$ , contradiction.

Thus three colors is not enough; we need four colors. So $f(S) = 4$ in this case. This completes the problem.

---

Bonus: Find $f(S)$ for the following sets:

1. $S = \{1, 2, 6, 24, 120, \ldots\}$ is the set of factorial numbers.
2. $S = \{1, 4, 9, 16, 25, \ldots\}$ is the set of square numbers.