Miklós Schweitzer Memorial Competition in Mathematics 29 October — 8 November 2004

1. The Lindelöf number L(X) of a topological space X is the least infinite cardinal λ with the property that every open covering of X has a subcovering of cardinality at most λ. Prove that if every non-countably infinite subset of a first countable space X has a point of condensation, then L(X) = sup L(A), where A runs over the separable closed subspaces of X. (A point of condensation of a subset H ⊆ X is a point x ∈ X such that any neighbourhood of x intersects H in a non-countably infinite set.)

2. Write t(G) for the number of complete quadrilaterals in the graph G and e_{G}(S) for the number of edges spanned by a subset S of vertices of G. Let G_{1}, G_{2} be two (simple) graphs on a common underlying set V of vertices, |V | = n, and assume that |e_{G_{1}}(S) − e_{G_{2}}(S)| ≤ n^{2}/1000 holds for any subset S ⊆ V. Prove that |t(G_{1}) − t(G_{2})| ≤ n^{4}/1000.

3. Prove that there is a constant c > 0 such that for any n ≥ 3 there exists a planar graph G with n vertices such that every straight-edged plane embedding of G has a pair of edges with ratio of lengths at least cn.

4. Determine all totally multiplicative and non-negative functions f : ℤ → ℤ with the property that if a, b ∈ ℤ and b ≠ 0, then there exist integers q and r such that a = qb + r and f(r) < f(b).

5. Let G be a non-solvable finite group and let ε > 0. Show that there exist a positive integer k and a word w ∈ F_{k} such that w assumes the value 1 with probability less than ε when its k arguments are considered to be independent and uniformly distributed random variables with values in G. (We write F_{k} for the free group generated by k elements.)

6. Is it true that if the perfect set F ⊂ [0, 1] is of zero Lebesgue measure then those functions in C^{1}[0, 1] which are one-to-one on F form a dense subset of C^{1}[0, 1]? (We use the metric

d(f, g) = sup_{x∈[0,1]} |f(x) − g(x)| + sup_{x∈[0,1]} |f′(x) − g′(x)|

to define the topology in the space C^{1}[0, 1] of continuously differentiable real functions on [0, 1].)

7. Suppose that the closed subset K of the sphere

S^{2} = {(x, y, z) ∈ ℝ^{3} : x^{2} + y^{2} + z^{2} = 1}

is symmetric with respect to the origin and separates any two antipodal points in S^{2}\K. Prove that for any positive ε there exists a homogeneous polynomial P of odd degree such that the Hausdorff distance between

Z(P) = {(x, y, z) ∈ S^{2} : P (x, y, z) = 0}

and K is less than ε.

8. Prove that for any 0 < δ < 2π there exists a number m ≥ 1 such that for any positive integer n and unimodular complex numbers z_{1}, …, z_{n} with z_{1}^{ν} + ⋯ + z_{n}^{ν} = 0 for all integer exponents 1 ≤ ν ≤ m, any arc of length δ of the unit circle contains at least one of the numbers z_{1}, …, z_{n}.

9. Let F be a smooth (i.e., C^{∞}) closed surface. Call a continuous map f : F → ℝ^{2} an almost-immersion if there exists a smooth closed embedded curve γ (possibly disconnected) in F such that f is smooth and of maximal rank (i.e., rank 2) on F \γ, and each point p ∈ γ admits local coordinate charts (x, y) and (u, v) about p and f(p), respectively, such that the coordinates of p and f(p) are zero and the map f is given by (x, y) ↦ (u, v), u = |x|, v = y. Determine the genera of those smooth, closed, connected, orientable surfaces F that admit an almost-immersion in the plane with the curve γ having a given positive number n of connected components.

10. Let N_{p} stand for a p dimensional random variable of standard normal distibution. For a ∈ ℝ^{p}, let H_{p}(a) stand for the expectation E|N_{p} + a|. For p > 1, prove that

H_{p}(a) = (p − 1) ∫_{0}^{∞} H_{1} (\frac{|a|}{\sqrt{1 + r^{2}}} ) \frac{r^{p−2}}{(1 + r^{2})^{\frac{p}{2}}} dr.

The deadline for submitting solutions is 12:00 (CET) 8 November, 2004. If the participant relies on knowledge not included in the standard curriculum, then (s)he should cite the exact source. For further information see the

homepage http://www.cs.elte.hu/~schw04.