Magyar Information Contest Journal Articles
 Current issue Previous issues Order Form Special issues Archives

# English Issue, December 2002

Previous pageContentsNext pageORDER 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=X1$\displaystyle \cup$X2, but then, as

max (f(X1),f(X2))$\displaystyle \ge$f(X1$\displaystyle \cup$X2)=f(X)=m,

one of f(X1) and f(X2) 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 Sv be the set of those subsets of the set S for which the value assigned by the function f is not greater than v:

Sv = {X$\displaystyle \subset$Sf(X)$\displaystyle \le$v}.

Then |Sv| is either 0, or a power of 2 that is different from 1.

Proof for the lemma. First observe that Sv is closed for complement, union, intersection and difference, that is, for all sets X,Y in Sv, $\displaystyle S\setminus X$, X$\displaystyle \cap$Y, X$\displaystyle \cup$Y and $\displaystyle X\setminus Y$ are also in Sv. 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 Sv is not empty, then S$\displaystyle \in$Sv.

It follows from the closeness under complement that if Sv has at least one element then the complement of that element also belongs to S. Thus the elements of Sv can be matched, and thus Sv cannot be a one-element set.

Let the atoms of Sv be its nonempty subsets with the minimum number of elements. Thus a nonempty set A$\displaystyle \in$Sv is an atom if and only if for all X$\displaystyle \subset$A, X$\displaystyle \in$Sv 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$Sv is an atom and X$\displaystyle \in$Sv 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 Sv. 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 Sv 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 Sv, they are proper subsets of A, and one of them contains x. This contradicts to A being minimal among the sets in Sv containing x. Therefore, A is indeed an atom.

It follows that any set in X$\displaystyle \in$Sv can be uniquely expressed as the union of atoms in Sv. For any element x$\displaystyle \in$S, let Ax be the atom for which x$\displaystyle \in$Ax. 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 Ax 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 Ax 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 Sv be A1,...,Ak. By the above reasoning, for each set X in Sv 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 Sv. Thus there is a one-to-one correspondence between the sets in Sv and the subsets of the set {1,2,...,k}. The number of such subsets is 2k, therefore |Sv|=2k. 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 v1< v2< ...< vn. 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.

 Támogatóink: Morgan Stanley