Problems of the Miklós Schweitzer Memorial Competition November 8–18, 2002

1. For an arbitrary ordinal number α let H(α) denote the set of functions f : α → {−1, 0, 1} that map all but finitely many elements of α to 0. Order H(α) according to the last difference, that is, for f, g ∈ H(α) let f ≺ g if f(β) < g(β) holds for the maximum ordinal number β < α with f(β) ≠ g(β). Prove that the ordered set (H(α), ≺) is scattered (i.e. it does not contain a subset isomorphic to the set of rational numbers with the usual order), and that any scattered order type can be embedded into some (H(α), ≺).

2. Let G be a simple k-edge-connected graph on n vertices and let u and v be different vertices of G. Prove that there exist k edge-disjoint paths from u to

v each having at most \frac{20n}{k} edges.

3. Put A = {yes, no}. A function f : A^{n} → A is called a decision function if

(a) the value of the function changes if we change all of its arguments; and

(b) the value does not change if we replace any of the arguments by the function value.

A function d : A^{n} → A is called a dictatoric function, if there is an index i such that the value of the function equals its ith argument.

The democratic function is the function m : A^{3} → A that outputs the majority of its arguments.

Prove that any decision function is a composition of dictatoric and democratic functions.

4. For a given natural number n, consider those sets A ⊆ ℤ_{n} for which the equation xy = uv has no other solution in the residual classes x, y, u, v ∈ A than the trivial solutions x = u, y = v and x = v, y = u. Let g(n) be the maximum of the size of such sets A. Prove that

lim sup_{n→∞} \frac{g(n)}{\sqrt{n}} = 1 .

5. Denote by λ(H) the Lebesgue outer measure of H ⊆ [0, 1]. The horizontal and vertical sections of the set A ⊆ [0, 1] × [0, 1] are denoted by A^{y} and A_{x} respectively; that is, A^{y} = {x ∈ [0, 1] : (x, y) ∈ A} and A_{x} = {y ∈ [0, 1] : (x, y) ∈ A} for all x, y ∈ [0, 1] .

(a) Is there a decomposition A ∪ B of the unit square [0, 1] × [0, 1] such that A^{y} is the union of finitely many segments of total length less than 1/2 and λ(B_{x}) ≤ 1/2 for all x, y ∈ [0, 1]?

(b) Is there a decomposition A ∪ B of the unit square [0, 1] × [0, 1] such that A^{y} is the union of finitely many segments of total length not greater than 1/2 and λ(B_{x}) < 1/2 for all x, y ∈ [0, 1]?

6. Let K ⊆ ℝ be compact. Prove that the following two statements are equivalent to each other.

(a) For each point x of K we can assign an uncountable set F_{x} ⊆ ℝ such that

dist(F_{x}, F_{y}) ≥ |x − y|

holds for all x, y ∈ K;

(b) K is of measure zero.

7. Let the complex function F (z) be regular on the punctuated disk {0 < |z| < R}. By a level curve we mean a component of the level set of Re F (z), that is, a maximal connected set on which Re F (z) is constant. Denote by A(r) the union of those level curves that are entirely contained in the punctuated disk {0 < |z| < r}. Prove that if the number of components of A(r) has an upper bound independent of r then F (z) can only have a pole type singularity at 0.

8. Prove that there exists an absolute constant c such that any set H of n points of the plane in general position can be coloured with c · log n colours in such a way that any disk of the plane containing at least one point of H intersects some colour class of H in exactly one point.

9. Let M be a connected, compact C^{∞}-differentiable manifold, and dentote the vector space of smooth real functions on M by C^{∞}(M). Let the subspace V ≤ C^{∞}(M) be invariant under C^{∞}-diffeomorphisms of M, that is, let f ∘ h ∈ V for every f ∈ V and for every C^{∞}-diffeomorphism h : M → M. Prove that if V is different from the subspaces {0} and C^{∞}(M) then V only contains the constant functions.

10. Let X_{1}, X_{2}, … be independent random variables of the same distribution such that their joint distribution is discrete and is concentrated on infinitely many different values. Let a_{n} denote the probability that X_{1}, …, X_{n+1} are all different on the condition that X_{1}, …, X_{n} are all different (n ≥ 1). Show that

(a) a_{n} is strictly decreasing and tends to 0 as n → ∞; and

(b) for any sequence 1 ≤ f(1) < f(2) < … of positive integers the joint distribution of X_{1}, X_{2}, … can be chosen such that

lim sup_{n→∞} \frac{a_{f(n)}}{a_{n}} = 1

holds.

The deadline for submitting solutions to the problems is November the 18th, 2002./ 12h (CET). If the participant uses some knowledge that is not contained in the standard curriculum, then (s)he should cite the exact source. For further

information see the homepage http://www.cs.elte.hu/~schw02 .