2006 Romanian NMO Problems/Grade 10/Problem 1

Problem

Let $M$ be a set composed of $n$ elements and let $\mathcal P (M)$ be its power set. Find all functions $f : \mathcal P (M) \to \{ 0,1,2,\ldots,n \}$ that have the properties

(a) $f(A) \neq 0$ , for $A \neq \phi$ ;

(b) $f \left( A \cup B \right) = f \left( A \cap B \right) + f \left( A \Delta B \right)$ , for all $A,B \in \mathcal P (M)$ , where $A \Delta B = \left( A \cup B \right) \backslash \left( A \cap B \right)$ .

Solution

I claim that $f(A)=|A|$ , for all $A\in \mathcal P(M)$ . Clearly this function works; we must now show that it is the only function with the two given properties. We shall do this by proving that any such function $f$ that satisfies both properties must be $f(A)=|A|$ .

We have $f(\emptyset) = f(\emptyset) + f(\emptyset)$ , hence $f(\emptyset) = 0$ . Also, if $A \subset B \subset M$ , then $f(B) = f(A) + f(B-A)$ since $B = B \cup A$ , $A = B \cap A$ , and $B-A = B\Delta A$ .

Let $A_{0} = \emptyset \subsetneq A_{1} \subsetneq \dotsb \subsetneq A_{n-1} \subsetneq A_{n} = M$ be an increasing sequence of subsets of $M$ , such that $A_{i} = A_{i-1} \cup \{a_{i}\}$ for all $i=1,\dotsc,n$ . Then $|A_{i}| = i$ for all $i$ .

Note that $f(a_{i}) \ge 1$ for any $i$ , from property (a). Hence $f(A_{0}) = 0 < f(A_{1}) < \dotsb < f(A_{n-1}) < f(A_{n}) \le n \;,$ which implies $f(A_{i}) = i$ for all $i$ .

Page

Toolbox

Search

2006 Romanian NMO Problems/Grade 10/Problem 1

Problem

Solution

See Also