An amazing solution given by Dongyi Wei(2008,2009 IMO gold medalist) indicated that $ 4n$ can be replaced by $ 2n+4$

hxy09 wrote: An amazing solution given by Dongyi Wei(2008,2009 IMO gold medalist) indicated that $ 4n$ can be replaced by $ 2n + 4$ I haven't seen this solution (please post if you have it), but he's most probably right. I have found $ 3n + 2$, but the solution is quite "wasteful", so a much better bound probably exists. Say that an element $ z\in S_a$ is an "$ m$-divider" in the set if elements $ x_a,y_a\in S_a$ exist such that $ z > y_a\geq z - m> x_a$. Clearly, a given element of $ A$ may not be an $ m$-divider in more than one subset for the same value of $ m$; say $ z$ is $ m$-divider in sets $ S_a,S_b$ with $ a < b$, then $ x_b < z - m\leq y_a$, contradiction. We consider now only $ m = 2,2^2,\dots,2^n$ (clearly no number may be an $ 2^{n + 1}$-divider), since each one of the $ 2^{n + 1}$ elements in $ A$ may be an $ m$-divider for each one of these $ n$ values of $ m$ at most once, there may be no more than $ 2^n(2n)$ numbers (counted once for each subset in which they appear) that are $ m$-dividers for $ m$ a power of $ 2$. Consider now in a given set $ S_a$ the numbers that are not $ m$-dividers for a power of $ 2$, call them $ a_1 < a_2 < ... < a_k$. We prove by induction that $ a_k - a_1\geq2^{k - 1}$. The result is obvious for $ k = 1,2$, assume it is true for $ k\geq2$ but not for $ k + 1$. Then, since $ a_k$ is not a $ 2^{k - 1}$-divider, $ a_1 + 2^k > a_k > 2^{k - 1} + a_k$, contradiction. Since $ a_k > 2^{k - 1}$, there are at most $ n + 2$ elements in each $ S_a$ that are not $ m$-dividers for $ m$ a power of $ 2$, hence a total of $ (n + 2)2^n$ elements that are not $ m$-dividers (counted once for each subset in which they appear). So the sum of the cardinals of the $ S_a$ is at most $ (3n + 2)2^n$, and at least one subset contains no more that $ 3n + 2$ elements.

The two official solutions get bounds of $ 3n + 1$ and $ 2n + 1$ respectively. A remark at the end suggests the best known lower bound is $ n + 1$. daniel's solution is almost exactly the first official one (I'm not sure where he dropped one element though). EDIT: Okay, your bounds on the sequence of non-$ m$-dividers are a little weak; you can get that from $ n+2$ to $ n+1$.

MellowMelon wrote: The two official solutions get bounds of $ 3n + 1$ and $ 2n + 1$ respectively. Maybe the second official solution is similar to Dongyi's, could you please post it MellowMelon?

daniel73 wrote: hxy09 wrote: An amazing solution given by Dongyi Wei(2008,2009 IMO gold medalist) indicated that $ 4n$ can be replaced by $ 2n + 4$ I haven't seen this solution (please post if you have it), but he's most probably right. I have found $ 3n + 2$, but the solution is quite "wasteful", so a much better bound probably exists. Say that an element $ z\in S_a$ is an "$ m$-divider" in the set if elements $ x_a,y_a\in S_a$ exist such that $ z > y_a\geq z - m > x_a$. Clearly, a given element of $ A$ may not be an $ m$-divider in more than one subset for the same value of $ m$; say $ z$ is $ m$-divider in sets $ S_a,S_b$ with $ a < b$, then $ x_b < z - m\leq y_a$, contradiction. We consider now only $ m = 2,2^2,\dots,2^n$ (clearly no number may be an $ 2^{n + 1}$-divider), since each one of the $ 2^{n + 1}$ elements in $ A$ may be an $ m$-divider for each one of these $ n$ values of $ m$ at most once, there may be no more than $ 2^n(2n)$ numbers (counted once for each subset in which they appear) that are $ m$-dividers for $ m$ a power of $ 2$. Consider now in a given set $ S_a$ the numbers that are not $ m$-dividers for a power of $ 2$, call them $ a_1 < a_2 < ... < a_k$. We prove by induction that $ a_k - a_1\geq2^{k - 1}$. The result is obvious for $ k = 1,2$, assume it is true for $ k\geq2$ but not for $ k + 1$. Then, since $ a_k$ is not a $ 2^{k - 1}$-divider, $ a_1 + 2^k > a_k > 2^{k - 1} + a_k$, contradiction. Since $ a_k > 2^{k - 1}$, there are at most $ n + 2$ elements in each $ S_a$ that are not $ m$-dividers for $ m$ a power of $ 2$, hence a total of $ (n + 2)2^n$ elements that are not $ m$-dividers (counted once for each subset in which they appear). So the sum of the cardinals of the $ S_a$ is at most $ (3n + 2)2^n$, and at least one subset contains no more that $ 3n + 2$ elements. Very very nice solution,you are the !!! Your solution is quite direct and natural which is much different from DongyiWei's.His solution is very algebraic. I wrote the solution from Dongyi Wei below.

Attachments:

MellowMelon wrote: The two official solutions get bounds of $ 3n + 1$ and $ 2n + 1$ respectively. A remark at the end suggests the best known lower bound is $ n + 1$. daniel's solution is almost exactly the first official one (I'm not sure where he dropped one element though). EDIT: Okay, your bounds on the sequence of non-$ m$-dividers are a little weak; you can get that from $ n + 2$ to $ n + 1$. Hi,Mellowmelon.Could you please post the second offcial solution?I think it is surely different from Dongyi Wei P.S.DongyiWei get IMO perfect marks this year and last year

Here's a quick sketch of the second official solution. Given $ n \geq 2$ and $ k$ subsets $ S_1, S_2, \ldots S_k$ of $ \{1,2,\ldots 2^n\}$ that satisfy the problem condition, we want to show that \[ \sum_{i = 1}^k (|S_i| - n) \leq (2n - 1)2^{n - 2},\] which directly implies the problem statement with the bound $ 2n + 1$. The proof is by induction. I'll leave the base case $ n = 2$ up to you. Suppose it is true for $ n$ and consider $ n + 1$. Consider all of the sets among $ \{S_i\}$ whose least element is at least $ 2^n + 1$ and apply the induction hypothesis to them. Now consider only the $ S_i$ whose least element is at most $ 2^n$. Let $ V_i = S_i \backslash \{1,2,\ldots 2^n\}$. Use the condition to show that removing the least element from each $ V_i$ makes all of the $ V_i$ pairwise disjoint (use the element at most $ 2^n$ that we know exists). This gets a bound on the cardinalities of the $ V_i$. Now apply the induction hypothesis to the sequence $ S_i \cap \{1,2,\ldots 2^n\}$. Combining all of these bounds accounts for all of the sets and completes the induction.

Very nice! Thanks a lot MellowMelon!

I'd like to say 'WOW' to the genius WDY!

We modify the condition to the following (this helps in reducing notation later): There do not exist indices $ a$ and $ b$ with $ b < a$ and elements $ x$, $ y$, $ z\in A$ with $ x < y < z$ and $ y$, $ z\in S_a$, and $ x$, $ z\in S_b$. This is equivalent to the original formulation with the order of the sets reversed. Let $L_i= |S_i|$ and $a_{i,j}$ be the $j$th element of $S_i$ in increasing order (we use one-based indexing). Define a weight $W(i,j)$ for every $1 \leq i \leq 2^n, 0 \leq j \leq L_i$ as follows: $W(i,0)=W(i,1)=0$. For $j>1$, consider $T=\{t | a_{i,j} \in S_t, t \leq i\}$. Let $T= \{t_1, t_2, \cdots, t_u\}$ where $t_1 < t_2 < \cdots < t_u=i$. Let $a_{i,j}$ be the $q_k$th element of $S_{t_k}$, i.e, $a_{i,j}= a_{t_k, q_k}$. Set $W(i,j)= 1+\sum_k W(t_k, q_k-1)$. Claim: We have $W(i,j) \leq \max(0,a_{i,j}-a_{i,2}+1)$ for all $i,j$. Proof: This is trivially true for $j <2$ so assume $j \geq 2$. Consider $T=\{t | a_{i,j} \in S_t, t \leq i\}$. Let $T= \{t_1, t_2, \cdots, t_u\}$ where $t_1 < t_2 < \cdots < t_u = i$ and let $q_k$ be the position of $a_{i,j}$ in $S_{t_k}$. By the definition of $W$, $W(i,j) = 1+ \sum W(t_k, q_k-1)$. By induction (on $a_{i,j}$) we have $W(t_k, q_k-1) \leq \max(a_{t_k, q_k-1}-a_{t_k,2}+1,0)$ for all $k$. Thus it suffices to show $\sum \max(a_{t_k,q_k-1} - a_{t_k,2}+1,0) \leq a_{i,j}-a_{i,2}$. We only need to consider the above sum for those $k$ for which $q_k>2$. Let $U=\{k| k \leq |T|, q_k>2\}$. Consider any two indices $p,r \in U$ with $p<r$. Note that the given condition implies that the interval $[a_{t_p, 1}, a_{t_p, q_p-1}]$ is contained in the interval $[a_{t_r, q_r-1}, a_{t_r, q_r}]$ (otherwise we would have a contradiction: $a_{t_p, 1}, a_{i,j} \in S_{t_p}, a_{t_r, q_r-1}, a_{i,j} \in S_{t_r}, t_p<t_r, a_{t_p,1}<a_{t_r,q_r-1}<a_{i,j}=a_{t_r, q_r}=a_{t_p, q_p} $. This is the only place in the proof where we use the given condition.). Thus $[a_{t_p, 2}, a_{t_p, q_p-1}]$ is a proper subinterval of $[a_{t_r, q_r-1}, a_{t_r, q_r}]$. So the intervals $[a_{t_k, 2}, a_{t_k, q_k-1}]$ for $k \in U$ don't intersect with each other and are all contained in $[a_{i,2}, a_{i,j}-1]$. It follows that $\sum_{k \in U} (a_{t_k,q_k-1} - a_{t_k,2}+1) \leq a_{i,j}-a_{i,2}$. $\blacksquare$ As a corollary we have $W(i, j) \leq 2^{n+1}$ for all $i,j$. Call a pair $(i,j)$ beautiful if the following holds: $j \in S_i, p>2$ and $W(i,p) \leq 2 W(i,p-1)$ where $j=a_{i,p}$. For any $i$, there are at most $n+1$ indices $j>2$ such that $(i, a_{i,j})$ is not beautiful, as otherwise $W(i,L_i) \geq 2^{n+2} W(i,2) > 2^{n+1}$. So, there are at most $n+3$ indices $j$ such that $(i,a_{i,j})$ is non-beautiful. Claim: For any $x$ there can be at most $n+2$ values of $i$ such that $(i,x)$ is beautiful. Proof: Assume otherwise, let $t_1 < \cdots < t_{n+3}$ be such that $(t_1, x), \cdots , (t_{n+3}, x)$ are all beautiful. Let $x$ be the $q_i$th element of $t_i$. By assumption $q_i>2$. We have $$W(t_i, q_i) \leq 2 W(t_i, q_{i}-1) \implies 1+\sum_{j \leq i} W(t_j, q_j-1) \leq 2W(t_i, q_i-1) \implies W(t_i, q_i-1) \geq 1+\sum_{j<i} W(t_j, q_j-1)$$Now $$W(t_1, q_1-1) \geq 1 \implies W(t_2, q_2-1) \geq 2 \implies W(t_3, q_3-1) \geq 4 \implies W(t_4, q_4-1) \geq 8 \implies \cdots $$By easy induction $W(t_i, q_i-1) \geq 2^{i-1}$. So $W(t_{n+3}, q_{n+3}-1) \geq 2^{n+2} > 2^{n+1}$, contradiction. $\blacksquare$ Now, the number of beautiful pairs is at most $(n+2)2^{n+1}$, so there exists an $i$ which is involved in at most $2n+4$ beautiful pairs. Thus, there are at most $2n+4$ indices $j$ such that $(i,a_{i,j})$ is beautiful. As shown before, there are at most $n+3$ indices $j$ such that $(i,a_{i,j})$ is non-beautiful. It follows that $|S_i| \leq 3n+7$.