Prove that every selection of $1325$ integers from $M=\{1, 2, \cdots, 1987 \}$ must contain some three numbers $\{a, b, c\}$ which are pairwise relatively prime, but that it can be avoided if only $1324$ integers are selected.
Problem
Source:
Tags: pigeonhole principle, number theory, relatively prime
28.05.2009 19:14
$ 1324$ can be achieved by choosing the mutiples of either $ 2$ or $ 3$ but for the part of $ 1325$,I can't come up with a construction of pigeonholes just like official solution for IMO 1991 problem 3.I think the proofs should be similar,but $ 1987$ is too big to check
11.05.2014 09:21
Looking at the solution at http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366445&sid=9556e86316f70b641e898387570238ac#p366445, we see the answer to the general question Let $M=\{1, 2, \ldots, N\}$, let $2=p_1<p_2 < \cdots < p_n \leq N < p_{n+1}$ be the start of the sequence of primes, and let $1\leq k < n$. Determine the largest size a subset of $M$ may have, so it does not contain $k+1$ pairwise relatively prime elements is given by the size of the subset containing all multiples of $p_1,p_2,\ldots,p_k$, which can be computed by PIE. So the difficulty is bigger when $k$ is large, not when $N$ is large.
26.04.2016 09:26
$Great$ work