## Miklos Schweitzer 2012 Problems

1. Is there any real number ${\alpha}$ for which there exist two functions ${f,g: \Bbb{N} \rightarrow \Bbb{N}}$ such that

$\displaystyle \alpha=\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)},$

but the function which associates to ${n}$ the ${n}$-th decimal digit of ${\alpha}$ is not recursive?

2. Call a subset ${A}$ of the cyclic group ${(\Bbb{Z}_n,+)}$ rich if for all ${x,y \in \Bbb{Z}_n}$ there exists ${r \in \Bbb{Z}_n}$ such that ${x-r,x+r,y-r,y+r}$ are all in ${A}$. For what ${\alpha}$ is there a constant ${C_\alpha>0}$ such that for each odd positive integer ${n}$, every rich subset ${A \subset \Bbb{Z}_n}$ has at least ${C_\alpha n^\alpha}$ elements?

3. Prove that if a ${k}$-chromatic graph’s edges are coloured in two colors in any way, there is a subtree with ${k}$ vertices and edges of the same color.

4. Let ${K}$ be a convex shape in the ${n}$ dimensional space, having unit volume. Let ${S \subset K}$ be a Lebesgue measurable set with measure at least ${1-\varepsilon}$, where ${0<\varepsilon<1/3}$. Prove that dilating ${K}$ from its centroid by the ratio of ${2\varepsilon \ln(1/\varepsilon)}$, the shape obtained contains the centroid of ${S}$.

5. Let ${V_1,V_2,V_3,V_4}$ be four dimensional linear subspaces in ${\Bbb{R}^8}$ such that the intersection of any two contains only the zero vector. Prove that there exists a linear four dimensional subspace ${W}$ in ${\Bbb{R}^8}$ such that all four vector spaces ${W\cap V_i}$ are two dimensional.

6. Let ${A,B,C}$ be matrices with complex elements such that ${[A,B]=C,\ [B,C]=A}$ and ${[C,A]=B}$, where ${[X,Y]}$ denotes the ${XY-YX}$ commutator of the matrices. Prove that ${e^{4 \pi A}}$ is the identity matrix. [Solution]

7. Let ${\Gamma}$ be a simple curve, lying inside a circle of radius ${r}$, rectifiable and of length ${l}$. Prove that if ${l > kr\pi}$, then there exists a circle of radius ${r}$ which intersects ${\Gamma}$ in at least ${k+1}$ distinct points.

8. For any function ${f: \Bbb{R}^2\rightarrow \Bbb{R}}$ consider the function ${\Phi_f:\Bbb{R}^2\rightarrow [-\infty,\infty]}$ for which ${\Phi_f(x,y)=\limsup_{ z \rightarrow y} f(x,z)}$ for any ${(x,y) \in \Bbb{R}^2}$.

a) Is it true that if ${f}$ is Lebesgue measurable then ${\Phi_f}$ is also Lebesgue measurable?

b) Is it true that if ${f}$ is Borel measurable then ${\Phi_f}$ is also Borel measurable?

9. Let ${D}$ be the complex unit disk ${D=\{x \in \Bbb{C}: |z|<1\}}$, and ${0 a real number. Suppose that ${f:D \rightarrow \Bbb{C}\setminus \{0\}}$ is a holomorphic function such that ${f(a)=1}$ and ${f(-a)=-1}$. Prove that

$\displaystyle \sup_{z \in D} |f(z)| \geq \exp\left(\frac{1-a^2}{4a}\pi\right)$

10. Let ${K}$ be a knot in the ${3}$-dimensional space (that is a differentiable injection of a circle into ${\Bbb{R}^3}$), and ${D}$ be the diagram of the knot (that is the projection of it to a plane so that in exception of the transversal double points it is also an injection of a circle). Let us color the complement of ${D}$ in black and color the diagram ${D}$ in a chessboard pattern, black and white so that zones which share an arc in common are coloured differently. Define ${\Gamma_B(D)}$ the black graph of the diagram, a graph which has vertices in the black areas and every two vertices which correspond to black areas which have a common point have an edge connecting them.

a) Determine all knots having a diagram ${D}$ such that ${\gamma_B(D)}$ has at most ${3}$ spanning trees. (Two knots are not considered distinct if they can be moved into each other with a one parameter set of the injection of the circle)

b) Prove that for any knot and any diagram ${D}$, ${\Gamma_B(D)}$ has an odd number of spanning trees.

11. Let ${X_1,X_2,..}$ be independent random variables with the same distribution, and let ${S_n=X_1+X_2+...+X_n,\ n=1,2,...}$. For what real numbers ${c}$ is the following statement true:

$\displaystyle P\left(\left| \frac{S_{2n}}{2n}- c \right| \leq \left| \frac{S_n}{n}-c\right| \right)\geq \frac{1}{2}\ \ ?$

Miklos Schweitzer competition 2012 (many thanks to Eles Andras for the translation of the problems from Hungarian to English)