Iran TST? I'm happy! I really like iranian problems! First a few observation: let us divide A in the set $A_{1}$, the set of numbers that divide exactly another element of A, and $A_{2}$, the set of numbers that divide no other element of $A_{2}$. By definition, $A_{2}$ is an antichain. But it's obvious that also $A_{1}$ is an antichain. Therefore, A is the disjoint union of two antichains. What is the maximum size of an antichain? $\frac{1}{2}n$, because if you take the greatest odd divisor of each element, these must be distinct, but there are only $\frac{1}{2}n$ odd numbers $\le n$. An example of a maximal antichain is the set $\frac{1}{2}n+1 ,\frac{1}{2}n+2 \ldots, n-1,n$. Now let's start solving the problem. Suppose that $|A| > \frac{3n}4$. Take the greatest odd divisor of each element of A. There are no three elements with the same greatest odd divisor, and there are only $\frac{n}{2}$ odd numbers, then, by the pigeonhole principle, there are more than $\frac{n}{4}$ couples of elements of A with the same greatest odd divisor. Among their greatest odd divisors, take d, the greatest. Since in $[1,\frac{n}{2}]$ there are at most $\frac{1}{4}n$ odd numbers, it must be $d > \frac{n}{2}$. But then, there is a pair of elements of A with d as divisor, and the bigger must be $\ge 2d > n$, contradiction. To prove that $|A| \ge \frac{3}{2}n$, consider $A = \{ k : \frac{1}{3}n \le k \le \frac{1}{2}n \land k \equiv 1 \pmod 2\}\cup \{ 2k : \frac{1}{3}n \le k \le \frac{1}{2}n \land k \equiv 1 \pmod 2\}$. The two sets of which A is union are antichains, the first because if an odd number divides another, the second is at least 3 times the first, the second set because if $2k \mid 2j$ with both k,j odd, we have $k \mid j$.

What about the case $A = \{1\}$, $n = 1$? Then we have $|A| = 1 > \frac{3n}{4}$...

Excuse me, that must be $\left\lceil \frac{3n}4\right\rceil$. Moderators, Could you please edit this topic?

What's an antichain?

Do you know what a search engine is? http://mathworld.wolfram.com/Antichain.html The poset in question is the set of integers from 1 to $ n$ ordered by division.

i think this solution is a bit easier than the one presented above : for the first part it is clear just by taking $ B={k+1,k+2,......,3k+e}$ where $ n=3k+e$ and $ e = 0,1,2$ because $ |A|\geq |B|$for the second part,let's take $ n=4k$ and for $ n=4k+1,2,3$ it can be done almost exactly the same way.we can write $ {1,2,....,4k}$ as $ 1,3,.....,4k-1; 2*1,2*3,....2*(2k-1); 4*1,4*3,.....; ..........;2^{v}*1;$ where$ 4k\geq 2^{v}$and v is the greatest number with that property.so $ {1,2,3,....,4k}$can be partitioned in $ A_{1}={1,2*2,4*1,......,2^{v}*1}+A_{3}{3,2*3,4*3,.......}+........A_{(}2k-1)={2k-1,2*(2k-1)}+C={2k+1,2k+3,.....,4k-1}$.it is clear that from $ A_{(}2j-1)$ we can choose at most 2 numbers,for every $ j=0,1,2,....,k-1$ so we can get at most $ 2k$ numbers from there and we are left with just $ k$ numbers that we can choose ,the numbers from $ C$.so we kave at most $ 3k$ numbers in $ A$. that's all

bodom wrote: i think this solution is a bit easier than the one presented above : for the first part it is clear just by taking $ B={k+1,k+2,......,3k+e}$ where $ n=3k+e$ and $ e = 0,1,2$ because $ |A|\geq |B|$for the second part,let's take $ n=4k$ and for $ n=4k+1,2,3$ it can be done almost exactly the same way.we can write $ {1,2,....,4k}$ as $ 1,3,.....,4k-1; 2*1,2*3,....2*(2k-1); 4*1,4*3,.....; ..........;2^{v}*1;$ where$ 4k\geq 2^{v}$and v is the greatest number with that property.so $ {1,2,3,....,4k}$can be partitioned in $ A_{1}={1,2*2,4*1,......,2^{v}*1}+A_{3}{3,2*3,4*3,.......}+........A_{(}2k-1)={2k-1,2*(2k-1)}+C={2k+1,2k+3,.....,4k-1}$.it is clear that from $ A_{(}2j-1)$ we can choose at most 2 numbers,for every $ j=0,1,2,....,k-1$ so we can get at most $ 2k$ numbers from there and we are left with just $ k$ numbers that we can choose ,the numbers from $ C$.so we kave at most $ 3k$ numbers in $ A$. that's all How is this clear for the first part? Still confused with that