Minimum number of values in the union of 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

Minimum number of values in the union of sets

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Simon Marais Mathematics Competition 2023 Paper A Problem 3

The post below has been deleted. Click to close.

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

14 posts

#1 h Oct 14, 2023, 8:55 AM

Y by

For each positive integer $n$ , let $f(n)$ denote the smallest possible value of $|A_1 \cup A_2 \cup \dots \cup A_n|$ where $A_1, A_2, A_3 \dots 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$ .

Z K Y

The post below has been deleted. Click to close.

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

10471 posts

#2 h Oct 15, 2023, 4:43 PM

Y by

First we derive some small values and then we use two lemmata to show that $f(n)=n+2$ for $n\ge 3$ .
We call a collection of sets good if the condition of the problem is satisfied, hence no inclusions and distinct cardinalities.
- we have $f(1)=0$ if you consider this case.
- suppose $A_1,A_2\subset [1,2]$ is good . Then the $|A_k|\in \{1,2\}$ are distinct, hence one of them equals 2. Contradiction. With $\{1\},\{2,3\}$ we have $f(2)=3$ .
- suppose $A_1,A_2,A_3\subset [1,4]$ is good. Then the $|A_k|\in \{1,2,3\}$ are distinct, hence wlog $A_3=\{4\}$ and $A_1,A_2\subset \{1,2,3\}$ with cardinalities 2,3. Hence one of them is $\{1,2,3\}$ , contradiction. With $\{1,4\},\{2,3,4\},\{5\}$ we see that $f(3)=5$ .

Lemma 1. Suppose $A_1,\cdots, A_n\subset [1,n+2]$ are good with cardinalities $1,\cdots,n$ . Then we can construct the same for $n+2$ . Proof: let $B_k:=A_k\cup \{n+3\}, B_{n+1}:=[1,n+2],B_{n+2}=\{n+4\}$ .

With induction base $n=2,3$ we find that $f(n)\le n+2$ for all $n\ge 2$ .

Lemma 2. Suppose that $n\ge 3$ and $f(n)\le n+1$ . Then also $f(n-1)\le n$ .
Proof: suppose that $A_1,\cdots,A_n\subset [1,n+1]$ is good. The $|A_k|\in [1,n]$ are distinct hence wlog $A_n=\{n+1\}$ . Then $A_1,\cdots, A_{n-1}\subset [1,n]$ are good.

Now suppose that $f(n)\le n+1$ for some $n\ge 3$ . Then $n>3$ and we can use Lemma 2 to obtain $f(n-1)\le n$ etc until $f(3)\le 4$ . Contradiction, hence $f(n)=n+2$ for $n\ge 3$ .

This post has been edited 2 times. Last edited by alexheinis, Oct 15, 2023, 8:37 PM

Z K Y

The post below has been deleted. Click to close.

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

1474 posts

math90

#3 h Oct 16, 2023, 8:31 PM

Y by

Above: nice solution. BTW, you can prove that $f(n)\ge n+2$ for $n\ge 3$ directly: suppose that $A_1,\cdots,A_n\subset [1,n+1]$ is good. Then since $A_i\not\subset A_j$ and $|A_i|\ne |A_j|$ for $i\ne j$ and $n\ge 3$ , the sizes of $A_i$ are $1,\ldots,n$ . Hence we can assume WLOG $A_n=\{n+1\}$ . Then $A_1,\cdots, A_{n-1}\subset [1,n]$ are good of sizes $2,\ldots,n$ . WLOG $A_{n-1}=\{1,\ldots,n\}$ . But then $A_{n-2}\subset A_{n-1}$ (here we use the assumption $n\ge 3$ ), contradiction.

This post has been edited 4 times. Last edited by math90, Oct 16, 2023, 10:17 PM
Reason: Thanks @below

Z K Y

The post below has been deleted. Click to close.

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

10471 posts

#5 h Oct 16, 2023, 9:32 PM • 1 Y

Y by math90

@math90: Thank you. What you write is nearly correct, we don't have inclusions in a good collection hence $A_i\subset A_j$ is not true when $i<j$ . The cardinalities are distinct, however, and that's why we have $1,\cdots,n$ for the cardinalities. The rest of your argument is fine.

This post has been edited 1 time. Last edited by alexheinis, Oct 16, 2023, 9:33 PM

Z K Y

The post below has been deleted. Click to close.

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

1474 posts

math90

#6 h Oct 16, 2023, 10:14 PM

Y by

Thanks, corrected now.

This post has been edited 1 time. Last edited by math90, Oct 16, 2023, 10:16 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a