Consider S={1,2,3,⋯,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}⇒k≤n Now take X={a1,a2,...,a3n+1},Y={a3n+2,a3n+3,...,a4n} and A=X∪Y⊂S we know that ∃ai<aj∈X such that ai∣aj then make X1=X∖aj∪{a3n+2} again making this process we have that k≥n, then k=n.
22.10.2015 01:57
Lemma: Let n∈N and let S be an n+1 element subset of {1,2,⋯2n}. Then S has two elements such that one divides the other. Proof: Break {1,2,⋯,2n} into subsets of the form {p⋅2k∣k∈N0} for each prime p≤2n. Since we have created π(2n)≤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. ◼ Back to the problem at hand, consider A={2n+1,2n+2,⋯,6n}. If x,y∈A are distinct and satisfy x∣y, then on account of y/x<3, we must have y/x=2. Thus, it is easy to classify all pairs (x,y)∈A2 such that x∣y and x≠y: they are of the form (2n+t,4n+2t) for t=1,2,⋯,n. It follows that k≤n. Now, we will show that k≥n. Suppose otherwise, and let (x1,y1),(x2,y2),⋯,(xm,ym), with m<n, be all pairs (x,y)∈A2 such that x∣y and x≠y. Now, remove x1,x2,⋯,xm from A to create a new set B. In particular, there are no pairs (x,y)∈B2 such that x∣y and x≠y. However, since |B|≥|A|−m≥3n+1, this contradicts the lemma. It follows that k≥n as well, and therefore k=n. ◻
27.10.2015 04:46
I've needed a bit more computations. Here is my solution: Definition: Given an integer n=2aI, where I is odd, we define I as the odd part of n. Lemma 1: k≥n. Proof: Let 1,3,5,⋯,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 yi be the amount of numbers a in our set A which have the odd part equal to bi, with {1,3,5,⋯,6n−1}={b1,b2,⋯,b3n}. Suppose WLOG that y1=y2=⋯=yt=0, yt+1=yt+2=⋯=yl=1 and yl+i≥2∀i≥1. Define ∑3n−li=1yl+i=S. We also know that the amount of pairs (a,b) such that a<b,a|b with a,b∈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.