MathDB
Problems
Contests
National and Regional Contests
Romania Contests
Romania National Olympiad
2006 Romania National Olympiad
1
Function on the power set
Function on the power set
Source: RMO 2006, 10th grade
April 17, 2006
function
induction
algebra proposed
algebra
Problem Statement
Let
M
\displaystyle M
M
be a set composed of
n
\displaystyle n
n
elements and let
P
(
M
)
\displaystyle \mathcal P (M)
P
(
M
)
be its power set. Find all functions
f
:
P
(
M
)
→
{
0
,
1
,
2
,
…
,
n
}
\displaystyle f : \mathcal P (M) \to \{ 0,1,2,\ldots,n \}
f
:
P
(
M
)
→
{
0
,
1
,
2
,
…
,
n
}
that have the properties (a)
f
(
A
)
≠
0
\displaystyle f(A) \neq 0
f
(
A
)
=
0
, for
A
≠
ϕ
\displaystyle A \neq \phi
A
=
ϕ
; (b)
f
(
A
∪
B
)
=
f
(
A
∩
B
)
+
f
(
A
Δ
B
)
\displaystyle f \left( A \cup B \right) = f \left( A \cap B \right) + f \left( A \Delta B \right)
f
(
A
∪
B
)
=
f
(
A
∩
B
)
+
f
(
A
Δ
B
)
, for all
A
,
B
∈
P
(
M
)
\displaystyle A,B \in \mathcal P (M)
A
,
B
∈
P
(
M
)
, where
A
Δ
B
=
(
A
∪
B
)
\
(
A
∩
B
)
\displaystyle A \Delta B = \left( A \cup B \right) \backslash \left( A \cap B \right)
A
Δ
B
=
(
A
∪
B
)
\
(
A
∩
B
)
.
Back to Problems
View on AoPS