Given a set $X=\{x_1,\ldots,x_n\}$ of natural numbers in which for all $1< i \leq n$ we have $1\leq x_i-x_{i-1}\leq 2$, call a real number $a$ good if there exists $1\leq j \leq n$ such that $2|x_j-a|\leq 1$. Also a subset of $X$ is called compact if the average of its elements is a good number. Prove that at least $2^{n-3}$ subsets of $X$ are compact. Proposed by Mahyar Sefidgaran
Problem
Source: Iran TST 2014, third exam, day 2, problem 2
Tags: combinatorics unsolved, combinatorics
24.02.2015 16:12
Aren't there at least $2^{n-1}$ compact subsets? Could someone give a counter example for my assertion ?
13.03.2018 12:51
I think $2^{n-3}$ is a very weak bound. I haven't found a counterexample for $2^{n-1}$. But here's a proof for $2^{n-3}$: As $1$ element subsects work $n<6$ is trivial. Let $f(B)$ where $B$ is a binary string denote the average of the subset $B$ of $X$. Consider all non-empty binary strings of length $n-1$ containing an even number of $1$'s. There are $2^{n-2}-1$ such strings. We split the string into two parts $A,B$ with $B$ starting directly after the $\frac{k}{2}^{\text{th}}$ $1$ in the string. We consider the $3$ strings: $AB0,A0B,0AB$ and prove at least one denotes a compact subset by contradiction. Let $x_1<f(AB0)<x_2$. Clearly $x_2=x_1+2$ otherwise $AB0$ is compact so $x_1+\frac{1}{2}<f(AB0)<x_1+\frac{3}{2}=x_2-\frac{1}{2}$. By shifting $B$ forward $1$ we increase the average by between $\frac{1}{2}$ and $1$. For this to also not be compact we see: $x_1+1<f(A0B)<x_1+\frac{3}{2}$ but then by shifting $A$ forward by $1$ to get $0AB$ we see this must be a compact set. We can reverse the process from all compact sets with an even number of $1$'s and deleting a $0$ from the start, end and middle (i.e. between the $2$ middle $1$'s) and so each such sequence is counted at most $3$ times hence there are at least $\frac{2^{n-2}-1}{3}$ such sequences. We now consider the strings of length $n-1$ with an odd number of $1$'s. There are $2^{n-2}$ such sequences. Let there be $2k+1$ $1$'s in a given sequence. We split them into $A$ starting after the first $1$ and $B$ starting after the $(k+1)^{\text{th}}$ $1$. This time we will prove one of $1AB0,1A0B,10AB,01AB$ is compact again by contradiction. We get: $$x_1+\frac{1}{2}<f(1AB0)<x_1+\frac{3}{2}=x_2-\frac{1}{2}$$Then by shifting $B$ we increase the average by between $\frac{k}{2k+1},\frac{2k}{2k+1}<1$ and similarly for $A$ so we get: $$x_1+\frac{1}{2}+\frac{k}{2k+1}<f(1A0B)<x_1+\frac{3}{2} \quad , \quad x_1+\frac{1}{2}+\frac{2k}{2k+1}<f(10AB)<x_1+\frac{3}{2}$$And so by moving the $1$ we shift by at least $\frac{1}{2k+1}$ so we see $01AB$ is compact yielding the desired contradiction. Now by deleting a $0$ from the start, after the first $1$, after $k+1$ $1$'s and the end we see each odd compact set is counted at most $4$ times so there are at least $\frac{2^{n-2}}{4}$ such compact sets. This shows in total there are at least: $$\frac{2^{n-2}}{4}+\frac{2^{n-2}-1}{3}=2^{n-3}+\frac{2^{n-3}}{12}-1>2^{n-3}-1$$Compact sets so there are at least $2^{n-3}$ compact sets as desired. I hope my solution is correct. By trying examples with a computer it seems the actual bound is much higher probably nearer to $2^{n-1}$
08.07.2019 21:01
Here is a different proof. Fix some even $2 \le k \le n.$ We will use the term $k-$subsets to denote subsets of $X$ of size $k.$ We will show that the number of compact $k-$subsets is at least $\binom{n-2}{k-1}$. This would imply the desired bound since $\sum_{\textit{k odd}} \binom{n-2}{k} = 2^{n-3}.$ So let's show this. Since $x_n \ge x_1 + k-1,$ it's clear that either $x_1 + k-1$ or $x_1 + k$ is in $X$. This is because we either have $x_n \in \{x_1+ k-1, x_1+k\}$ or $x_n > x_1+k.$ In the latter case, it's clear that $X$ cannot "jump over" both of the values $x_1+k-1$ and $x_1+k$, from the condition on $X.$ Therefore, we can let $2 \le t \le n$ be such that $x_t \in \{x_1 + k-1, x_1 + k\}.$ Let $A$ be the set of $k-$subsets containing $x_1$ but not $x_t$, and $B$ be the set of $k-$subsets containing $x_t$ but not $x_1.$ As there exists a clear bijection between $A$ and $B$, we have $|A| = |B|.$ The following claim is the key to obtaining a lower bound. Claim. For every pair of sets $S \in A, T \in B$ such that $|S \cap T| = k-2$ (in other words, $T$ is just $S$ but with $x_t$ instead of $x_1$), at least one of $S, T$ is compact. Proof. Note that the difference between the average of the elements of $S$ and those of $T$ is either $\frac{k-1}{k}$ or $1.$ From here the claim is clear. $\blacksquare$ Since $|A| = |B| = \binom{n-2}{k-1}$, the claim implies that there are at least $\binom{n-2}{k-1}$ compact $k-$subsets, so summing over even $k$ implies the conclusion. $\square$