Infinitely Many Co-Primes

Although the problem has been formulated in a number theoretic fashion, the problem can be solved in a more general setting.

We'll use the following theorem to prove the result.

Theorem: Given a complete graph $G = (V, E)$ on countably infinite vertices, with each edge $e \in E$ colored with a color from a finite set of colors, there is a subset $W \subseteq V$ such that the graph induced by $W$ is monochromatic.

Now, assuming the theorem above, Bob's winning strategy is simple. He constructs a complete graph on $S$ , the set given by Alice, and colors an edge blue if the two incident numbers are coprime, and red otherwise. The statement of the theorem is just the guarantee that Bob has a winning strategy.

---

Now, we turn to the proof of the theorem.

Without loss of generality, we can assume that the vertices of the graph are $\mathbb{N}$ .

Step I We find $A \subseteq \mathbb{N}$ such that for each $i \in A$ , the edges to every $j \in A$ satisfying $i < j$ are of the same color.

This is not hard. We only have to carefully pick elements of $A$ in an inductive fashion. We'll inductively define a sequence of vertices $x_i$ , a sequence of infinite sets of vertices $V_i$ as follows:

Let $V_0 = \mathbb{N}$ . Now, supposing that $V_{i-1}$ is defined, pick $x_i$ to be the smallest element of $V_{i-1}$ . Now, since there are only finitely many colors, there must be some color such that there are an infinite number of elements in $V_{i-1}$ the edge to which from $x_i$ are of the same color. Pick this set to be $V_{i}$ .

Now, consider the collection $\left \{x_1, x_2, \cdots \right \}$ . This set, by construction, satisfies the property we wanted $A$ to satisfy.

Step II We find $B \subseteq A$ such that the graph induced by $B$ is monochromatic.

Again, this is not hard. Associated with each vertex $i \in A$ , there is a color, namely the color such that all the vertices $j_{>i} \in A$ satisfy the property we mentioned in Step I. But there are only finitely many colors to begin with. So, we can pick a subset $B \subseteq A$ such that all the "associated" colors (as explained above) are the same.

And this concludes the proof.

Theorem (Ramsey). For any $k,n\in\mathbb{N}$ with $k,n>1$ and for any $F:[\mathbb{N}]^{k}\longrightarrow n$ there exists an inifinite subset $H\subseteq\mathbb{N}$ , such that $F\mid [H]^{k}$ is constant.

Clearly, one can replace $\mathbb{N}$ in the above by any countably infinite set.

Application. Player I chooses $S\subseteq\mathbb{N}$ infinite. Let $g:\mathbb{N}\longrightarrow S$ be any bijection. Define $F:[A]^{2}\longrightarrow 2$ via $F(\{i,j\})=1$ iff $\gcd(i,j)=1$ . By the Ramsey-Theorem, there exists $B\subseteq A$ infinite such that $F\mid[B]^{2}$ is constant (say equal to some $c$ ). Player II shall pick this set (requires potentially the Axiom of Choice). This infinite subset satisfies $\gcd(m,n)=F(\{m,n\})=c$ for all $m,n\in B$ . In particular, if $c=1$ , all pairs of elements in $B$ are coprime, and if $c=0$ , all pairs of elements in $B$ are not coprime. Hence Player II will always win. Thus this is a winning strategy.