Compact sets

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Compact sets

G H J

Reveal topic tags

combinatorics unsolved

L

G H BBookmark kLocked kLocked NReply

Source: Iran TST 2014, third exam, day 2, problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

97 posts

#1 h Jan 1, 2015, 8:53 PM • 4 Y

Y by wiseman, a-shi2213, Mathuzb, Adventure10

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

This post has been edited 1 time. Last edited by TheOverlord, Jul 23, 2016, 3:29 PM
Reason: proposer added

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

46 posts

#2 h Feb 24, 2015, 2:12 PM • 2 Y

Y by Adventure10, Mango247

Aren't there at least $2^{n-1}$ compact subsets? Could someone give a counter example for my assertion ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

307 posts

#3 h Mar 13, 2018, 9:51 AM • 2 Y

Y by Adventure10, Mango247

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}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

578 posts

#4 h Jul 8, 2019, 6:01 PM • 4 Y

Y by Chokechoke, Adventure10, Mango247, amirhsz

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$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a