Solutions of advanced problems A
A. 284. Let f be a function defined on the subsets of a finite set S. Prove that if \(\displaystyle f(S\setminus A)=f(A)\) and max (f(A),f(B))\(\displaystyle \ge\)f(A\(\displaystyle \cup\)B) for all subsets A, B of S, then f assumes at most S distinct values.
(Miklós Schweitzer Memorial Competition, 2001)
Solution 1. If S=\(\displaystyle \emptyset\), the statement is not true. Assume from now on that S is not empty.
The proof is by induction. For S=1 and S=2 the number of complementary pairs of subsets is exactly 1 and 2, respectively, thus the function can have no other values. Now let S>2, and assume that the statement is true for smaller numbers of elements.
Let the m be the largest value of f. First we prove that S has a oneelement subset X={x}, such that f(X)=m. Consider the subsets assigned the number m by the function f. It follows from the complementary property that there is a nonempty set among these subsets. Thus consider the smallest nonempty subset X, such that f(X)=m. If X had at least two elements, it could be expressed as the union of two smaller sets: X=X_{1}\(\displaystyle \cup\)X_{2}, but then, as
max (f(X_{1}),f(X_{2}))\(\displaystyle \ge\)f(X_{1}\(\displaystyle \cup\)X_{2})=f(X)=m,
one of f(X_{1}) and f(X_{2}) would also be m. Therefore, the set X has one element.
Let \(\displaystyle R=S\setminus X\), and define the function \(\displaystyle g:P(R)\to R\) as follows: for all A\(\displaystyle \subset\)R, let
\(\displaystyle
g(A)=\min\big(f(A),f(A\cup X)\big)=\min\big(f(A),f(R\setminus A)\big).
\)
Note that for any A\(\displaystyle \subset\)R, max (f(A),f(A\(\displaystyle \cup\)X))=m, as m = f(X)=f(S\X)=f (A\(\displaystyle \cup\)(R\A)) \(\displaystyle \le\)max (f(A),f(R\A))= = max (f(A),f (S\(R\A)))= max (f(A),f(A\(\displaystyle \cup\)X)).
There remains to prove that the assumption of the induction is true for the function g, that is, \(\displaystyle g(R\setminus A)=g(A)\) and g(A\(\displaystyle \cup\)B)\(\displaystyle \le\)max (g(A),g(B)) for all A,B\(\displaystyle \subset\)R. Then, by the induction hypothesis, g may assume at most (S1) different values. For any set A\(\displaystyle \subset\)R, one of f(A) and f(A\(\displaystyle \cup\)X) is m, and the other is g(A). Hence the range of f can only exceed the range of g by the single element m.
The property \(\displaystyle g(R\setminus A)=g(A)\) can be deduced from the definition of g.
If either of g(A) or g(B) is m, then g(A\(\displaystyle \cup\)B)\(\displaystyle \le\)max (g(A),g(B)) follows trivially. Assume, therefore, that g(A) and g(B) are both smaller than m, that is, one of f(A) and f(A\(\displaystyle \cup\)X), and one of f(B) and f(B\(\displaystyle \cup\)X) are smaller than m. If f(A)< m, then let C=A, otherwise let C=A\(\displaystyle \cup\)X. Similarly, for f(B)< m let D=B, otherwise D=B\(\displaystyle \cup\)X. Then f(C)=g(A) and f(D)=g(B), and the set C\(\displaystyle \cup\)D is either A\(\displaystyle \cup\)B or A\(\displaystyle \cup\)B\(\displaystyle \cup\)X. Therefore, max (g(A),g(B)) = max (f(C),f(D))\(\displaystyle \ge\)f(C\(\displaystyle \cup\)D)\(\displaystyle \ge\) \(\displaystyle \ge\) min (f(A\(\displaystyle \cup\)B),f(A\(\displaystyle \cup\)B\(\displaystyle \cup\)X))=g(A\(\displaystyle \cup\)B). Thus the function g satisfies the conditions, indeed.
Solution 2 (by E. Csóka). The solution is based on the following lemma:
Lemma. For any real number v, let S_{v} be the set of those subsets of the set S for which the value assigned by the function f is not greater than v:
S_{v} = {X\(\displaystyle \subset\)S: f(X)\(\displaystyle \le\)v}.
Then S_{v} is either 0, or a power of 2 that is different from 1.
Proof for the lemma. First observe that S_{v} is closed for complement, union, intersection and difference, that is, for all sets X,Y in S_{v}, \(\displaystyle S\setminus X\), X\(\displaystyle \cap\)Y, X\(\displaystyle \cup\)Y and \(\displaystyle X\setminus Y\) are also in S_{v}. The first two are true because \(\displaystyle f(S\setminus X)=f(X)\le v\), and f(X\(\displaystyle \cup\)Y)\(\displaystyle \le\)max (f(X),f(Y))\(\displaystyle \le\)max (v,v)=v; and both intersection and difference can be expressed in terms of complement and union.
It follows from the closeness under union and complement that if S_{v} is not empty, then S\(\displaystyle \in\)S_{v}.
It follows from the closeness under complement that if S_{v} has at least one element then the complement of that element also belongs to S. Thus the elements of S_{v} can be matched, and thus S_{v} cannot be a oneelement set.
Let the atoms of S_{v} be its nonempty subsets with the minimum number of elements. Thus a nonempty set A\(\displaystyle \in\)S_{v} is an atom if and only if for all X\(\displaystyle \subset\)A, X\(\displaystyle \in\)S_{v} it is true that either X=\(\displaystyle \emptyset\) or X=A.
Two important consequences are immediate: One of them is that if A\(\displaystyle \in\)S_{v} is an atom and X\(\displaystyle \in\)S_{v} is arbitrary, then A is a subset of either X or \(\displaystyle (S\setminus X)\). They contrary would imply that \(\displaystyle A\setminus X\) is a proper subset of A, which contradicts to A being an atom. The other important consequence is that atoms are pairwise disjoint. If there were two nondisjoint atoms, then they would contain each other for the above reason, that is, the two atoms would be identical.
Now we shall prove that every element of the set S is contained in exactly one atom of S_{v}. As the atoms are pairwise disjoint, x can belong to at most one atom, and all we need to prove is that such an atom exists. Let x\(\displaystyle \in\)S be an arbitrary element. Consider a set in S_{v} that contains x and has the minimum number of elements, and call it A. If A is not an atom then it is not minimal, that is, it has a subset X\(\displaystyle \subset\)A that is not empty but not equal to A either. Then X and \(\displaystyle A\setminus X\) are both in S_{v}, they are proper subsets of A, and one of them contains x. This contradicts to A being minimal among the sets in S_{v} containing x. Therefore, A is indeed an atom.
It follows that any set in X\(\displaystyle \in\)S_{v} can be uniquely expressed as the union of atoms in S_{v}. For any element x\(\displaystyle \in\)S, let A_{x} be the atom for which x\(\displaystyle \in\)A_{x}. The unique representation of the set X is then:
\(\displaystyle
X=\bigcup_{x\in X}A_x.
\)
For a proof, observe that all atoms are subsets of X and thus the righthand side is a subset of X, and that the righthand side contains all elements of X as the set A_{x} containing x occurs among the terms for each x\(\displaystyle \in\)X. All there remains to prove is that the above representation is unique. If x\(\displaystyle \in\)X, then a representation of X must contain the atom A_{x} as that is the only atom that contains x. On the other hand, if X and a particular atom are disjoint, it cannot occur in the representation of X.
Let the atoms of S_{v} be A^{1},...,A^{k}. By the above reasoning, for each set X in S_{v} there exists a unique index set I\(\displaystyle \subset\){1,2,...,k}, such that \(\displaystyle X=\cup_{i\in I}A^i\), and vice versa, for any index set I the set \(\displaystyle \cup_{i\in I}A^i\) is in S_{v}. Thus there is a onetoone correspondence between the sets in S_{v} and the subsets of the set {1,2,...,k}. The number of such subsets is 2^{k}, therefore S_{v}=2^{k}. This completes the proof of the lemma.
Now there remains to prove the statement of the problem. Let the values of the function f be v_{1}< v_{2}< ^{...}< v_{n}. Consider the sets \(\displaystyle S_{v_1},S_{v_2},\dots,S_{v_n}\). These sets form a chain getting larger and larger: \(\displaystyle S_{v_1}\subset S_{v_2}\subset\cdots\subset S_{v_n}.\)
These sets are not empty, and no two of them are identical. It follows from the lemma that \(\displaystyle S_{v_1}<S_{v_2}<
\cdots<S_{v_n}\) are different powers of 2, greater than 1, and thus \(\displaystyle S_{v_n}\ge2^n\). On the other hand, \(\displaystyle S_{v_n}\) consists of all the subsets of S, thus \(\displaystyle S_{v_n}=2^{S}\). Hence, n\(\displaystyle \le\)S.
Remark. It is not hard to construct an example where the range of f has exactly S elements. Let S={1,2,...,n}, f(S)=f(\(\displaystyle \emptyset\))=0, and for any subset X different from S and the empty set, let f(X) be the largest number in S, such that exactly one of f(X) and f(X)1 is an element of X. For example, in the case of n=6, let f({1,2,5})=5.
