## Angol nyelvű szám, 2002. december | ||||

Előző oldal | Tartalomjegyzék | Következő oldal | MEGRENDELŐLAP |

## 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*_{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 (|*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*^{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 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*_{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.