Competition problem — Number theory

Library / /172 of 520

Number theory Difficulty 5.0 AIME, harder Find the answer

For the integer $n(n \geqslant 4)$ , find the smallest integer $f(n)$ , such that for any positive integer $m$ , any $f(n)$ -element subset of the set $\{m, m+1, \cdots, m+n-1\}$ contains at least 3 pairwise coprime elements.

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

When $n \geqslant 4$ , for the set $M=\{m, m+1, m+2, \cdots, m+n-1\}$ , if $2 \mid m$ , then $m+1, m+2, m+3$ are pairwise coprime; if $2 \nmid m$ , then $m, m+1, m+2$ are pairwise coprime.

Thus, in all $n$ -element subsets of $M$ , there are at least 3 elements that are pairwise coprime. Therefore, $f(n)$ exists, and $f(n) \leqslant n$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.