Obscure Set Problem

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

Obscure Set Problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Romania Junior TST 2025 Day 1 P5

The post below has been deleted. Click to close.

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

1742 posts

oVlad

#1 h Apr 12, 2025, 9:59 AM

Y by

Let $n\geqslant 3$ be a positive integer and $\mathcal F$ be a family of at most $n$ distinct subsets of the set $\{1,2,\ldots,n\}$ with the following property: we can consider $n$ distinct points in the plane, labelled $1,2,\ldots,n$ and draw segments connecting these points such that points $i$ and $j$ are connected if and only if $i{}$ belongs to $j$ subsets in $\mathcal F$ for any $i\neq j.$ Determine the maximal value that the sum of the cardinalities of the subsets in $\mathcal{F}$ can take.

Z K Y

The post below has been deleted. Click to close.

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

69 posts

kokcio

#2 h Apr 12, 2025, 10:57 AM

Y by

We know that $i$ is in $j$ subsets if and only if $j$ is in $i$ subsets, because of there is segment between $i,j$ if and only if there is segment between $j,i$ .
Let $a_k$ be a number of subsets, which contain $k$ . Assume that $a_k=a_l=m$ for some integers $k,l,m$ and $m>0$ . Then, we would have to have that $k=a_m=l$ from our first sentence. This means that all $a_i$ , which are greater than $0$ have to pairwise different. This means that $a_1+a_2+...+a_n\leq1+2+...+n=\frac{n(n+1)}{2}$ , but sum of cardinalities of subsets in $\mathcal{F}$ is equal to $a_1+a_2+...+a_n$ , so we have upper bound. We can make $a_1+a_2+...+a_n=\frac{n(n+1)}{2}$ for subsets $\{1\},\{1,2\},...,\{1,2,...,n\}$ (because $a_i=n+1-i$ ), so maximal sum of cardinalities of subsets in $\mathcal{F}$ is $\frac{n(n+1)}{2}$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a