SCHWEITZER 2009

On every card of a deck of cards a regular 17-gon is displayed with all sides and diagonals, and the vertices are numbered from 1 through 17. On every card all edges (sides and diagonals) are colored with a color 1,2,...,105 such that the following property holds: for every 15 vertices of the 17-gon the 105 edges connecting these vertices are colored with different colors on at least one of the cards. What is the minimum number of cards in the deck?

Let $p_1,\dots,p_k$ be prime numbers, and let $S$ be the set of those integers whose all prime divisors are among $p_1,\dots,p_k$ . For a finite subset $A$ of the integers let us denote by $\mathcal G(A)$ the graph whose vertices are the elements of $A$ , and the edges are those pairs $a,b\in A$ for which $a - b\in S$ . Does there exist for all $m\geq 3$ an $m$ -element subset $A$ of the integers such that (i) $\mathcal G(A)$ is complete? (ii) $\mathcal G(A)$ is connected, but all vertices have degree at most 2?

Prove that there exist positive constants $c$ and $n_0$ with the following property. If $A$ is a finite set of integers, $|A| = n > n_0$ , then $$|A - A| - |A + A| \leq n^2 - c n^{8/5}.$$

Prove that the polynomial $$f(x) = \frac {x^n + x^m - 2}{x^{\gcd(m,n)} - 1}$$ is irreducible over $\mathbb{Q}$ for all integers $n > m > 0$ .

Let $G$ be a finite non-commutative group of order $t = 2^nm$ , where $n, m$ are positive and $m$ is odd. Prove, that if the group contains an element of order $2^n$ , then (i) $G$ is not simple; (ii) $G$ contains a normal subgroup of order $m$ .

A set system $(S,L)$ is called a Steiner triple system, if $L\neq\emptyset$ , any pair $x,y\in S$ , $x\neq y$ of points lie on a unique line $\ell\in L$ , and every line $\ell\in L$ contains exactly three points. Let $(S,L)$ be a Steiner triple system, and let us denote by $xy$ the thrid point on a line determined by the points $x\neq y$ . Let $A$ be a group whose factor by its center $C(A)$ is of prime power order. Let $f,h: S\to A$ be maps, such that $C(A)$ contains the range of $f$ , and the range of $h$ generates $A$ . Show, that if $$f(x) = h(x)h(y)h(x)h(xy)$$ holds for all pairs $x\neq y$ of points, then $A$ is commutative, and there exists an element $k\in A$ , such that $f(x) = kh(x)$ for all $x\in S$ .

Let $H$ be an arbitrary subgroup of the diffeomorphism group $\mathsf{Diff}^\infty(M)$ of a differentiable manifold $M$ . We say that an $\mathcal C^\infty$ -vector field $X$ is weakly tangent to the group $H$ , if there exists a positive integer $k$ and a $\mathcal C^\infty$ -differentiable map $\varphi \mathrel{: } \mathord{]} - \varepsilon,\varepsilon\mathord{[}^k\times M\to M$ such that (i) for fixed $t_1,\dots,t_k$ the map $$\varphi_{t_1,\dots,t_k} : x\in M\mapsto \varphi(t_1,\dots,t_k,x)$$ is a diffeomorphism of $M$ , and $\varphi_{t_1,\dots,t_k}\in H$ ; (ii) $\varphi_{t_1,\dots,t_k}\in H = \mathsf{Id}$ whenever $t_j = 0$ for some $1\leq j\leq k$ ; (iii) for any $\mathcal C^\infty$ -function $f: M\to \mathbb R$ $$X f = \left.\frac {\partial^k(f\circ\varphi_{t_1,\dots,t_k})}{\partial t_1\dots\partial t_k}\right|_{(t_1,\dots,t_k) = (0,\dots,0)}.$$ Prove, that the commutators of $\mathcal C^\infty$ -vector fields that are weakly tangent to $H\subset \textsf{Diff}^\infty(M)$ are also weakly tangent to $H$ .

Let $\{A_n\}_{n \in \mathbb{N}}$ be a sequence of measurable subsets of the real line which covers almost every point infinitely often. Prove, that there exists a set $B \subset \mathbb{N}$ of zero density, such that $\{A_n\}_{n \in B}$ also covers almost every point infinitely often. (The set $B \subset \mathbb{N}$ is of zero density if $\lim_{n \to \infty} \frac {\#\{B \cap \{0, \dots, n - 1\}\}}{n} = 0$ .)

Let $P\subseteq \mathbb{R}^m$ be a non-empty compact convex set and $f: P\rightarrow \mathbb{R}_{ + }$ be a concave function. Prove, that for every $\xi\in \mathbb{R}^m$ $$\int_{P}\langle \xi,x \rangle f(x)dx\leq \left[\frac {m + 1}{m + 2}\sup_{x\in P}{\langle\xi,x\rangle} + \frac {1}{m + 2}\inf_{x\in P}{\langle\xi,x\rangle}\right] \cdot\int_{P}f(x)dx.$$

Let $U\subset\mathbb R^n$ be an open set, and let $L: U\times\mathbb R^n\to\mathbb R$ be a continuous, in its second variable first order positive homogeneous, positive over $U\times (\mathbb R^n\setminus\{0\})$ and of $C^2$ -class Langrange function, such that for all $p\in U$ the Gauss-curvature of the hyper surface $$\{ v\in\mathbb R^n \mid L(p,v) = 1 \}$$ is nowhere zero. Determine the extremals of $L$ if it satisfies the following system $$\sum_{k = 1}^n y^k\partial_k\partial_{n + i}L = \sum_{k = 1}^n y^k\partial_i\partial_{n + k} L (i\in\{1,\dots,n\})$$ of partial differetial equations, where $y^k(u,v) : = v^k$ for $(u,v)\in U\times\mathbb R^k$ , $v = (v^1,\dots,v^k)$ .

Denote by $H_n$ the linear space of $n\times n$ self-adjoint complex matrices, and by $P_n$ the cone of positive-semidefinite matrices in this space. Let us consider the usual inner product on $H_n$ $$\langle A,B\rangle = {\rm tr} AB (A,B\in H_n)$$ and its derived metric. Show that every $\phi: P_n\to P_n$ isometry (that is a not necessarily surjective, distance preserving map with respect to the above metric) can be expressed as $$\phi(A) = UAU^* + X (A\in H_n)$$ or $$\phi(A) = UA^TU^* + X (A\in H_n)$$ where $U$ is an $n\times n$ unitary matrix, $X$ is a positive-semidefinite matrix, and $^T$ and $^*$ denote taking the transpose and the adjoint, respectively.

Let $Z_1, Z_2\dots, Z_n$ be $d$ -dimensional independent random (column) vectors with standard normal distribution, $n - 1 > d$ . Furthermore let $$\overline Z = \frac {1}{n}\sum_{i = 1}^n Z_i, S_n = \frac {1}{n - 1}\sum_{i = 1}^n(Z_i - \overline Z)(Z_i - \overline Z)^\top$$ be the sample mean and corrected empirical covariance matrix. Consider the standardized samples $Y_i = S_n^{ - 1/2}(Z_i - \overline Z)$ , $i = 1,2,\dots,n$ . Show that $$\frac {E|Y_1 - Y_2|}{E|Z_1 - Z_2|} > 1,$$ and that the ratio does not depend on $d$ , only on $n$ .