Given an integer $n\ge3$, prove that the set $X=\{1,2,3,\ldots,n^2-n\}$ can be divided into two non-intersecting subsets such that neither of them contains $n$ elements $a_1,a_2,\ldots,a_n$ with $a_1<a_2<\ldots<a_n$ and $a_k\le\frac{a_{k-1}+a_{k+1}}2$ for all $k=2,\ldots,n-1$.
Problem
Source:
Tags: induction, inequalities, combinatorics proposed, combinatorics
31.05.2010 01:32
Can we try something like this: suppose we want to partition $X$ into $A$ and $B$, Put 1 into $A$, 2 into $B$ put 3,4 into $A$, 5,6 into $B$ put 7,8,9 into $A$, 10, 11, 12 into $B$ ...and so on We can show that this partition satisfies the requirement of the problem via induction. It's easily verifiable for $n=3$. Now for $n$, we see the last two "rows" in the division above: ... we put $(n-2)(n-3) + 1,..., (n-2)^2$ into $A$ and $(n-2)^2+1,...,(n-1)(n-2)$ into $B$ we put $(n-1)(n-2) + 1,..., (n-1)^2$ into $A$ and $(n-1)^2+1,...,n(n-1)$ into $B$ Suppose that there is a subsequence of length $n$ that violates the condition, we consider whether they're in group $A$ or $B$. Case 1: they're in group $A$. We know from the induction hypothesis that there is no subsequence of length $n-1$ in the first $n-2$ rows, because that's exactly the partition we use in the induction hypothesis. So that means that $a_{n-1}$ and $a_n$ are both in the last row. $a_n - a_{n-1} \leq (n-1)^2-(n-1)(n-2)-1 = n-2$ but $a_{n-1} - a_{n-2} \geq (n-1)(n-2) +1 - (n-2)^2 = n-1$ So $a_n - a_{n-1} < a_{n-1}-a_{n-2}$. Contradiction. Case 2: they're in group $B$. As before, we know from the induction hypothesis that $a_{n-1}$ and $a_n$ must both be in the last row. $a_n - a_{n-1} \leq n(n-1)-(n-1)^2-1 = n-2$ but $a_{n-1} - a_{n-2} \geq (n-1)^2 +1 - (n-1)(n-2) = n-1$ again, we derive a contradiction.
31.05.2010 05:34
It is similar with the official solution. Outline of my proof: The case $n=3$ is trivial, assume $n\ge4$. We call such $n$ elements set a "convex set". Given an increasing sequence of positive integers $d_1,\ldots,d_{n-1}$ with $d_1+\ldots+d_{n-1}=k$, there exist $n^2-n-k$ convex set with $a_{k+1}-a_k=d_k$. Since $d_1+\ldots+d_{n-1}=k$ has at most ${k-1\choose n-2}$ solutions and $n-1\le k\le n^2-n-1$, then the total number of convex set is at most $\sum_{k=n-1}^{n^2-n-1}(n^2-n-k){k-1\choose n-2}<(n^2-2n+1){n^2-n\choose n-1}$. It is easy to verify that this expression is not greater than $2^{n^2-n-1}$ for $n\ge4$. But there are $2^{n^2-n-1}$ possible partition of $X$, so there exist a partition which does not contain any convex set. Is it correct?
31.05.2010 17:56
Hello, two questions regarding your solution. 1. The inequality that the sum on the LHS is less than the RHS. I'm sure it's true, but I don't yet see an easy way to prove it. But it may not matter that much because eventually you're trying to establish that it's less than $2^{n^-n-1}$. 2. What you proved was that one partition doesn't contain a convex set. But does that guarantee that the other partition also doesn't contain a convex set?
01.06.2010 18:42
Here is my full proof: For $n=3$ we can take $\{1,3,4\}$ and $\{2,5,6\}$. Suppose that $n\ge4$. Call $\{a_1,a_2,\ldots,a_n\}\subset\{1,2,\ldots,n^2-n\}$ "convex" if $a_1<a_2<\ldots<a_n$ and $a_k\le\frac{a_{k-1}+a_{k+1}}2$ for $k=2,3,\ldots,n-1$. Let $d_1\le d_2\le\ldots\le d_{n-1}$ be positive integers such that $d_1+d_2+\ldots+d_{n-1}=k$. We will count the number of convex sets $\{a_1,a_2,\ldots,a_n\}$ such that $a_{k+1}-a_k=d_k$ for $k=1,\ldots,n-1$. Such convex set can be determined uniquely from $a_n$ and $d_1,d_2,\ldots,d_{n-1}$. Note that $n^2-n\ge a_n\ge1+k$, so there are $n^2-n-k$ possible values for $a_n$ (whence we conclude $k\le n^2-n-1$), and hence, given $d_1,\ldots,d_{n-1}$, we have $n^2-n-k$ convex sets. But $d_1+d_2+\ldots+d_{n-1}=k$ has at most ${k-1\choose n-2}$ solutions in positive integers, so the total number of convex sets is at most \[\sum_{k=n-1}^{n^2-n-1}{k-1\choose n-2}(n^2-n-k).\] We claim that this expression is less than $2^{n^2-n-1}$. We have $n^2-n-k\le n^2-2n+1$ and $\sum_{k=n-1}^{n^2-n-1}{k-1\choose n-2}={n^2-n-1\choose n-1}$, so it suffices to prove that $(n-1)^2{n^2-n-1\choose n-1}<2^{n^2-n-1}$. This is true for $n=4$, now assume $n\ge5$. Note that $n^2>3n+1$, $2n^2-4n-2>n^2-n-1$, $n^2-n-1<(n^2-2n-1)2\le(n^2-2n-1)(n-2)$, $\frac{(n^2-n-1)!}{(n-1)!(n^2-2n)!}<\frac{(n^2-n-2)!}{(n^2-2n-2)!n!}$, ${n^2-n-1\choose n-1}<{n^2-n-2\choose n}$, now it suffices to prove that $(n-1)^2{n^2-n-2\choose n}<2^{n^2-n-1}$. Note that ${n^2-n-2\choose n}={n^2-n-2\choose n}$, ${n^2-n-2\choose n}<{n^2-n-2\choose n+1}$, $\ldots$, ${n^2-n-2\choose n}<{n^2-n-2\choose n^2-2n-3}$, ${n^2-n-2\choose n}={n^2-n-2\choose n^2-2n-2}$. Add all the inequalities and equations, we get $(n^2-3n-1){n^2-n-1\choose n-1}<\sum_{k=n-1}^{n^2-2n}{n^2-n-1\choose k}<2^{n^2-n-2}$. Now it suffices to prove that $2^{n^2-n-2}\frac{n^2-2n+1}{n^2-3n-1}<2^{n^2-n-1}$, which is equivalent to $n^2-2n+1<2n^2-6n-2$, $n^2>4n+3$, which is true for $n\ge5$. Therefore the number of convex set is less than $2^{n^2-n-1}$. There are $2^{n^2-n}$ subsets of $X$. We pair each subset with its complement, there are $2^{n^2-n-1}$ pairs. Since the number of convex sets is less than $2^{n^2-n-1}$, there exist a pair which does not contain pair. QED Note: A pair of subsets contains a convex sets iff at least one of its subset contain a convex set.
16.12.2010 12:10
How about the converse, I mean, is there a nice bound f(n) that for every positive integer $n \geq 3$, $ X=\{1,2,3,\ldots,f(n)\} $, for each way that we divide X into two non-intersecting subsets, we can find n positive integer $a_{1}<a_{2}<......a_{n} $ in the same subset for which $ a_{k}\le\frac{a_{k-1}+a_{k+1}}{2} $ is right for all $ k=2,\ldots,n-1 $. I can prove $f(n)=n(n^{2}+5)/6$ is able, but I think it's too big.
22.12.2010 17:55
litongyang wrote: How about the converse, I mean, is there a nice bound f(n) that for every positive integer $n \geq 3$, $ X=\{1,2,3,\ldots,f(n)\} $, for each way that we divide X into two non-intersecting subsets, we can find n positive integer $a_{1}<a_{2}<......a_{n} $ in the same subset for which $ a_{k}\le\frac{a_{k-1}+a_{k+1}}{2} $ is right for all $ k=2,\ldots,n-1 $. I can prove $f(n)=n(n^{2}+5)/6$ is able, but I think it's too big. Anyone notice my problem?