For every $\epsilon>0$ there's a constant $C$ independent of $n$ such that $d(n)<C n^{\epsilon}$ for every natural $n$.

Prove this lemma and this problem is killed immediately. About 50% contestants solved it.

@above, what is $d(n)$? If it is the number of divisors, then the lemma is pretty trivial to prove.

Yep...

In fact we have that for large enough n, it is less than $e^{O(\frac{\log n}{\log \log n})}$. So we are trivially done.

Yes, I know. But it's more than necessary.

How to prove the lemma of @smy2012?

Lemma: For all sufficiently large $n$, $d(n)^c \leq n$, for any constant $c>0$. Proof: Define the function $\max(f(x))$ to be the maximum of $f(x)$ as $x$ goes through the positive integers. Let $M=\prod_{p \leq 2^c} \max\left(\frac{(x+1)^c}{p^x}\right)$ Note that $M$ is not infinity because $p^x$ grows much faster than $(x+1)^c$. Let $\{p_1, ..., p_k\}$ be the set of all primes less than $M2^c$. For each $i \leq k$, there exists some $a_i$ such that $\frac{p_i^{a_i}}{(a_i+1)^c} \geq M$ and the function $\frac{p_i^{x}}{(x+1)^c}$ for all $x \geq a_i$. Now, let $n > \prod_{i=1}^k p_i^{a_i}$. Let $n=\prod q_i^{b_i}$ be the prime factorization of $n$. Then, $d(n) = \prod(b_i+1)$. Call $q_i^{b_i}$ bad if $q_i^{b_i} \leq (b_i+1)^c$, and good otherwise. The bad factors have a maximum product of $M$. It suffices to prove that the good factors product to more than $M$. If there is a good factor $q^b$ of $n$ such that $q>M2^c$, then we are done since $\frac{q^b}{(b+1)^c} \geq \frac{q}{2^c} \geq M$. If there is some good factor $q_b$ of $n$ such that $q=p_i$ and $b \geq a_i$, then we are done since $\frac{q^b}{(b+1)^c} \geq \frac{p_i^{a_i}}{(a_i+1)^c} \geq M$. Otherwise, the product of all factors of $n$ are at most $ \prod_{i=1}^k p_i^{a_i}$, a contradiction. The problem follows easily from the Lemma (e.g. $lcm (1, 2, ..., n^{0.01}) \geq 2^{n^{0.01}-1} > n^{n^{2c}} > n^{d(n)^2} > \prod(d_i-d_j)$, product of all pairs of divisors of $n$ and for some $c < 1/200$ and all sufficiently large $n$).

We prove that $d(n) = n^{o(1)}$. For any $\epsilon >0$, we show that $\frac{d(n)}{n^\epsilon}$ is bounded. For $n=p^{e_1}_1 \cdots p^{e_k}_k$, we have $\frac{d(n)}{n^\epsilon} = \prod_{1 \le i \le k} \frac{e_i +1}{p^{\epsilon \cdot e_i}_i}$. If $p_i \ge e^{ \frac{1}{\epsilon}}$, we have $p^{\epsilon \cdot e_i}_i \ge e^{e_i} \ge e_i + 1$, so $\frac{e_i+1}{p^{\epsilon \cdot e_i}} \le 1$. If not, so if $p_i < e^{\frac{1}{\epsilon}}$, since $\frac{x+1}{p^{\epsilon \cdot x}}$ is a convergent function as $x$ goes to infinity, we know that $\frac{e_i+1}{p^{\epsilon \cdot e_i}}$ is bounded above. Therefore, $\frac{d(n)}{n^\epsilon}$ is no more than a finite product of bounded values, so it is bounded above, as required. Now, $|D_n| = n^{o(1)}$, and the set of divisors of numbers which can be represented as a difference of two elements in $D_n$ is $n^{o(1)}$ as well. Since $f(n)$ is the "mex" of this set, it is clearly $n^{o(1)}$ as well, proving the claim.

Claim: for all $\epsilon>0$, there exist $N$ such that $\forall n>N, d(n)<n^{\epsilon}$. Proof: $\frac{d(n)}{n^{\epsilon}} = \prod_{p\mid n} \frac{\nu_p(n)+1}{p^{\epsilon\nu_p(n)}}$. Consider the function $f(t)=\frac{t+1}{p^{\epsilon t}}$. We can see that for all primes $p$, this is bounded, and for all large enough primes, such $t$ don't exist. It's easy to see that this works. Now, we attack the original problem. I first tried to construct $n$, but realized it is hard because the primes behave rather randomly. Even if I set the prime divisors of $n$ to be generators, there is still a chance of collision. Local don't work, so we consider global. Wait a minute, let $E=D_n-D_n,$ then $|E|\le |D_n|^2 =d(n)^2$. GG

Very nice! The proof is based around the following well-known lemma: Lemma: For any $\varepsilon>0$ there exists $N_\varepsilon$ such that $\tau(n)<n^{\varepsilon}$ for all $n\geq N_{\varepsilon}.$ Let $1=d_1<d_2<\ldots<d_{\tau(n)}=n$ be the divisors of $n$. It follows easily from the definition of $f(n)$ that: \[f(n)<\sum_{i<j}\tau\big(|d_i-d_j|\big).\]Now, let $C_\varepsilon:=\max(\tau(1),\ldots,\tau(N_\varepsilon)).$ Let $k$ be the number of pairs $(i,j)$ with $i<j$ such that $|d_i-d_j|<N_\varepsilon.$ Then, we have \[\sum_{i<j}\tau\big(|d_i-d_j|\big)=\sum_{|d_i-d_j|<N_\varepsilon}\tau\big(|d_i-d_j|\big)+\sum_{|d_i-d_j|\geq N_\varepsilon}\tau\big(|d_i-d_j|\big)<\]\[<C_\varepsilon\cdot k+\sum_{|d_i-d_j|\geq N_\varepsilon}|d_i-d_j|^{\varepsilon}<C_\varepsilon\cdot k+\Bigg(\binom{\tau(n)}{2}-k\Bigg)\cdot n^\varepsilon<\]\[C_\varepsilon\cdot k+\big(\tau(n)^2-k\big)\cdot n^\varepsilon<\max\big(\tau(n)^2\cdot C_\varepsilon, \tau(n)^2\cdot n^{\varepsilon}\big).\]The latter inequality was deduced from the fact that $C_\varepsilon\cdot k+\big(\tau(n)^2-k\big)\cdot n^\varepsilon$ is a linear function in terms of $k.$ Choose (and fix) $\varepsilon$ to be strictly less than $0.01/2$ and let $\delta=0.01/2-\varepsilon.$ We claim that if $n$ is big enough, then we will indeed have \[\max\big(\tau(n)^2\cdot C_\varepsilon, \tau(n)^2\cdot n^{\varepsilon}\big)<n^{0.01}.\]Notice that if $n>N_\delta$ then by our lemma $\tau(n)^2\cdot n^{\varepsilon}<n^{2\delta+\varepsilon}=n^{0.01}$ so everything's good. If we also have $n>\big(C_\varepsilon\big)^{1/\varepsilon}$ then again by our lemma $\tau(n)^2\cdot C_{\varepsilon}<n^{2\delta}\cdot C_{\varepsilon}=n^{0.01}\cdot \big(C_\varepsilon/n^{\varepsilon}\big)<n^{0.01}.$ Hence, if $\varepsilon<0.01/2$ and $\delta=0.01/2-\varepsilon$ and $n>\max\big(N_\delta,\big(C_\varepsilon\big)^{1-\varepsilon}\big),$ to cite CANBANKAN, it's GG.

How is this true? $2^{n^{0.01}-1} > n^{n^{2c}}$ for $c<1/200$

The following claim is the pith of the problem. Claim: Let $d$ be the divisor-counting function. Then $d(n)=O(n^k)$ for all $k>0$ (here we use the actual definition of big-O, i.e. $f(n)=O(g(n)) \iff |f(n)|\leq Cg(n)$ for some fixed constant $C$.) Proof: For some prime power $n=p^e$, we have $d(n)=e+1$, so $\tfrac{d(n)}{n^k}=\tfrac{e+1}{p^{e/k}}$. There exists a constant $M$ (dependent on $k$) such that for any $p>M$, this fraction will always be at most $1$. Then $\tfrac{d(n)}{n^k}$ is bounded above by $$\prod_{\substack{p \text{ prime}\\p\leq M}} \max\left\{\frac{e+1}{p^{e/k}}\right\}_{e\geq 0}$$which is clearly finite, proving the desired claim. $\blacksquare$ Now pick $k=1/1000$ for our lemma. By picking $n$ as shown in the problem, we have $d(n)=O(n^{1/1000})$, so there are $O(n^{1/500})$ pairs of distinct divisors $(d_1,d_2)$ of $n$. For one of these pairs, there are exactly $d(|d_1-d_2|)$ positive numbers $m$ such that $d_1$ and $d_2$ are not distinct modulo $m$. By union bounding, this means that the number of $m$ such that the elements of $D_n$ aren't pairwise distinct modulo $m$ is at most $$\sum_{(d_1,d_2)} d(|d_1-d_2|)\leq \sum_{(d_1,d_2)} d(n)=\sum_{(d_1,d_2)} O(n^{1/1000})=O(n^{3/1000}),$$which will clearly be less than $n^{1/100}$ for sufficiently large $n$. $\blacksquare$