Here is a two-step game between Alice and Bob.
Bob wins if any one of the two conditions hold:
Alice wins if Bob does not.
Who has a winning strategy?
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.
Theorem (Ramsey). For any k , n ∈ N with k , n > 1 and for any F : [ N ] k ⟶ n there exists an inifinite subset H ⊆ N , such that F ∣ [ H ] k is constant.
Clearly, one can replace N in the above by any countably infinite set.
Application. Player I chooses S ⊆ N infinite. Let g : N ⟶ S be any bijection. Define F : [ A ] 2 ⟶ 2 via F ( { i , j } ) = 1 iff g cd ( i , j ) = 1 . By the Ramsey-Theorem, there exists B ⊆ A infinite such that F ∣ [ 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 g cd ( m , n ) = F ( { m , n } ) = c for all m , n ∈ 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.
Problem Loading...
Note Loading...
Set Loading...
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.
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 N .
Step I We find A ⊆ N such that for each i ∈ A , the edges to every j ∈ 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 = 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 { x 1 , x 2 , ⋯ } . This set, by construction, satisfies the property we wanted A to satisfy.
Step II We find B ⊆ A such that the graph induced by B is monochromatic.
Again, this is not hard. Associated with each vertex i ∈ A , there is a color, namely the color such that all the vertices j > i ∈ 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 such that all the "associated" colors (as explained above) are the same.
And this concludes the proof.