سوال ۱۱۸ کنکور ارشد علوم کامپیوتر ۱۳۹۸

We must guarantee that two of the chosen numbers share a common factor (i.e. their $\gcd$ exceeds $1$, meaning they are not coprime). This is a worst-case / pigeonhole question, so we first find the largest subset of $\{1,2,\ldots,10\}$ that we could pick while staying safe — a set in which every pair is coprime ($\gcd = 1$). One more than that size is the answer.

Largest pairwise-coprime subset

The only primes up to $10$ are $2, 3, 5, 7$. Group the numbers $2,\ldots,10$ by their prime factors:

If two chosen numbers share any prime, their $\gcd > 1$. So in a pairwise-coprime set, each prime may be "used" by at most one chosen number. That allows at most one number contributing the factor $2$, one contributing $3$, one contributing $5$, and one contributing $7$ — four numbers — plus the number $1$, which is coprime to everything.

A concrete maximum pairwise-coprime set is $\{1,\ 2,\ 3,\ 5,\ 7\},$ which has $5$ elements and contains no pair with a common factor.

Apply the pigeonhole bound

• Choosing $5$ numbers is not enough: the set $\{1,2,3,5,7\}$ is a counterexample with all pairs coprime.
• Choosing $6$ numbers forces failure of the "all coprime" structure: with only $4$ available primes and the single number $1$, any $6$th distinct number must reuse a prime already represented, creating a pair with $\gcd > 1$.

Hence the minimum guaranteeing count is $1 + (\text{max coprime size}) = 1 + 5 = 6.$

The answer is 6 (option 2).

Pitfall: Don't forget to include $1$ in the safe set — it is coprime to everything, so it enlarges the worst case from $4$ to $5$, which is exactly why the threshold is $6$ and not $5$.