Infinitely Many Co-Primes

Here is a two-step game between Alice and Bob.

  • Alice picks S N S \subseteq \mathbb{N} , an infinite set of positive integers, and sends them to Bob.
  • Bob picks an infinite subset T S T \subseteq S .

Bob wins if any one of the two conditions hold:

  1. Any two elements of T T are coprime.
  2. No two elements of T T are coprime.

Alice wins if Bob does not.

Who has a winning strategy?

Alice Bob

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

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 ) G = (V, E) on countably infinite vertices, with each edge e E e \in E colored with a color from a finite set of colors, there is a subset W V W \subseteq V such that the graph induced by W W is monochromatic.

Now, assuming the theorem above, Bob's winning strategy is simple. He constructs a complete graph on S 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 N \mathbb{N} .

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

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

Let V 0 = N V_0 = \mathbb{N} . Now, supposing that V i 1 V_{i-1} is defined, pick x i x_i to be the smallest element of V i 1 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 V_{i-1} the edge to which from x i x_i are of the same color. Pick this set to be V i V_{i} .

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

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

Again, this is not hard. Associated with each vertex i A i \in A , there is a color, namely the color such that all the vertices j > i A 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 A B \subseteq A such that all the "associated" colors (as explained above) are the same.

And this concludes the proof.

R Mathe
May 26, 2018

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

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

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

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...