Determine the maximal size of the set $S$ such that: i) all elements of $S$ are natural numbers not exceeding $100$; ii) for any two elements $a,b$ in $S$, there exists $c$ in $S$ such that $(a,c)=(b,c)=1$; iii) for any two elements $a,b$ in $S$, there exists $d$ in $S$ such that $(a,d)>1,(b,d)>1$. Yao Jiangang
Problem
Source: Chinese Mathematical Olympiad 2003 Problem 2
Tags: number theory, prime numbers, combinatorics proposed, combinatorics
20.02.2012 14:52
the answer is $75$ consider the set $A_{i}=\left \{ x : i\mid x , x\leq100 \right \}$ then let $S=A_{2}\cup A_{3}\cup A_{5}\cup A_{7}\cup A_{11}-\left \{ 77,70,66,55 \right \}$ one can check that such $S$ satisfies the conditions for prove that this is maximum we need to check some cases but first notice that $1$ can't occur is $S$ and in $21$ prime numbers greater than $7$ we can have just one of them in $S$
08.03.2012 13:12
mlm95 wrote: the answer is $75$ consider the set $A_{i}=\left \{ x : i\mid x , x\leq100 \right \}$ then let $S=A_{2}\cup A_{3}\cup A_{5}\cup A_{7}\cup A_{11}-\left \{ 77,70,66,55 \right \}$ one can check that such $S$ satisfies the conditions for prove that this is maximum we need to check some cases but first notice that $1$ can't occur is $S$ and in $21$ prime numbers greater than $7$ we can have just one of them in $S$ 75 is not reachable, consider in your case 7 and 11, there exists no d such that (7,d)>1 and (11,d)>1. I think the answer is 72. $S=A_{2}\cup A_{3}\cup A_{5}\cup A_{7}\cup A_{11}-\left \{ 30,60,90,70,66,42,84 \right \}$
18.10.2019 03:47
The answer is $\boxed{72}.$ This is achieved by taking all things which are divisible by at least one of $2, 3, 5, 7, 11$, excluding $30, 60, 90, 42, 84, 35, 70$ and $66$. Let's now show that this is optimal. Notice that there cannot be two primes bigger than $7$, as then there is clearly no number which isn't relatively prime with any of them. If $p > 7$ were in the set, then it's easy to see that there must be at least two other multiples of $p$. Indeed, if not then there is no integer which isn't relatively prime with any of them. It's obvious that $1$ is not in the set. We consider two cases. Case 1. No primes in the set are $>7$. Then, all elements of the set have a prime divisor among $\{2, 3, 5, 7\}.$ Observe that for each of the pairs $(30, 7), (70, 3), (6, 35), (10, 21), (14, 15), (42, 5), (60, 91), (90, 77),$ we cannot have that both members of the pair are in the set. This implies that there are at most $72$ numbers in the set (do some counting!). Case 2. There is a prime $p > 7$ in the set. This case is much more involved. We will say that the set is tasty if at least one of $7, 49$ is in the set, and tangy if at least one of $5, 25$ is in the set. If the set is both tasty and tangy, then we know that there must be multiples of $7p$ and $5p$ in the set. As $5p > 50$, this means that $5p, 7p$ are in the set. This implies that $30, 60, 90$ are not in the set (since nothing in the set is relatively prime to both one $30, 60, 90$ and $7p$) and $42, 84$ are not in the set (by similar logic). Now, note that some element of the set $\{6p, 35\}$ must be excluded, since nothing in the set is relatively prime to both $6p$ and $35$. By similar logic, some element of the set $\{3p, 70\}$ is excluded. Combining the aforementioned reasoning with the fact that $1$ isn't in the set, it's easy to see that the set has size at most $72$ in this case. If the set is tasty but not tangy, then again we have $7p$ is in the set. We also again have that $30, 60, 90$ are excluded. By non-tanginess, $5$ and $25$ are both excluded. Finally, notice that each of the sets $\{5p, 42, 84\}$ and $\{3p, 70\}$ has at least one element which is excluded. Combining with the fact that $1$ is excluded, these observations give that the set has size at most $72$ in this case. Otherwise, we have that $7, 49$ are both not in the set. If a multiple of $2p$ was in the set, then $15, 30, 45, 60, 75, 90$ would all have to be excluded, since nothing in the set is relatively prime both to $15$ and to $2p.$ This is already enough to imply that the set has size at most $72.$ Hence, no multiples of $2p$ are in the set. If a multiple of $3p$ was in the set, then we'd have that $10, 20, 30, 40, 50, 60, 70, 80, 90$ are all excluded, since nothing in the set is relatively prime to both $10$ and $3p.$ This is again enough to imply that the set has size at most $72.$ Hence, suppose that all multiples of $3p$ or $2p$ are excluded. Since there are at least two other multiples of $p$ in the set (other than $p$), we know from $10p > 100$ that $5p, 7p$ are both in the set. This means that $30, 60, 90$ must all be excluded (nothing relatively prime to both $30$ and $7p$) and $42, 84$ are also all excluded (nothing relatively prime to both $42$ and $5p$). Together with $1, 7, 49$ not being in the set, these results are enough to show that the set has size at most $72$ in this case. As we've exhausted all cases, we've shown that the set has size at most $72$ in any case, and therefore the answer is $\boxed{72}.$ $\square$