Problem

Source: Iran TST 2007, Day 1

Tags: ceiling function, pigeonhole principle, modular arithmetic, search, combinatorics proposed, combinatorics



Let $A$ be the largest subset of $\{1,\dots,n\}$ such that for each $x\in A$, $x$ divides at most one other element in $A$. Prove that \[\frac{2n}3\leq |A|\leq \left\lceil \frac{3n}4\right\rceil. \]