Problem A. 464. (November 2008)
A. 464. Let H a set and denote by P(H) the family of all subsets of H. Suppose that f and g are P(H)P(H) maps such that f(X)f(Y)H and g(X)g(Y)H whenever XYH. Prove that there exist sets A,BH for which f(A)=H\B and g(B)=H\A.
Deadline expired on December 15, 2008.
Solution. For every XH, let h(X)=H\g(H\f(X)). Our goal is to construct a set AH for which h(A)=A,
The function the function h s nondecreasing, i.e. h(X)h(Y) whenever XYH.
Call a set XH "nice" if Xh(X) and let A be the union of all nice sets:
We will show that h(A)=A. Let A'=h(A).
For every nice set X we have XA and thus Xh(X)h(A). Then
Therefore, the set A is nice, Ah(A).
Since h is nondecreasing, the set A' is nice as well; A'=h(A)h(A'). On the othe hand, A is the union of all nice sets, so A'=h(A) is a subset of A.
Hence, Ah(A) and h(A)A. Therefore A=h(A).
9 students sent a solution. 5 points: Backhausz Tibor, Bodor Bertalan, Éles András, Tomon István, Tossenberger Anna. 2 points: 2 students. 0 point: 2 students.