# 2006 Romanian NMO Problems/Grade 10/Problem 1

## Problem

Let be a set composed of elements and let be its power set. Find all functions that have the properties

(a) , for ;

(b) , for all , where .

## Solution

### Solution 1

I claim that , for all . 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 that satisfies both properties must be .

We have , hence . Also, if , then since , , and .

Let be an increasing sequence of subsets of , such that for all . Then for all .

Note that for any , from property (a). Hence which implies for all .

### Solution 2

I claim that , for all . Clearly this function works; we must now show that it is the only function with the two given properties. We shall do this by constructing a function that does satisfy both properties, and then showing that this function is in fact .

We have , hence . Note that if , then , from property (a). Let and for some . We then have from property that . Since , . This shows that for all with , .

Lemma: for all . Proof: We proceed by induction on . Clearly and if from property (a). This is our base case. Now we do the inductive step. Assume that for all for some positive integer , if . Let and be subsets of such that , and . We then have from property 2 that . From our inductive hypothesis, this sum is at least . This completes the inductive step, which completes the proof.

I shall now prove that for all .

Note that our lemma implies that . Consider a set with cardinality . We then have that and . We then have that and , so their sum (which equals from property (b)) is at least . This then implies that and for all . We defined to be , so . This completes the proof.