Let $n \geq 2$ be a positive integer and define $k$ to be the number of primes $\leq n$. Let $A$ be a subset of $S = \{2,...,n\}$ such that $|A| \leq k$ and no two elements in $A$ divide each other. Show that one can find a set $B$ such that $|B| = k$, $A \subseteq B \subseteq S$ and no two elements in $B$ divide each other.
Problem
Source: China Mathematical Olympiad 2016 Problem 4
Tags: number theory
18.12.2015 15:44
Let $A_1,A_2,...,A_k$ be the largest power of each of the $k$ primes which is less than $n$. Call a number i-affiliated if it is either a power of $p_i$ or a multiple of $A_i$. No number can be doubly affiliated - if it were, it has to be a multiple of some $A_iA_j$. But wlog $p_i <p_j $, $A_ip_i\le A_ip_j\le A_iA_j \le n$, which contradicts the definition of $A_i $. Note that a number can only divide or be divided by $A_i $ if it is i-affuliated. So we just choose the $A_i $ s that are not affiliated with any number in $A $.
23.12.2015 17:55
We will show the desired result by backward induction on $|A|.$ For the base case, $|A| = k$, take $B = A.$ Now, suppose that the result is true for $|A| = m < k$ and we will prove it true for $|A| = m - 1.$ Let $\{p_1, p_2, \cdots, p_k\}$ be the set of all primes $\le n$ and for $i = 1, 2, \cdots, k$, define \[A_i := \{x \in A : p_i \text{ is the largest prime divisor of } x\}.\]Note that $A$ is a disjoint union of the $A_i$'s and $|A| < \# A_i.$ Thus, the Pigeonhole Principle implies that $A_j$ is empty for some $1 \le j \le k.$ Let $p = p_j$ and let $p^{\alpha}$ be the largest power of $p \le n.$ We claim that $A$ contains no divisors nor multiples of $p^{\alpha}.$ Indeed, if $p^{\beta} \in A$ for some $\beta \le \alpha$, it would follow that $p^{\beta} \in A_j$, absurd. Meanwhile, if $cp^{\alpha} \in A$ for some $c > 1$, then $cp^{\alpha}$ has a prime divisor $q > p$ because $cp^{\alpha} \not\in A_j.$ Hence, $q \mid c$, which implies that $cp^{\alpha} \ge qp^{\alpha} > p^{\alpha + 1} > n$, absurd. Thus, if $A' = A \cup \{p^{\alpha}\}$, then no two distinct elements of $A'$ divide one another. Since $|A'| = m$ and $A \subset A'$, we can then find the desired $B$ by the inductive hypothesis applied to $A'.$ $\square$
14.11.2016 18:57
Let $P$ be the set of $k$ primes. For each element in $A$, take its largest prime divisor and we have the multiset $A_p=\{p_1,p_2,\ldots, p_{|A|}\}$. Consider $P \setminus A_p = \{q_1,q_2,\ldots,q_{|Q|}\}$, and $Q=\{q_1^{c_1},q_2^{c_2},\ldots, q_{|Q|}^{c_{|Q|}}\}$, where each $q_i$ is taken to its largest power less than or equal to $n$. Note $A\cap Q=\emptyset$, thus $|Q|\ge k-|A|$, and we show $A\cup Q$ will give the desired set(take away elements from $|Q|$ if necessary such that $|A\cup Q|=k$). Clearly no two elements in $Q$ divide each other. Neither does any element in $A$ divide an element in $Q$, since each element in $A$ contain a prime that each element in $Q$ does not. Now suppose $q_i^{c_i}|p_ja_j$, where $p_ja_j\in A$ and $p_j$ is its largest prime factor. By definition $q_i< p_j$. Thus $p_ja_j\ge p_jq_i^{c_i}>q_i^{c_i+1}>n$, contradiction. Hence no element in $Q$ divides an element in $A$ and we are done.