MathDB
Problems
Contests
National and Regional Contests
Greece Contests
Greece National Olympiad
2022 Greece National Olympiad
4
4
Part of
2022 Greece National Olympiad
Problems
(1)
How many elements can a good set contain?
Source: Greece National Olympiad 2022, Problem 4
2/26/2022
Let
Q
n
Q_n
Q
n
be the set of all
n
n
n
-tuples
x
=
(
x
1
,
…
,
x
n
)
x=(x_1,\ldots,x_n)
x
=
(
x
1
,
…
,
x
n
)
with
x
i
∈
{
0
,
1
,
2
}
x_i \in \{0,1,2 \}
x
i
∈
{
0
,
1
,
2
}
,
i
=
1
,
2
,
…
,
n
i=1,2,\ldots,n
i
=
1
,
2
,
…
,
n
. A triple
(
x
,
y
,
z
)
(x,y,z)
(
x
,
y
,
z
)
(where
x
=
(
x
1
,
x
2
,
…
,
x
n
)
x=(x_1,x_2,\ldots,x_n)
x
=
(
x
1
,
x
2
,
…
,
x
n
)
,
y
=
(
y
1
,
y
2
,
…
,
y
n
)
y=(y_1,y_2,\ldots,y_n)
y
=
(
y
1
,
y
2
,
…
,
y
n
)
,
z
=
(
z
1
,
z
2
,
…
,
z
n
)
z=(z_1,z_2,\ldots,z_n)
z
=
(
z
1
,
z
2
,
…
,
z
n
)
) of distinct elements of
Q
n
Q_n
Q
n
is called a good triple, if there exists at least one
i
∈
{
1
,
2
,
…
,
n
}
i \in \{1,2, \ldots, n \}
i
∈
{
1
,
2
,
…
,
n
}
, for which
{
x
i
,
y
i
,
z
i
}
=
{
0
,
1
,
2
}
\{x_i,y_i,z_i \}=\{0,1,2 \}
{
x
i
,
y
i
,
z
i
}
=
{
0
,
1
,
2
}
. A subset
A
A
A
of
Q
n
Q_n
Q
n
will be called a good subset, if any three elements of
A
A
A
form a good triple. Prove that every good subset of
Q
n
Q_n
Q
n
contains at most
2
⋅
(
3
2
)
n
2 \cdot \left(\frac{3}{2}\right)^n
2
⋅
(
2
3
)
n
elements.
combinatorics