SCHWEITZER 2005

Let [n] be the set {1, 2,. . . , n}.

For any $a, b \in N$ , denote $G (a, b)$ by a graph (not directed) defined by the following rule: the vertices have the form (i, f), where $i \in [a]$ , and $f: [a] \to [b]$ . A vertex (i, f) and a vertex (j, g) are connected if $i \neq j$ , and $f (k) \neq g (k)$ holds exactly for k strictly between i and j. Prove that for any $c \in N$ there is $a, b \in N$ such that the vertices of G (a, b) cannot be well-colored with $c$ colors.

Let $(a_{n})_{n \ge 1}$ be a sequence of integers satisfying the inequality $$0\le a_{n-1}+\frac{1-\sqrt{5}}{2}a_{n}+a_{n+1} <1$$ for all $n \ge 2$ . Prove that the sequence $(a_{n})$ is periodic.

Any Hints or Sols for this hard problem?? :help:

Let $\alpha\leq 22$ be non-negative integer. For which $\alpha$ does the equation $$8x^{23}-5^{\alpha}y^{23}=1$$ have the most integer solutions (x,y)? What can we say about $\alpha\geq 23$ ?

Let F be a countable free group and let $F = H_1> H_2> H_3> \cdots$ be a descending chain of finite index subgroups of group F. Suppose that $\cap H_i$ does not contain any nontrivial normal subgroups of F. Prove that there exist $g_i\in F$ for which the conjugated subgroups $H_i^{g_i}$ also form a chain, and $\cap H_i^{g_i}=\{1\}$ .

Let $GL(n, K)$ be a linear group over the field K with a topology induced by a non-Archimedean absolute value of the field K. Prove that if the matrix $M \in GL (n, K)$ is contained by some compact subgroup of $GL(n, K)$ , then all eigenvalues of M have absolute value 1.

$SU_2(\mathbb{C})=\left\{\begin{pmatrix} z & w -\bar{w} & \bar{z} \end{pmatrix} : z,w\in\mathbb{C} , z\bar{z}+w\bar{w}=1\right\}$ A and B are 2 elements of the above matrix group and have eigenvalues $e^{i\theta_1}$ , $e^{-i\theta_1}$ and $e^{i\theta_2}$ , $e^{-i\theta_2}$ respectively, where $0\leq\theta_i\leq\pi$ . Prove that if AB has eigenvalue $e^{i\theta_3}$ , then $\theta_3$ satisfies the inequality $|\theta_1-\theta_2|\leq\theta_3\leq \min\{\theta_1+\theta_2 , 2\pi-(\theta_1+\theta_2)\}$

Let $t\in R$ . Prove that $\exists A:R \times R \to R$ such that A is a symmetric, biadditive, nonzero function and $A(tx,x)=0 \,\forall x\in R$ iff t is transcendental or (t is algebraic and t,-t are conjugates over $\mathbb{Q}$ ).

Determine all continuous, strictly monotone functions $\phi : \mathbb{R}^+\to\mathbb{R}$ such that $$F(x,y)=\phi^{-1} \left(\frac{x\phi(x)+y\phi(y)}{x+y}\right) + \phi^{-1} \left(\frac{y\phi(x)+x\phi(y)}{x+y}\right)$$ is homogeneous of degree 1, ie $F(tx,ty)=tF(x,y) , \forall x,y,t\in\mathbb{R}^+$ NoteF(x,y)=F(y,x) and F(x,x)=2x

prove that if $r_n$ is a rational function whose numerator and denominator have at most degrees $n$ , then $$||r_n||_{1/2}+\left\|\frac{1}{r_n}\right\|_2\geq\frac{1}{2^{n-1}}$$ where $||\cdot||_a$ denotes the supremum over a circle of radius $a$ around the origin.

Given 5 nonzero vectors in three-dimensional Euclidean space, prove that the sum of their pairwise angles is at most $6\pi$ .

Let $E: R^n \backslash \{0\} \to R^+$ be a infinitely differentiable, quadratic positive homogeneous (that is, for any λ>0 and $p \in R^n \backslash \{0\}$ , $E (\lambda p) = \lambda^2 E (p)$ ). Prove that if the second derivative of $E''(p): R^n \times R^n \to R$ is a non-degenerate bilinear form at any point $p \in R^n \backslash \{0\}$ , then $E''(p)$ ( $p \in R^n \backslash \{0\}$ ) is positive definite.

Let $x_1,x_2,\cdots,x_n$ be iid rv. $S_n=\sum x_k$ (a) let $P(|x_1|\leq 1)=1$ , $E[x_1]=0$ , $E[x_1^2]=\sigma^2>0$ Prove that $\exists C>0$ , $\forall u\geq 2n\sigma^2$ $P(S_n\geq u)\leq e^{-C u \log(u/n\sigma^2)}$ (b) let $P(x_1=1)=P(x_1=-1)=\sigma^2/2$ , $P(x_1=0)=1-\sigma^2$ Prove that $\exists B_1<1,B_2>1,B_3>0$ , $\forall u\geq1, B_1 n\geq u\geq B_2 n\sigma^2$ $P(S_n\geq u)>e^{-B_3 u \log(u/n\sigma^2)}$