Let $S=\{1,2,\ldots ,98\}$. Find the least natural number $n$ such that we can pick out $10$ numbers in any $n$-element subset of $S$ satisfying the following condition: no matter how we equally divide the $10$ numbers into two groups, there exists a number in one group such that it is coprime to the other numbers in that group, meanwhile there also exists a number in the other group such that it is not coprime to any of the other numbers in the same group.
Problem
Source: Chinese Mathematical Olympiad 1998 Problem 3
Tags: number theory unsolved, number theory
McTeague
08.01.2016 01:25
This is a bit long winded but I think it works.
Notice that $n > 49$: take $\{2,4,6,\ldots, 98\}$. We claim that $n = 50$ works.
Assume for contradiction that there exists $A \subset S$ with $|A| = 50$ which does not contain $10$ numbers satisfying the given condition. Let $B_2$ be the set of elements of $A$ divisible by $2$ and let $B_3$ be the set of elements of $A$ divisible by $3$. Notice that either $|B_2| \ge 9$ or $|B_3| \ge 9$. Indeed, if $|B_2|, |B_3| \le 8$, this gives at most $16$ elements. The rest must be $1$ or $5 \pmod 6$, of which there are $33$ in $[98]$. Then $A$ can have at most $49$ elements, a contradiction.
If $1 \in A$ or $p \in A$ for some prime $p > 50$, then we are done: take that number along with nine elements from $B_i$ for appropriate $i$. Thus, we can assume $A \cap \{1, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97\} = \varnothing$. Notice that these are each $1$ or $5 \pmod 6$. Improving on the bound from above and using a similar argument, either $|B_2| \ge 14$ or $|B_3| \ge 14$.
Now consider a prime $p$ such that $2p \le 98$ and $3p > 98$. If $p \in A$, then at worst one element $x$ in $B_i$ (for appropriate $i$) is not relatively prime to $p$. We can then choose $9$ elements from $B_i \setminus \{x\}$ along with $p$ for the set of $10$. Thus, such $p$ cannot be in $A$. We then get an even better bound of either $|B_2| \ge 16$ or $|B_3| \ge 16$.
Iterating this process, we cannot have any prime $p \ge 5$ in $A$ and either $|B_2| \ge 20$ or $|B_3| \ge 20$. Among elements of $S$ which are $1, 5 \pmod 6$, this leaves $25, 35, 49, 55, 65, 77, 85, 91, 95$. Notice that there are at most $4$ multiples of $11$ in $B_i$ and at most $7$ multiples of $7$ in $B_i$, for appropriate $i$. This leaves at least $9$ elements in $B_i$ relatively prime to $77$. Thus, $77 \not \in A$. In a similar manner we eliminate $25, 49, 85, 91, 95$.
Thus, $|A \cap (B_2 \cup B_3)| \le 3$. Since $|A| = 50$, this implies that either $|B_2| \ge 24$ or $|B_3| \ge 24$. There are at most $9$ multiples of $5$ and at most $4$ multiples of $11$ in $B_i$. Leaving at least $11$ elements of $B_i$ relatively prime to $55$. We may then choose $9$ from these $11$ along with $55$ (if $55 \in A$) to get an appropriate set of $10$. Thus, $55 \not \in A$. In a similar manner, $65 \not \in A$.
One last time, we improve on our bounds for $|B_2|, |B_3|$. Since now $|A \cap (B_2 \cup B_3)| \le 1$ (using $35$), either $|B_2| \ge 25$ or $|B_3| \ge 25$. There are at most $7$ multiples of $7$ and at most $9$ multiples of $5$ in $B_i$, leaving at least $9$ elements of $B_i$ to pair with $35$ (if $35 \in A$). Thus, $35 \not \in A$ and all elements of $A$ are either multiples of $2$ or $3$.
Let $B_{3}^{'}$ denote the set of elements of $A \cap S$ which are divisible by $3$ but not by $2$. Since $|B_{3}^{'}| \le 16$, in fact $|B_2| \ge 34$. Notice also that $|B_2| \le 49$ so at least one element of $A$ is not even. Let $y$ be one such element. We now estimate an upper bound on the number of elements of $B_2$ which are not relatively prime to $y$, which we denote by $f(y)$. If $y$'s prime factorization contains only one prime ($3$), then $f(y) \le 16$. If $y$'s prime factorization contains two primes, then $f(y) \le 16+9-3 = 22$. $y$'s prime factorization can contain no more than two primes since $3 \cdot 5 \cdot 7 > 98$. Thus, $f(y) \le 22$, leaving at least $12$ elements of $B_2$ relatively prime to $y$. Choose any $9$ of these along with $y$. This exhausts all cases, a contradiction.