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$.
Problem
Source: Problem 2, Brazilian MO 2015
Tags: combinatorics proposed, combinatorics
21.10.2015 03:33
Let $A=\{2n+1,2n+2,...,6n\}\Rightarrow k\le n$ Now take $X=\{a_1,a_2,...,a_{3n+1}\} , Y=\{a_{3n+2},a_{3n+3},...,a_{4n}\}$ and $A=X\cup Y \subset S$ we know that $\exists a_i<a_j \in X$ such that $a_i\mid a_j$ then make $X_1=X\backslash a_j \cup \{a_{3n+2}\}$ again making this process we have that $k\ge n$, then $k=n.$
22.10.2015 01:57
Lemma: Let $n \in \mathbb{N}$ and let $S$ be an $n + 1$ element subset of $\{1, 2, \cdots 2n\}.$ Then $S$ has two elements such that one divides the other. Proof: Break $\{1, 2, \cdots, 2n\}$ into subsets of the form $\{p \cdot 2^k \mid k \in \mathbb{N}_0\}$ for each prime $p \le 2n.$ Since we have created $\pi(2n) \le n$ of these subsets, by the Pigeonhole Principle, two elements of $S$ must belong to one of these subsets. But then one of these elements divides the other, as desired. $\blacksquare$ Back to the problem at hand, consider $A = \{2n + 1, 2n + 2, \cdots, 6n\}.$ If $x, y \in A$ are distinct and satisfy $x \mid y$, then on account of $y / x < 3$, we must have $y / x = 2.$ Thus, it is easy to classify all pairs $(x, y) \in A^2$ such that $x \mid y$ and $x \ne y$: they are of the form $(2n + t, 4n + 2t)$ for $t = 1, 2, \cdots, n.$ It follows that $k \le n.$ Now, we will show that $k \ge n.$ Suppose otherwise, and let $\left(x_1, y_1\right), \left(x_2, y_2\right), \cdots, \left(x_m, y_m\right)$, with $m < n$, be all pairs $(x, y) \in A^2$ such that $x \mid y$ and $x \ne y.$ Now, remove $x_1, x_2, \cdots, x_m$ from $A$ to create a new set $B.$ In particular, there are no pairs $(x, y) \in B^2$ such that $x \mid y$ and $x \ne y.$ However, since $|B| \ge |A| - m \ge 3n + 1$, this contradicts the lemma. It follows that $k \ge n$ as well, and therefore $k = n.$ $\square$
27.10.2015 04:46
I've needed a bit more computations. Here is my solution: Definition: Given an integer $n=2^aI$, where $I$ is odd, we define $I$ as the odd part of $n$. Lemma 1: $k\ge n$. Proof: Let $1, 3, 5, \cdots, 6n-1$ be the odd parts of the numbers from $1$ to $6n$. It is easy to see that if two numbers $a$ and $b$ have the same odd part, and $a<b$, so $a|b$. Moreover, let $y_i$ be the amount of numbers $a$ in our set $A$ which have the odd part equal to $b_i$, with $\{1,3,5,\cdots,6n-1\}=\{b_1,b_2,\cdots,b_{3n}\}$. Suppose WLOG that $y_1=y_2=\cdots=y_t=0$, $y_{t+1}=y_{t+2}=\cdots=y_l=1$ and $y_{l+i}\ge 2 \forall i\ge 1$. Define $\sum_{i=1}^{3n-l} y_{l+i} = S$. We also know that the amount of pairs $(a,b)$ such that $a<b, a|b$ with $a, b \in A$ is at least $$T=\sum_{i=1}^{3n-l}\binom{y_{l+i}}{2}$$because if $a,b$ has the same odd part, so $a|b$ or $b|a$. So, using Cauchy, we have that $$T \ge \frac{S^2-(3n-l)S}{2(3n-l)}$$Moreover, notice that $S+1(l-t)+0(t)=4n \iff S=4n+t-l$, and we also know that $S \ge 2(3n-l)$, thus $4n+t-l \ge 2(3n-l) \iff t+l \ge 2n$. So $$T \ge \frac{S(S-3n+l)}{2(3n-l)}=\frac{(4n+t-l)(n+t)}{2(3n-l)}$$It is enough to prove that the right side above is greater or equal than $n$. But this occours iff $(4n+t-l)(n+t)\ge 2n(3n-l) $ $\iff 4n^2+5nt+t^2-ln-lt \ge 6n^2-2nl$ $ \iff t(4n+t-l)+n(t+l)\ge 2n^2 $ $\iff St+n(t+l)\ge 2n^2$, which indeed is true, since $t+l\ge 2n$ and $S,t\ge0$. Therefore, $k\ge T \ge n$. $\square$ Lemma 2: $k\le n$. Proof: Take $A=\{2n+1,2n+2, \cdots, 6n\}$, and it is easy to see that we have at most $n$ pairs $(a,b)$, $a<b$, such that $a|b$. $\square$ So $k=n$, and we are done. $\blacksquare$.