# Family of sets $\{A_i\}_{i=1}^n$ such that $A_i\not \subseteq A_j$ and $|A_i|\neq |A_j|$ for all distinct $i$,$j$.

This problem is from the Simon Marais Mathematics Competition Paper A which was conducted a couple of days ago (on October 14, 2023).

Problem statement (verbatim):

For each positive integer $$n$$, let $$f(n)$$ denote the smallest possible value of $$|A_1\cup A_2\cup \cdots\cup A_n|$$ where $$A_1$$, $$A_2$$, $$\ldots$$, $$A_n$$ are sets such that $$A_i\not\subseteq A_j$$ and $$|A_i|\neq |A_j|$$ whenever $$i\neq j$$. Determine $$f(n)$$ for each positive integer $$n$$.

My attempt:

The case $$n=1$$ is trivial, we take $$A_1=\emptyset$$ and hence, $$f(1)=0$$.

In other cases, without loss of generality, we may assume $$|A_1|<|A_2|<\ldots<|A_n|$$. Since we need the least value of $$f(n)$$, take $$|A_i|=i$$.

Case $$n=2$$: $$A_1=\{1\}$$, $$A_2=\{2,3\}$$ and $$f(2)=3$$.

Case $$n=3$$: $$A_1=\{1\}$$, $$A_2=\{2,3\}$$, $$A_3=\{2,4,5\}$$ and $$f(3)=5$$.

Case $$n=4$$: $$A_1=\{1\}$$, $$A_2=\{2,3\}$$, $$A_3=\{2,4,5\}$$, $$A_4=\{3,4,5,6\}$$ and $$f(4)=6$$.

I can't think of how to proceed constructively to determine $$f(n)$$ for any $$n\in\mathbb Z^+$$.

I think the general idea is to take the set $$X=\{1,2,\ldots, f(n)\}$$ and consider its subsets which don't contain each other and their union is $$X$$ itself.

I expect to see a combinatoric approach which yields a nice closed form for $$f(n)$$...

I think the answer is: $$f(n)=n+2 \;\;\;\;\;\;\; \mathrm{for} \; n \geq 3.$$

This can be proved by induction.

Since the OP has already established that $$f(3)=5$$ and $$f(4)=6$$. The statement is true for $$n=3$$ and $$n=4$$.

We need only prove that if the statement is true for $$n=k$$, then it is true for $$n=k+2.$$

For simplicity, let us see how to prove that if $$f(4)=6$$, then $$f(6)=8$$. The general case is just the same.

Let us fill up the smallest and the largest sets, i.e. $$A_1$$ and $$A_6$$ first.

So we may let $$A_1=\{ 1\}$$ and $$A_{6}=\{ 2, 3, \cdots, 7\}.$$  Next we consider $$A_2$$ to $$A_5$$.

Obviously each $$A_i$$ must contain at least one element other than $$1, 2, \cdots, 7$$. We must introduce at least one more element, say $$8$$.

Therefore at least $$8=6+2$$ elements are needed.

To see that the addition of $$8$$ is enough, we may reason as follows:

First assign $$8$$ to each each $$A_i, \; i=2, 3,4, 5$$. Thus

$$A_2 = \{8, x \}$$, $$A_3 = \{8, x, x \}$$, $$A_4 = \{8, x, x, x \}$$, $$A_5= \{8, x, x, x, x\}$$.

where the $$x$$'s are elements to be filled in.

We may also write it as follows:

$$A_2=\{8 \}\cup B_1, A_3=\{8 \}\cup B_2, A_4=\{8 \}\cup B_3 \; \mathrm{and \; A_5=\{8 \}\cup B_4}$$

where $$|B_i|=i$$ and $$B_i \not\subset B_j$$ whenever $$i \neq j.$$

Thus to fill up $$B_2$$ to $$B_5$$ is just the same question asked with $$n=4.$$

Can we fill up $$B_2$$ to $$B_5$$ by using the elements of $$\{2, 3, 4, 5, 6, 7\}$$ so that no extra element is needed?

The answer is yes. This is because $$f(4)=6$$ and there are exactly $$6$$ elements in $$\{2, 3, 4, 5, 6, 7\}$$.

For concreteness, we may let $$B_1=\{ 2\}, B_2=\{3, 4\}, B_3=\{3, 5, 6 \} \; \mathrm{and} \; B_4=\{4, 5, 6, 7 \}$$ and finally obtain $$A_1=\{1\}, A_2=\{8, 2\}, A_3=\{8, 3, 4\}, A_4=\{8, 3, 5, 6 \}, A_5=\{8, 4, 5, 6, 7 \} \; \mathrm{and} \; A_6=\{2, 3, 4, 5, 6, 7 \}$$

Thus we have proved that $$f(6)=8$$ if $$f(4)=6$$.

Same arguments obviously apply for all $$n$$.

Therefore if the statement is true for $$n=k$$, then it is true for $$n=k+2.$$

By the principle of mathematical induction, $$f(n)=n+2 \;\;\;\;\;\;\; \mathrm{for} \; n \geq 3.$$

• I can't believe that the closed form of $f(n)$ is so simple.... I wish I had computed $f(5)$ and $f(6)$ on the day of the competition... I would have figured out the formula simply by observing... Thank you for this answer... I learned so much! :) Commented Oct 16, 2023 at 13:30

I think duality is the key (but maybe we don't need it). Suppose sets $$A_1, A_2, \ldots, A_n$$ satisfy the condition. Then, for any set $$X$$ including $$A_1 \cup A_2 \cup \cdots \cup A_n$$, the complements $$\overline A_1 = X - A_1,\ \overline A_2, \ldots, \overline A_n$$ also satisfy the condition.

We show that $$f(n)=n+2$$ for $$n \geq 3$$ by constructing subsets $$A_1, A_2, \ldots, A_n$$ of $$[n+2] = \{1,2,\ldots,n+2\}$$ so that $$|A_k| = k+1$$. (It is easy to see that $$n+2$$ is the smallest number possible.)

Suppose $$n \geq 4$$ and let $$A_n = \{1,2,\ldots,n+1\}$$. Other sets $$A_k$$ should contain $$n+2$$. Now it is enough to construct $$B_k = A_k - \{n+2\}$$ so that:

• each $$B_k$$ is a subset of $$[n+1]$$,
• $$|B_k| = k$$,
• sets $$B_1, B_2, \ldots, B_{n-1}$$ satisfy the condition.

We rewrite these conditions in terms of $$C_k = \overline B_{n-k} = [n+1] - B_{n-k}$$:

• each $$C_k$$ is a subset of $$[n+1]$$,
• $$|C_k| = k+1$$,
• sets $$C_1, C_2, \ldots, C_{n-1}$$ satisfy the condition.

Hence the usual induction implies the claim.