SCHWEITZER 2018

Let $S\subset \mathbb{R}$ be a closed set and $f:\mathbb{R}^{2n}\to \mathbb{R}$ be a continuous function. Define a graph $G$ as follows: Let $x$ be a vertex of $G$ iff $x\in \mathbb{R}^{n}$ and $f(x,x)\not\in S$ , then connect the vertices $x$ and $y$ by an edge in $G$ iff $f(x,y)\in S$ or $f(y,x)\in S$ . Show that the chromatic number of $G$ is countable.

A family $\mathcal{F}$ of sets is called really neat if for any $A,B\in \mathcal{F}$ , there is a set $C\in \mathcal{F}$ such that $A\cup B = A\cup C=B\cup C$ . Let $$f(n)=\min \left\{ \max_{A\in \mathcal{F}} |A| \colon \mathcal{F} \text{ is really neat and } |\cup \mathcal{F}| =n\right\} .$$ Prove that the sequence $f(n)/n$ converges and find its limit.

We call an $n\times n$ matrix well groomed if it only contains elements $0$ and $1$ , and it does not contain the submatrix $\begin{pmatrix} 1& 0 0 & 1 \end{pmatrix}.$ Show that there exists a constant $c>0$ such that every well groomed, $n\times n$ matrix contains a submatrix of size at least $cn\times cn$ such that all of the elements of the submatrix are equal. (A well groomed matrix may contain the submatrix $\begin{pmatrix} 0& 1 1 & 0 \end{pmatrix}.$ )

Let $P$ be a finite set of points in the plane. Assume that the distance between any two points is an integer. Prove that $P$ can be colored by three colors such that the distance between any two points of the same color is an even number.

For every positive integer $n$ , define $$f(n)=\sum_{p\mid n}{p^{k_p}},$$ where the sum is taken over all positive prime divisors $p$ of $n$ , and $k_p$ is the unique integer satisfying $$p^{k_p}\leqslant n<p^{k_p+1}.$$ Find $$\limsup_{n\to \infty} \frac{f(n)\log \log n}{n\log n} .$$

Prove that if $a$ is an integer and $d$ is a positive divisor of the number $a^4+a^3+2a^2-4a+3$ , then $d$ is a fourth power modulo $13$ .

Describe all functions $f: \{ 0,1\}^n \to \{ 0,1\}$ which satisfy the equation \begin{align*} & f(f(a_{11},a_{12},\dotsc ,a_{1n}),f(a_{21},a_{22},\dotsc ,a_{2n}),\dotsc ,f(a_{n1},a_{n2},\dotsc ,a_{nn})) & = f(f(a_{11},a_{21},\dotsc ,a_{n1}),f(a_{12},a_{22},\dotsc ,a_{n2}),\dotsc ,f(a_{1n},a_{2n},\dotsc ,a_{nn}))\end{align*} for arbitrary $a_{ij}\in \{ 0,1\}$ where $i,j\in \{1,2,\dotsc ,n\}.$

Does there exist a piecewise linear, continuous, surjective mapping $f: [0,1]\to [0,1]$ such that $f(0)=f(1)=0$ , and for all positive integer $n$ , $$2.0001^{(n-10)} <P_n(f)<2.9999^{(n+10)}$$ holds, where $P_n(f)$ is the number of points $x$ such that $\underbrace{f(\dotsc f}_n(x)\dotsc )=x$ ?

Let $f:\mathbb{C} \to \mathbb{C}$ be an entire function, and suppose that the sequence $f^{(n)}$ of derivatives converges pointwise. Prove that $f^{(n)}(z)\to Ce^z$ pointwise for a suitable complex number $C$ .

In 3-dimensional hyperbolic space, we are given a plane $P$ and four distinct straight lines: the lines $a_1$ and $a_2$ are perpendicular to $P$ ; while the lines $r_1$ and $r_2$ do not intersect $P$ , and their distances from $P$ are equal. Denote by $S_i$ the surface of revolution obtained by rotating $r_i$ around $a_i$ . Show that the common points of $S_1$ and $S_2$ can be covered by two planes.

We call an $m$ -dimensional smooth manifold parallelizable if it admits $m$ smooth tangent vector fields that are linearly independent at all points. Show that if $M$ is a closed orientable $2n$ -dimensional smooth manifold of Euler characteristic $0$ that has an immersion into a parallelizable smooth $(2n+1)$ -dimensional manifold $N$ , then $M$ is itself parallelizable.