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.