A uniform covering of the integers $1,2,...,n$ is a finite multiset of subsets of $\{1,2,...,n\}$, so that each number lies in the same amount of sets from the covering. A covering may contain the same subset multiple times, it must contain at least one subset, and it may contain the empty subset. For example, $(\{1\},\{1\},\{2,3\},\{3,4\},\{2,4\})$ is a uniform covering of $1,2,3,4$ (every number occurs in two sets). The covering containing only the empty set is also uniform (every number occurs in zero sets). Given two uniform coverings, we define a new uniform covering, their sum (denoted by $\oplus$), by adding the sets from both coverings. For example: $(\{1\},\{1\},\{2,3\},\{3,4\},\{2,4\})\oplus(\{1\},\{2\},\{3\},\{4\})=$ $(\{1\},\{1\},\{1\},\{2\},\{3\},\{4\},\{2,3\},\{3,4\},\{2,4\})$ A uniform covering is called non-composite if it's not a sum of two uniform coverings. Prove that for any $n\geq1$, there are only finitely many non-composite uniform coverings of $1,2,...,n$.
Problem
Source: Israel National Olympiad 2018 Q7
Tags: combinatorics, Sets, covering
09.08.2019 15:00
We will prove the result using induction on $n$. The base-case is obvious. For any uniform covering $S_k$ of the integers $1,2,\dots k$ let $A(S_k)$ denote the number of times each element of $\{1,2,\dots k\}$ appears and let $B(S_k)$ denote the number of not necessarily different subsets contained in $S_k$. For instance if $S_3=\{\{1,2\},\{2,3\},\{1,3\}\}$ then $A(S_3)=2$ and $B(S_3)=3$. Assume that there are only finitely many non-composite uniform coverings of $1,2,\dots n-1$. Of all the non-composite uniform coverings $S_{n-1}$ let $A$ be the maximum of $A(S_{n-1})$ and $B$ be the maximum of $B(S_{n-1})$. Thus if there exists a uniform covering $S_{n-1}$ with $A(S_{n-1})>A$ or $B(S_{n-1})>B$ it has to be composite. Assume for contradiction that there exists infinitely many non-composite uniform coverings of $1,2,\dots n$. Note that for each $k$ there can only be finitely many non-composite uniform coverings $S_n$ with $A(S_n)=k$. Thus we can for any $N$ find a non-composite uniform covering $S_n$ such that $A(S_n)>N$. Pick a very big $N$ and a non-composite uniform covering $S_n$ with $A(S_n)>N$. For now ignore the number $n$ completely, and let $S_{n-1}$ denote the uniform covering we obtain from $S_n$. Now since $A(S_{n-1})=A(S_{n})>A$ we have that $S_{n-1}$ must be composite, which means that we can split it into two new uniform coverings $S^{1}_{n-1}$ and $S^{2}_{n-1}$. Clearly $A(S^1_{n-1})+A(S^2_{n-1})=A(S_{n-1})$. Using the induction hypothesis we can continue this procedure until we are left with uniform coverings $K^1_{n-1},K^2_{n-1}, \dots K^{i}_{n-1}$ such that $A(K^{j}_{n-1})\leq A$ and $B(K^{j}_{n-1})\leq B$ for every $1\leq j\leq i$. We have $N<A(S_{n-1})=\sum A(K^{j}_{n-1})\leq A*i \Rightarrow i>\frac{N}{A}$. This means that $i$ is unbounded. Now we return our attention back to element $n$. Let $k_j$ denote the number of times $n$ appears in the uniform covering $K^{j}_{n-1}$ and let $m_j=A(K^{j}_{n-1})$. Let $K$ be a proper non-empty subset of $\{1,2,\dots i\}$. If we have $\sum_{j\in K} (k_j-m_j)=0$ this would mean that we could merge the coverings $K^{j}_{n-1}$ for $j\in K$ back together and obtain a covering in which $n$ appears the same number of times as any other element i.e. a uniform covering. Since $K \neq \{1,2,\dots i\}$ and $K\neq \emptyset$ this would contradict the assumption that $S_{n}$ originally was non-composite. Clearly we have that $k_j$ and $m_j$ are non-negative integers. Also note that $m_j\leq A$ and that $n$ can appear at most once for each subset of $\{1,2,\dots n\}$ implying $k_j \leq B$. Create the sequence $\{a\}$ given by $a_j=k_j-m_j$. Note that $-A\leq a_j\leq B$. If $\exists j$ such that $a_j=0$ we are clearly done. Thus we can split the terms into a positive group and a negative group. Let $C$ be the multiset containing the positive terms and let the sum of its elements be $c$ while $D$ is the multiset containing the negative ones with sum of elements equalling $d$. We have $c-d=|c|+|d|\geq i$ and $c+d=0$, combining this gives $c\geq \frac{i}{2}$ and $d\leq \frac{-i}{2}$. Since the sum of elements in $C$ and $D$ is unbounded while the terms of the sequence $\{a\}$ is bounded we have that we can find as many equal elements in each of $C$ and $D$ as we need. Hence we assume that we have at least $A+B+1$ copies of the elements $c_1\in C$ and $d_1\in D$. We have $|d_1|\leq A$ and $|c_1|\leq B$ implying that we can choose $-d_1$ copies of $c_1$ and $c_1$ copies of $d_1$ to obtain $(-d_1)c_1+d_1c_1=0$. Clearly we have at least one copy of each element left, ensuring that we chose a proper subsequence of $\{a\}$. In addition we have $|c_1|+|d_1|>0$ meaning that the subsequence we chose was non-empty. Hence, the induction hypothesis is proven.
22.08.2019 04:51
Notice that there are only $2^n$ distinct sets. Therefore, every covering of the integers $1, 2, \cdots n$ can be represented as a $2^n-$tuple of nonnegative integers $(a_1, a_2, \cdots, a_{2^n}),$ with each of the integers corresponding to the number of a certain set in the covering. Furthermore, observe that no two non-composite coverings can be contained within one another. We will show the following more general statement. For any positive integer $d$ and any infinite sequence $A_1, A_2, A_3, \cdots$ of $d-$tuples of nonnegative integers, there exist $x < y$ such that the $i$th coordinate of $A_x$ is less than or equal to that of $A_y$, for each $1 \le i \le d.$ We will show this by induction on $d$. When $d = 1$, this is obvious, as else the sequence is strictly decreasing. Suppose that it holds when $d = k$. When $d = k+1$, we will consider two cases. Case 1. The first coordinates of the $d-$tuples take on only finitely many values Then, there exists an infinite subsequence so that the first coordinates are all the same by Infinite Pigeonhole. From here, we're done directly by applying the inductive hypothesis on this subsequence. Case 2. The first coordinates of the $d-$tuples take on infinitely many values Then, there exists an infinite subsequence such that the first coordinates are strictly increasing. Again, we're done by applying the inductive hypothesis on this subsequence. As we've exhausted all cases, the induction is complete. Finally, it remains to examine the case when $d = 2^n$, and use contradiction to solve the problem. $\square$