MathDB
Problems
Contests
National and Regional Contests
Bulgaria Contests
Bulgarian Spring Mathematical Competition
2023 Bulgarian Spring Mathematical Competition
12.4
12.4
Part of
2023 Bulgarian Spring Mathematical Competition
Problems
(1)
Find large subset of A not containing entirely any A_i
Source: Bulgarian Spring Tournament 2023 12.4
3/25/2023
Given is a set
A
A
A
of
n
n
n
elements and positive integers
k
,
m
k, m
k
,
m
such that
4
≤
k
<
n
4 \leq k <n
4
≤
k
<
n
and
m
≤
min
{
k
−
3
,
n
2
}
m \leq \min \{k-3, \frac {n} {2}\}
m
≤
min
{
k
−
3
,
2
n
}
. Let
A
1
,
A
2
,
…
,
A
l
A_1, A_2, \ldots, A_l
A
1
,
A
2
,
…
,
A
l
be subsets of
A
A
A
, all with size
k
k
k
, such that
∣
A
i
∩
A
j
∣
≤
m
|A_i \cap A_j| \leq m
∣
A
i
∩
A
j
∣
≤
m
for all
i
≠
j
i \neq j
i
=
j
. Prove that there exists a subset
B
B
B
of
A
A
A
with at least
n
m
+
1
+
m
\sqrt[m+1]{n}+m
m
+
1
n
+
m
elements which doesn't contain entirely any of the subsets
A
1
,
A
2
,
…
,
A
l
A_1, A_2, \ldots, A_l
A
1
,
A
2
,
…
,
A
l
.
combinatorics