Let $ n$ be a positive integer, let $ A$ be a subset of $ \{1, 2, \cdots, n\}$, satisfying for any two numbers $ x, y\in A$, the least common multiple of $ x$, $ y$ not more than $ n$. Show that $ |A|\leq 1.9\sqrt {n} + 5$.
Problem
Source: China TST 2007, Problem 6
Tags: least common multiple, number theory, relatively prime, number theory unsolved
15.04.2009 11:48
This is the official solution: For $ a\in (\sqrt{n},\sqrt{2n}]$, we have $ [a,a+1]=a(a+1)>n$.So $ |A\cap (\sqrt{n},\sqrt{2n})|\le \frac{1}{2}(\sqrt{2}-1)\sqrt{n}+1$. For $ a\in (\sqrt{2n},\sqrt{3n}]$, we have $ [a,a+1]=a(a+1)>n$, $ [a+1,a+2]=(a+1)(a+2)>n$, $ [a,a+2]\ge \frac{1}{2}a(a+2)>n$. So $ |A\cap (\sqrt{2n},\sqrt{3n}]|\le \frac{1}{3}(\sqrt{3}-\sqrt{2})\sqrt{n}+1$. For the same reason $ |A\cap (\sqrt{3n},2\sqrt{n}]|\le \frac{1}{4}(\sqrt{4}-\sqrt{3})\sqrt{n}+1$. So $ |A\cap [1,2\sqrt{n}]|\le \sqrt{n}+\frac{1}{2}(\sqrt{2}-1)\sqrt{n}+\frac{1}{3}(\sqrt{3}-\sqrt{2})\sqrt{n}+\frac{1}{4}(\sqrt{4}-\sqrt{3})\sqrt{n}+3=(1+\frac{1}{6}\sqrt{2}+\frac{1}{12}\sqrt{3})\sqrt{n}+3$ For positive integer $ k$, assume $ a,b\in (\frac {n}{k+1},\frac {n}{k}]$, $ a>b$, and assume $ [a,b]=as=bt$, then $ \frac{a}{(a,b)}s=\frac{b}{(a,b)}t$ Because $ \frac{a}{(a,b)}$ and $ \frac{b}{(a,b)}$ are relatively prime, so $ s$ is a multiple of $ \frac{b}{(a,b)}$. Therefore $ [a,b]=as\ge \frac{ab}{(a,b)}\ge \frac{ab}{a-b}=b+\frac{b^2}{a-b}>\frac{n}{k+1}+\frac{(\frac{n}{k+1})^2}{\frac{n}{k}-\frac{n}{k+1}}=n$ So $ |A\cap (\frac{n}{k+1},\frac{n}{k}]|\le 1$. Take positive integer $ T$ such that $ \frac{n}{T+1}\le 2\sqrt{n}<\frac{n}{T}$, then $ |A\cap (2\sqrt{n},n]|\le \sum_{k=1}^T |A\cap (\frac{n}{k+1},\frac{n}{k}]|\le T<\frac{1}{2}\sqrt{n}$ Combined all above we get $ |A|\le (\frac{3}{2}+\frac{1}{6}\sqrt{2}+\frac{1}{12}\sqrt{3})\sqrt{n}+3<1.9\sqrt{n}+5$. Q.E.D
06.05.2012 12:23
For $n\le64$ it is verry easy, try it yourself. In the last part i meant it has at least 1.9.... divisors smaller that $\sqrt{n+1}$
Attachments: