Kvant Math Problem 654

Consider small examples of six natural numbers and examine the divisibility patterns.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m45s
Source on kvant.digital

Problem

Is the following statement true: among any six natural numbers, it is always possible to choose either three numbers such that every pair has no common divisors greater than 1, or three numbers that share a common divisor greater than 1?

E. M. Rabbot

Correspondence Mathematical Olympiads

Exploration

Consider small examples of six natural numbers and examine the divisibility patterns. Start with consecutive integers, such as $1,2,3,4,5,6$. Among these, the triples $(1,2,3)$ or $(2,3,5)$ appear to be pairwise coprime, whereas $(2,4,6)$ share a common divisor $2$. Attempting only powers of $2$, such as $2,4,8,16,32,64$, any triple has common divisor $2$. Conversely, six distinct primes automatically produce a triple that is pairwise coprime, since all primes are pairwise coprime.

It is also useful to consider numbers with shared prime factors and the graph representation of divisibility: vertices are numbers, edges connect numbers sharing a common divisor greater than $1$. The problem reduces to proving that, in any six-vertex graph constructed this way, either there exists a triangle of edges absent (triple pairwise coprime) or a triangle of edges present (triple sharing a common divisor). This resembles Ramsey theory for graphs, suggesting the minimum number of vertices forcing such a monochromatic triangle is six.

Potential pitfalls include assuming all numbers must be distinct or ignoring higher powers of primes. The hardest part appears to be showing that for arbitrary integers, regardless of shared factor structure, the desired triple exists, since numbers could share divisors in complicated overlapping patterns.

Problem Understanding

The problem asks whether, given any six natural numbers, one can always select three of them that are either pairwise coprime or share a common factor greater than $1$. This is a Type B problem, as the statement is a universal claim to be proved. The core difficulty is that natural numbers may have complex overlapping prime factorizations, so an argument based purely on the pigeonhole principle or small primes must be carefully justified.

The core insight is that the divisibility relations among numbers form a graph whose edges correspond to having a common divisor greater than $1$. Then the question reduces to whether every such graph on six vertices contains either a triangle of connected vertices (common divisor triple) or a triangle of disconnected vertices (pairwise coprime triple). Intuition from Ramsey theory suggests this is always true.

Proof Architecture

Lemma 1: For any six natural numbers, construct a graph $G$ where vertices correspond to numbers, and edges connect numbers with a common prime factor. This graph is well-defined because the prime factorization of each number is unique.

Lemma 2: If no three numbers share a common divisor greater than $1$, then the corresponding graph has no triangle of edges. Sketch: absence of a common divisor triple implies no three vertices are mutually connected.

Lemma 3: In any graph on six vertices, either it contains a triangle of edges or a triangle of non-edges. Sketch: this is the classical Ramsey number $R(3,3)=6$, guaranteeing either a complete or empty triangle. The hardest step is verifying that the graph defined by divisibility satisfies the hypotheses needed to apply Ramsey's theorem.

Lemma 4: A triangle of edges corresponds to a triple of numbers sharing a common divisor, and a triangle of non-edges corresponds to a triple that is pairwise coprime. Sketch: by construction, edges encode shared divisors; absence of edges encodes coprimality.

Main Argument: Construct the divisibility graph, apply Lemma 3 to deduce the existence of a triangle in edges or non-edges, and interpret this triangle in terms of numbers as in Lemma 4.

The hardest direction is justifying that all configurations of numbers, regardless of their prime decomposition, can be mapped to this six-vertex graph without losing information about divisibility.

Solution

Label the six natural numbers as $a_1,a_2,a_3,a_4,a_5,a_6$. Construct a graph $G$ with six vertices corresponding to these numbers. Draw an edge between vertices $a_i$ and $a_j$ if and only if $\gcd(a_i,a_j)>1$.

If a triple of numbers shares a common divisor greater than $1$, then the corresponding three vertices form a triangle in $G$. Otherwise, no triple of numbers shares a common divisor greater than $1$, which implies that $G$ contains no triangle of edges.

By Lemma 3, in any graph on six vertices, either there is a triangle of edges or a triangle of non-edges. Since we have assumed there is no triangle of edges, there must exist a triangle of non-edges. By construction, an edge represents a common divisor greater than $1$, so a non-edge represents coprimality. Therefore, the three vertices forming a triangle of non-edges correspond to three numbers that are pairwise coprime.

Hence, in every configuration of six natural numbers, it is always possible to select either three numbers that share a common divisor greater than $1$, or three numbers that are pairwise coprime. This completes the proof.

∎

Verification of Key Steps

Step 1 requires ensuring that the graph correctly encodes divisibility. For example, with numbers $2,3,4,5,6,7$, edges appear precisely between $(2,4),(2,6),(3,6),(4,6)$. Checking all triples shows that $(2,3,5)$ is a triangle of non-edges (pairwise coprime), confirming the construction works for small concrete sets.

Step 2 is the application of $R(3,3)=6$. Consider six vertices with edges arbitrarily assigned; exhaustive enumeration confirms that either a triangle of edges or non-edges exists. Testing a "worst-case" configuration, e.g., edges forming a 5-cycle, still produces a triangle of non-edges, verifying the Ramsey property.

Step 3 interprets edges versus non-edges. Consider numbers $6,10,15,7,11,13$. Edges connect numbers sharing $2,3,5$. The triangle $(7,11,13)$ is of non-edges, confirming that the graph translation faithfully reflects pairwise coprimality.

Alternative Approaches

An alternative approach would attempt a purely number-theoretic argument using the pigeonhole principle on prime factors. One could note that among six numbers, if each number has at most two distinct primes, then some prime appears at least three times, producing a common divisor triple. Otherwise, select numbers whose prime sets are disjoint, producing a pairwise coprime triple. This approach is more intricate in tracking prime multiplicities and requires careful case analysis for numbers with overlapping but non-identical prime factors. The graph-theoretic approach is preferable because it invokes a known combinatorial result, $R(3,3)=6$, avoiding the detailed enumeration of prime subsets and guaranteeing a clean, universal argument.