This question was asked in the Indian Regional Mathematics Olympiad 2019 and was stated as:
Suppose 91 distinct positive integers greater than 1 are given such that there are at least 456 pairs among them which are relatively prime. Show that one can find four integers $\ a, b, c, d$ among them such that $\ gcd(a, b) = gcd(b, c) = gcd(c, d) = gcd(d, a) = 1 $
This appears to be a problem which involves the use of Pigeon-Hole Principle. However, I couldn't derive a straightforward situation of 'pigeons and boxes' that would imply a conclusion which is asked for.
Another attempt involved noticing the fact that this problems asks $\ (a, b), (b, c), (c, d), (d, a) $ to be equal to 1, which appear to be the sides of a quadrilateral ABCD. Suppose we construct 91 points in plane, no 3 of which are collinear. Each of these points represent the 91 distinct integers in our set. We show that 2 of these integers are co-prime by drawing a line connecting the respective points. We need to show that there exists a quadrilateral in this plane.
For 456 pairs to exists, there must be a point from which more than $\ [(456 * 2 – 1) / 91] $ lines are drawn, where $\ [x] $ represents Greatest Integer Function. Therefore, there must be a point from where at least 11 lines are drawn. However, I couldn't venture further to arrive at the desired conclusion. Maybe we can apply this argument recurringly in some way to the remaining set of points?
Any help would be appreciated.
Best Answer
This is actually a graph theoretic problem! The use of GCD doesn't factor in at all. [If someone with more reputation could tag this with the relevant tags, that would be great.] Consider a graph with these 91 numbers as vertices, where two are connected iff they are coprime. Then we want to show this graph cannot be squarefree, ie it must contain a 4-cycle. There is apparently a well-known result in extremal graph theory where any quadrilateral-free graph on $n$ vertices has at most $$\frac{n}{4}(1 + \sqrt{4n - 3})$$ edges. Note that for $n = 91$ this implies your graph can have at most 455 edges and remain squarefree, forcing our 456-edge graph to have a 4-cycle. S. Jukna has a slick proof here which he attributes to Reiman, though Reiman's original paper is in German and seems to be a more general (and much more complicated) result.