Competition problem — Combinatorics

Library / /11 of 19

Combinatorics Difficulty 6.2 National olympiad Prove it Mongolia

Given $a_1, a_2, ..., a_{2009}$ different natural numbers such that if two of any three numbers are not relatively prime, then one of the two numbers is not relatively prime to the third. If there do not exist 50 numbers that are relatively prime pairwise, then prove that there exist 40 numbers such that are not relatively prime pairwise.
(proposed by B. Bayasgalan)

Solution

Let us construct graph $G$ with vertices $a_1, a_2, ..., a_{2009}$ ; if two numbers are not relatively prime, then connect them with an edge. Then, the resulting graph $G$ will not have a subgraph that has three vertices and a single edge, by the given of the problem. Therefore, vertices of the graph $G$ can be divided into disjoint sets of independent vertices. Hence, $G$ is a $k$ -partite graph with $2009$ vertices. Each arbitrary set of independent vertices will contain no more than $49$ vertices. The least number of disjoint sets is $\frac{2009}{49} = 41$ . From each of the sets, select an element each, then $41$ numbers that are pairwise relatively prime can be selected.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.