English Issue, December 2002
	Previous page	Contents	Next page	ORDER FORM

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 one-element 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₁\(\displaystyle \cup\)X₂, but then, as

max (f(X₁),f(X₂))\(\displaystyle \ge\)f(X₁\(\displaystyle \cup\)X₂)=f(X)=m,

one of f(X₁) and f(X₂) 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 (|S|-1) 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 one-element 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 non-disjoint 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 right-hand side is a subset of X, and that the right-hand 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¹,...,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 one-to-one 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₁< v₂< ^...< 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.