Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# 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=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 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 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, S\X, X$\displaystyle cap$Y, X$\displaystyle cup$Y and X\Y are also in Sv. 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 Sv is not empty, then S$\displaystyle in$Sv.

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

Two important things follow from the definition of atoms. One of them is that if A$\displaystyle in$Sv is an atom and X$\displaystyle in$Sv 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 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 A\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 an atom.

It follows that any set in X$\displaystyle in$Sv can be expressed in one unique way 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 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 Ax 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 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 X=$\displaystyle cup$i$\displaystyle in$IAi, and vice versa, for any index set I the set $\displaystyle cup$i$\displaystyle in$IAi 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 Sv1,Sv2,...,Svn. These sets form a chain getting wider and wider:

Sv1$\displaystyle subset$Sv2$\displaystyle subset$...$\displaystyle subset$Svn.

The sets are not empty, and no two of them are identical. It follows from the lemma that |Sv1|<|Sv2|<...<|Svn| are different powers of 2, greater than 1, and thus |Svn|$\displaystyle ge$2n. On the other hand, Svn consists of all the subsets of S, thus |Svn|=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 a2+ac-c2=b2+bd-d2, 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=b2(b2+bd-d2)-b2(a2+ac-c2)=b2(b2+bd-d2)-a2b2-ab2c+b2c2$\displaystyle equiv$

$\displaystyle equiv$b2(b2+bd-d2)-c2d2+bc2d+b2c2=(b2+c2)(b2+bd-d2) (mod p).

Therefore, one of the numbers b2+c2 and b2+bd-d2 is divisible by p.

If p divides b2+c2, then it follows from 0<b2+c2<2(ab+cd)=2p that b2+c2=p. In that case, ab+cd=b2+c2. 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 b2+bd-d2, then it follows from 0<b2+bd-d2<2(ab+cd)=p that b2+bd-d2=p. Then ab+cd=b2+bd-d2=a2+ac-c2. 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<2a and 0<c+d<2b.

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)=sgnu.|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 e2a in the fraction .