$ S$ is a non-empty subset of the set $ \{ 1, 2, \cdots, 108 \}$, satisfying: (1) For any two numbers $ a,b \in S$ ( may not distinct), there exists $ c \in S$, such that $ \gcd(a,c)=\gcd(b,c)=1$. (2) For any two numbers $ a,b \in S$ ( may not distinct), there exists $ c' \in S$, $ c' \neq a$, $ c' \neq b$, such that $ \gcd(a, c') > 1$, $ \gcd(b,c') >1$. Find the largest possible value of $ |S|$.
Problem
Source: China TST 2004 Quiz
Tags: number theory unsolved, number theory
HARDMATH
24.10.2014 05:12
Is solution 76
Pathological
21.08.2019 04:34
We claim that the maximum value is $\boxed{79}.$
Let $T$ be the set of positive integers less than or equal to $108$ which have either $1$ or $2$ prime divisors among the set $\{2, 3, 5, 7, 11\}.$ If we consider $(T / \{55, 77\}) \cup \{30, 60, 90, 42, 84\},$ then we obtain a construction for $79.$
Let us now show that this is optimal.
Lemma 1. There are at most $2$ primes in $S$ which are $>7.$
Proof. Suppose that primes $p_1, p_2 > 7$ were both in $S$. Apply the second condition on them, contradiction.
$\blacksquare$
Lemma 2. $1 \notin S$.
Proof. Apply the second condition on $a = b = 1,$ contradiction.
$\blacksquare$
At this point, we have obtained with Lemmas $1$ and $2$ a bound of $108 - 1 - 23 = 84$.
By Lemma $1$, we may now consider only the following two cases:
Case 1. There is not a prime $p > 7$ in $S.$
Then, among the pairs $(6, 35), (10, 21), (14, 15), (2, 105), (3, 70), (5, 42), (7, 30)$ at least one in each pair is not in $S$. Indeed, if both of the numbers in one of the pairs was present, then applying the first condition on them would yield that some element in $S$ has only prime divisors $>7$, contradiction. This decreases the previous upper bound of $84$ to $84-7 = 77 < 79$, so this case is resolved.
Case 2. There is a prime $p > 7$ in $S.$
Let us first examine the subcases where one of $2, 3$ is not in $S.$ If $2 \notin S$, then either one of $4, 8, 16, 32, 64$ is or $|S| \le 79.$ If some power of $2$ is in $S$, then it is easily verified that we can simply add $2$ to $S$ without causing any harm. Hence, we can assume WLOG that $2 \in S.$
If $3 \notin S$, then if one of $9, 27, 81$ is, we can similarly just add $3$ to $S.$ Otherwise, let's examine the case where $3, 9, 27, 81 \notin S.$ Then, it's clear that either $|S| \le 79$, or $S \cup \{9, 27, 81\}$ is comprised of all composites, $2$, $5$, $7$, and $p$. In the former case, we win. In the latter case, applying the second condition on $7$ and $p$ yields that $7p \le 108$, and so therefore applying the first condition on $10$ and $7p$ yields a contradiction.
As a result, we may now only examine the subcases where $2, 3 \in S.$ By similar logic as before, if there exists any power of $5$ in $S$, we can assume WLOG that $5 \in S$, and similarly for $7$. We now have the following four subcases:
Subcase 1. $2, 3 \in S$ but $5, 7 \notin S$
Then we have from our assumption that $5, 25, 7, 49 \notin S.$ Now, we know that either $|S| \le 79$, or $S \cup \{5, 7, 25, 49\}$ consists exactly of all composites, $2$, $3$, $5$, $7$, and $p$. In the former case, we win. Otherwise, by applying the second condition on $3$ and $p$, we know that $3p \le 108.$ Therefore, as $3p$ is composite, we have that $3p \in S.$ Thus, as $70$ is also composite, applying the first condition on $70$ and $3p$ yields a contradiction.
Subcase 2. $2, 3, 5 \in S$ but $7 \notin S$
Then we have from our assumption that $7, 49 \notin S.$ By applying the second condition on $5, p$, we know that $5p \le 108.$ Now, in each of the pairs $(6, 5p), (10, 3p), (15, 2p)$ at least one number is not in $S$ (otherwise just apply the first condition to obtain a contradiction). Together with $7$ and $49$, these improve the previous bound of $84$ by $5$ to $79$, and so we're done here.
Subcase 3. $2, 3, 7 \in S$ but $5 \notin S$
Then we have from our assumption that $5, 25 \notin S.$ By applying the second condition on $7, p$, we know that $7p \le 108.$ Now, in each of the pairs $(6, 7p), (14, 3p), (21, 2p)$ at least one number is not in $S$ (otherwise just apply the first condition to obtain a contradiction). Together with $5$ and $25$, these improve the previous bound of $84$ by $5$ to $79$, and so we're done here.
Subcase 4. $2, 3, 5, 7 \in S$
By applying the second condition on $7, p$, we know that $7p \le 108.$ Now, in each of the pairs $(30, 7p), (42, 5p), (35, 6p), (70, 3p), (105, 2p)$ at least one number is not in $S$ (otherwise just apply the first conditionto obtain a contradiction). These five pairs improve our previous bound of $84$ by $5$ to $79$, and so we're done here.
As we've exhausted all subcases, we are done in Case $2$.
As we've exhausted both cases, we have shown that $|S| = 79$ is optimal, and so we conclude that the answer is indeed $\boxed{79}.$
$\square$