## Solutions for advanced problems "A" in February, 2002 |

In this page only the sketch of the solutions are published; in some cases only the final results. To achieve the maximum score in the competition more detailed solutions needed.

**A. 284.** Let *f* be a function defined on
the subsets of a finite set *S*. Prove that if
*f*(*S*\*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.** In the case of *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 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 *R*=*S*\*X*, and define the function *g*:*P*(*R*)\(\displaystyle to\)*R* as follows: for all *A\(\displaystyle subset\)R*, let

*g*(*A*)=min(*f*(*A*),*f*(*A\(\displaystyle cup\)X*))=min(*f*(*A*),*f*(*R*\*A*)).

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, *g*(*R*\*A*)=*g*(*A*) és *g*(*A\(\displaystyle cup\)**B*)\(\displaystyle le\)max(*g*(*A*),*g*(*B*)) for all *A*,*B\(\displaystyle subset\)R*. Then, according to the assumption, *g* may have at most (|*S*|-1) different values. For any set *A\(\displaystyle subset\)T*, one of *f*(*A*) and *f*(*A*+*X*) is *m*, and the other is *g*(*A*). Hence the range of *f* can only be wider than the range of *g* by the single element *m*.

The property *g*(*R*\*A*)=*g*(*A*) can be derived fom 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 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*-nél. 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 requirements.

**Solution 2. (by E. Csóka).** The solution is based on the following lemma:

*Lemma.* For a 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}, *S*\*X*, *X\(\displaystyle cap\)Y*, *X\(\displaystyle cup\)Y* and *X*\*Y* are also in *S*_{v}. The first two are true because *f*(*S*\*X*)=*f*(*X*)\(\displaystyle 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 expresssed in terms of complement and union.

It follows from the closure for union and complement that if *S*_{v} is not empty, then *S\(\displaystyle in\)S*_{v}.

It follows from the closure for complement that if *S*_{v} has at least one element then the complement of that element is also an element. Thus the elements of *S*_{v} can be paired up, and therefore *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 *X*=\(\displaystyle emptyset\) or *X*=*A*.

Two important things follow from the definition of atoms. One of them is that if *A\(\displaystyle in\)S*_{v} is an atom and *X\(\displaystyle in\)S*_{v} is an arbitrary set, then *A* is a subset of either *X* or (*S*\*X*). If it were not, *A*\*X* would not be the empty set but 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 *A*\*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 an atom.

It follows that any set in *X\(\displaystyle in\)S*_{v} can be expressed in one unique way 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 as follows:

\(\displaystyle X=\bigcup_{x\in X}A_x.\)

To prove, 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 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 *X*=\(\displaystyle cup\)_{i\(\displaystyle in\)I}*A*^{i}, and vice versa, for any index set *I* the set \(\displaystyle cup\)_{i\(\displaystyle 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 *S*_{v1},*S*_{v2},...,*S*_{vn}. These sets form a chain getting wider and wider:

*S*_{v1}\(\displaystyle subset\)*S*_{v2}\(\displaystyle subset\)...\(\displaystyle subset\)*S*_{vn}.

The sets are not empty, and no two of them are identical. It follows from the lemma that |*S*_{v1}|<|*S*_{v2}|<...<|*S*_{vn}| are different powers of 2, greater than 1, and thus |*S*_{vn}|\(\displaystyle ge\)2^{n}. On the other hand, *S*_{vn} consists of all the subsets of *S*, thus |*S*_{vn}|=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.

**A. 285.** Prove that if
*a*^{2}+*ac*-*c*^{2}=*b*^{2}+*bd*-*d*^{2},
for the integers *a*>*b*>*c*>*d*>0,
then *ab*+*cd* is a composite number.

**Solution.** Assume that *p*=*ab*+*cd* is a prime. Then *ab\(\displaystyle equiv\)*-*cd* (mod *p*), and

0=*b*^{2}(*b*^{2}+*bd*-*d*^{2})-*b*^{2}(*a*^{2}+*ac*-*c*^{2})=*b*^{2}(*b*^{2}+*bd*-*d*^{2})-*a*^{2}*b*^{2}-*ab*^{2}*c*+*b*^{2}*c*^{2}\(\displaystyle equiv\)

\(\displaystyle equiv\)*b*^{2}(*b*^{2}+*bd*-*d*^{2})-*c*^{2}*d*^{2}+*bc*^{2}*d*+*b*^{2}*c*^{2}=(*b*^{2}+*c*^{2})(*b*^{2}+*bd*-*d*^{2}) (mod *p*).

Therefore, one of the numbers *b*^{2}+*c*^{2} and *b*^{2}+*bd*-*d*^{2} is divisible by *p*.

If *p* divides *b*^{2}+*c*^{2}, then it follows from 0<*b*^{2}+*c*^{2}<2(*ab*+*cd*)=2*p* that *b*^{2}+*c*^{2}=*p*. In that case, *ab*+*cd*=*b*^{2}+*c*^{2}. Investigation modulo *b* shows that *c*(*c*-*d*) is divisible by *b*. *b* and *c* are relative primes (or *ab*+*cd* could not be a prime), thus *c*-*d* is divisible by *b*. This is contradiction, as 0<*c*-*d*<*b*.

If *p* divides *b*^{2}+*bd*-*d*^{2}, then it follows from 0<*b*^{2}+*bd*-*d*^{2}<2(*ab*+*cd*)=*p* that *b*^{2}+*bd*-*d*^{2}=*p*. Then *ab*+*cd*=*b*^{2}+*bd*-*d*^{2}=*a*^{2}+*ac*-*c*^{2}. Investigation modulo *a* and modulo *b* shows that (*c*+*d*)*c* is divisible by *a*, and (*c*+*d*)*d* is divisible by *b*. As *ab* and *cd* are relative primes, it follows that *c*+*d* is divisible by both *a* and *b*. But that is impossible,as 0<*c*+*d*<2*a* and 0<*c*+*d*<2*b*.

**A. 286.** Find all continuous functions such
that

\(\displaystyle f\left({x+y\over1+xy}\right)={f(x)f(y)\over|1+xy|},\)

where 1+*xy\(\displaystyle ne\)*0. (based on the idea of *Z.* *Győrfi* and
*G.* *Ligeti*)

**Solution.** Let

\(\displaystyle g(u)=\left|{1+u\over2}\right|\cdot f\left({u-1\over u+1}\right),\)

or, what is equivalent,

\(\displaystyle f(x)=|1-x|\cdot g\left({1+x\over1-x}\right).\)

With a little calculation, it is easy to check that this substitution means *g*(*uv*)=*g*(*u*)^{.}*g*(*v*). This may happen in three different ways:

a) *g*(*u*)\(\displaystyle equiv\)0; then *f*(*x*)\(\displaystyle equiv\)0.

b) *g*(*u*)=|*u*|^{\(\displaystyle alpha\)}, where \(\displaystyle alpha\) is a real number. Then *f*(*x*)=|1+*x*|^{\(\displaystyle alpha\)}^{.}|1-*x*|^{1-\(\displaystyle alpha\)}. It follows from continuity that 0\(\displaystyle le\)1.

c) *g*(*u*)=sgn*u*^{.}|*u*|^{}. Then *f*(*x*)=sgn(1-|*x*|)^{.}|1+*x*|^{}^{.}|1-*x*|^{1-}. In this case, 0<<1.

**Remark.** The fraction is reminiscent of the addition theorem for hyperbolic tangent:

In the solution above, *u* is substituted for *e*^{2a} in the fraction .