Problem

Source: Problem 2, Brazilian MO 2015

Tags: combinatorics proposed, combinatorics



Consider $S=\{1, 2, 3, \cdots, 6n\}$, $n>1$. Find the largest $k$ such that the following statement is true: every subset $A$ of $S$ with $4n$ elements has at least $k$ pairs $(a,b)$, $a<b$ and $b$ is divisible by $a$.