MathDB
Maximum subset wth no element divinding two other elements

Source: Iran TST 2007, Day 1

May 6, 2007
ceiling functionpigeonhole principlemodular arithmeticsearchcombinatorics proposedcombinatorics

Problem Statement

Let AA be the largest subset of {1,…,n}\{1,\dots,n\} such that for each x∈Ax\in A, xx divides at most one other element in AA. Prove that 2n3≤∣A∣≤⌈3n4⌉.\frac{2n}3\leq |A|\leq \left\lceil \frac{3n}4\right\rceil.
Back to ProblemsView on AoPS