Solved with Luke Robitaille, Justin Lee, and Espen Slettnes. Let \[V=\bigcup_{a\in A}\{\text{divisors of }a\} \quad\text{and}\quad W=\bigcup_{a\in A}\{\text{multiples of }a\}\cap D\] Claim: \(|V|\cdot|W|\ge|A|\cdot|D|\). Proof. We induct on the number of prime divisors of \(n\), with base case \(n=1\) trivial. For the inductive step, take a prime \(p\mid n\). For any set \(S\), let \(S_i=\{s\in S\mid \nu_p(s)=i\}\). Then \(|V_0|\ge|V_1|\ge\cdots\ge|V_n|\) and \(|W_0|\le|W_1|\le\cdots\le|W_n|\). By Chebyshev's inequality, \begin{align*} |V|\cdot|W|=\left(\sum_{i=0}^n|V_i|\right)\left(\sum_{i=0}^n|W_i|\right) &\ge(n+1)\sum_{i=0}^n|V_i|\cdot|W_i|\\ &\ge(n+1)\sum_{i=0}^n|A_i|\cdot|D_i| =|D|\sum_{i=0}^n|A_i|=|A|\cdot|D|. \end{align*}\(\blacksquare\) We may assume that for any \(d\in D\), if \(d\) has a divisor and a multiple in \(A\), then \(d\in A\). Then \(V\cap W=A\) and \(|V\cup W|=|D|-|B|\), so \[|D|-|B|+|A|=|V|+|W|\ge2\sqrt{V|\cdot|W|}\ge2\sqrt{|A|\cdot|D|},\]which rearranges to the desired.

Oops this is pretty much the same as above Let $A_{down} = \{ x \text{ st } x|a \text{ for some } a\in A\}$ and $A_{up} = \{ \text{ st } a|x|n \text{ for some } a\in A\}$. Define $B_{up}, B_{down}$ similarly. Main Claim: $|A| |D| \le |A_{up}||A_{down}|$ Proof: We induct on $\omega(n)$. Let $t=\nu_p(n)$ and for a set $S$, let $S_j=\{x \text{ st } \nu_p(x)=j \text{ and } x\in S\}$ Observe $A_{up,0} \subseteq A_{up,1} \subseteq \cdots \subseteq A_{up,t}$ and $A_{down,t} \subseteq A_{down,t-1} \subseteq \cdots \subseteq A_{down,0}$ Thus, by rearrangement inequality, $|A_{up}| |A_{down}| = \sum\limits_{0\le x,y\le t} |A_{up,x}| |A_{down,y}| \le (t+1) \sum\limits_{0\le x\le t} |A_{up,x}| |A_{down,x}|$ By inductive hypothesis on $\frac{n}{p^t}$, $|A_{up,x}| |A_{down,x}| \ge |A_x| |D_x|$ Therefore, $(t+1) \sum\limits_{0\le x\le t} |A_{up,x}| |A_{down,x}| \ge (t+1) \sum\limits_{0\le x\le t} |A_x| |D_x| = |D| \sum\limits_{0\le x\le t} |A_x| = |D||A|$ Now, notice $A_{up} \cap B_{down} = \emptyset$ because if $t\in A_{up} \cap B_{down}$, there exists $a,b$ st $a\mid t\mid b$, absurd. Similarly, $A_{down}\cap B_{up}=\emptyset$. Thus, $$\sqrt{|A|}+\sqrt{|B|} \le \frac{1}{\sqrt{|D|}} (\sqrt{|A_{up}||A_{down}|} + \sqrt{|B_{up}||B_{down}|}) = \frac{1}{\sqrt{|D|}} (\sqrt{(|A_{up}|+|B_{down}|) (|A_{down}|+|B_{up}|}) = \sqrt{|D|} $$

Here is another idea. WLOG, if there exists $a_1,a_2\in A$ st $a_1 | x | a_2$ then $x\in A$. Same for $B$. Let $X$ be the set of integers $x$ st there exists $a \in A, b\in B$ then $x\mid a, x\mid b$, and $Y$ be the set of integers $y$ st there exists $a\in A, b\in B$ st $b\mid y, a\mid y$. If I prove $|A| |B| \le |X| |Y|$ I am done since $(\sqrt{|A|}+\sqrt{B})^2 \le |A|+|B|+2\sqrt{|X||Y|} \le |A|+|B|+|X|+|Y|=|D|$ Wait a minute this rearranges into the main claim of the above solution oops and can be proved inductively in the exact same way.

I had posted a solution that used this : (and found out later it's a well known inequality) https://en.wikipedia.org/wiki/Ahlswede%E2%80%93Daykin_inequality

it's a difficult question if you don't know Kleitman Lemma during the exam

Counterattacker04 wrote: it's a difficult question if you don't know Kleitman Lemma during the exam Could you please tell me what is Kleitman Lemma？

\begin{align*} &(n+1)\sum_{i=0}^n|V_i|\cdot|W_i|\ge(n+1)\sum_{i=0}^n|A_i|\cdot|D_i| \end{align*}why?Is this the lemma?

wx-78 wrote: Counterattacker04 wrote: it's a difficult question if you don't know Kleitman Lemma during the exam Could you please tell me what is Kleitman Lemma？ If you're chinese you can read this article

This is an old problem. Here is a reference: "On Intersection Theorems and a lemma of Kleitman"

What we need to do is simply generalizing Kleitman Lemma from hypercube $Q_n$ to set of divisors $D_n.$ The proof is actually quite similar. The FKG inequality then says that for any monotonically increasing functions $f$ and monotonically decreasing function $g$ on $X$ the following positive correlation inequality holds: $${\displaystyle \left(\sum _{x\in X}f(x)g(x)\mu (x)\right)\left(\sum _{x\in X}\mu (x)\right)\leq \left(\sum _{x\in X}f(x)\mu (x)\right)\left(\sum _{x\in X}g(x)\mu (x)\right).}$$Here $\mu$ is a log supermodular function. A nice understanding is defining the expectation $$\langle f\rangle:=\frac{\sum _{x\in X}f(x)\mu (x)}{\sum _{x\in X}\mu (x)}$$So FKG inequality shows $\langle fg\rangle\le\langle f\rangle\cdot\langle g\rangle.$ To prove Kleitman Lemma: Quote: $\mathcal A,\mathcal B$ are upset, downset on $D_n$ respectively. Then $$\Pr[\mathcal A]\Pr[\mathcal B]\ge \Pr[\mathcal A\cap\mathcal B]$$ Proof. Let $f: D_n \rightarrow \mathbb{R}^{+}$ be the characteristic function of $\mathcal A$; that is, $f(A) = 0$ if $A \notin \mathcal A$ and $f(A) = 1$ if $A \in \mathcal A$. Similarly, let $g$ be the characteristic function of $\mathcal B$. By the assumptions, $f$ is increasing and $g$ is decreasing. Applying the FKG Inequality with the trivial measure $\mu = 1$ we get $$\Pr[A \cap B] = \langle fg\rangle\le\langle f\rangle\cdot\langle g\rangle = \Pr[A] \Pr[B].\Box$$Back to original problem, Let $A_{-} = \{ x \text{ st } x|a \text{ for some } a\in A\}$ and $A_{+} = \{ \text{ st } a|x|n \text{ for some } a\in A\}$. Define $B_{-}, B_{+}$ similarly. Since $A\subseteq A_-\cap A_+,B\subseteq B_-\cap B_+,$ by the theorem above and Cauchy Schwarz Inequality $$\sqrt{\frac{|A|}{|D|}}+\sqrt{\frac{|B|}{|D|}}\le\sqrt{\Pr[A_-]\Pr[A_+]}+\sqrt{\Pr[B_-]\Pr[B_+]}\le\sqrt{(\Pr[A_-]+\Pr[B_+])(\Pr[A_+]+\Pr[B_-])}\le 1.\Box$$