1
$\begingroup$

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)$...

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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! :) $\endgroup$ Commented Oct 16, 2023 at 13:30
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .