Olympiad problems

2016 IMC, 2

Tags: IMC , IMC 2016 , Matrices , linear algebra , college contests

Let $k$ and $n$ be positive integers. A sequence $\left( A_1, \dots , A_k \right)$ of $n\times n$ real matrices is [i]preferred[/i] by Ivan the Confessor if $A_i^2\neq 0$ for $1\le i\le k$, but $A_iA_j=0$ for $1\le i$, $j\le k$ with $i\neq j$. Show that $k\le n$ in all preferred sequences, and give an example of a preferred sequence with $k=n$ for each $n$. (Proposed by Fedor Petrov, St. Petersburg State University)

2016 IMC, 1

Tags: IMC , IMC 2016 , college contests , Sequences , Summation

Let $(x_1,x_2,\ldots)$ be a sequence of positive real numbers satisfying ${\displaystyle \sum_{n=1}^{\infty}\frac{x_n}{2n-1}=1}$. Prove that $$ \displaystyle \sum_{k=1}^{\infty} \sum_{n=1}^{k} \frac{x_n}{k^2} \le2. $$ (Proposed by Gerhard J. Woeginger, The Netherlands)

2016 IMC, 2

Tags: IMC , IMC 2016 , college contests , function , minimum value

Today, Ivan the Confessor prefers continuous functions $f:[0,1]\to\mathbb{R}$ satisfying $f(x)+f(y)\geq |x-y|$ for all pairs $x,y\in [0,1]$. Find the minimum of $\int_0^1 f$ over all preferred functions. (Proposed by Fedor Petrov, St. Petersburg State University)

2016 IMC, 4

Tags: IMC , IMC 2016 , college contests , functions

Let $k$ be a positive integer. For each nonnegative integer $n$, let $f(n)$ be the number of solutions $(x_1,\ldots,x_k)\in\mathbb{Z}^k$ of the inequality $|x_1|+...+|x_k|\leq n$. Prove that for every $n\ge1$, we have $f(n-1)f(n+1)\leq f(n)^2$. (Proposed by Esteban Arreaga, Renan Finder and José Madrid, IMPA, Rio de Janeiro)

2016 IMC, 5

Tags: IMC , IMC 2016 , college contests , matrix

Let $A$ be a $n\times n$ complex matrix whose eigenvalues have absolute value at most $1$. Prove that $$ \|A^n\|\le \dfrac{n}{\ln 2} \|A\|^{n-1}. $$ (Here $\|B\|=\sup\limits_{\|x\|\leq 1} \|Bx\|$ for every $n\times n$ matrix $B$ and $\|x\|=\sqrt{\sum\limits_{i=1}^n |x_i|^2}$ for every complex vector $x\in\mathbb{C}^n$.) (Proposed by Ian Morris and Fedor Petrov, St. Petersburg State University)

2016 IMC, 5

Tags: IMC , IMC 2016 , prime numbers , permutations , college contests

Let $S_n$ denote the set of permutations of the sequence $(1,2,\dots, n)$. For every permutation $\pi=(\pi_1, \dots, \pi_n)\in S_n$, let $\mathrm{inv}(\pi)$ be the number of pairs $1\le i < j \le n$ with $\pi_i>\pi_j$; i. e. the number of inversions in $\pi$. Denote by $f(n)$ the number of permutations $\pi\in S_n$ for which $\mathrm{inv}(\pi)$ is divisible by $n+1$. Prove that there exist infinitely many primes $p$ such that $f(p-1)>\frac{(p-1)!}{p}$, and infinitely many primes $p$ such that $f(p-1)<\frac{(p-1)!}{p}$. (Proposed by Fedor Petrov, St. Petersburg State University)

2016 IMC, 3

Tags: IMC , IMC 2016 , college contests , abstract algebra , function

Let $n$ be a positive integer, and denote by $\mathbb{Z}_n$ the ring of integers modulo $n$. Suppose that there exists a function $f:\mathbb{Z}_n\to\mathbb{Z}_n$ satisfying the following three properties: (i) $f(x)\neq x$, (ii) $f(f(x))=x$, (iii) $f(f(f(x+1)+1)+1)=x$ for all $x\in\mathbb{Z}_n$. Prove that $n\equiv 2 \pmod4$. (Proposed by Ander Lamaison Vidarte, Berlin Mathematical School, Germany)

2016 IMC, 3

Tags: IMC , IMC 2016 , Summation , college contests

Let $n$ be a positive integer. Also let $a_1, a_2, \dots, a_n$ and $b_1,b_2,\dots, b_n$ be real numbers such that $a_i+b_i>0$ for $i=1,2,\dots, n$. Prove that $$\sum_{i=1}^n \frac{a_ib_i-b_i^2}{a_i+b_i}\le\frac{\displaystyle \sum_{i=1}^n a_i\cdot \sum_{i=1}^n b_i - \left( \sum_{i=1}^n b_i\right) ^2}{\displaystyle\sum_{i=1}^n (a_i+b_i)}$$. (Proposed by Daniel Strzelecki, Nicolaus Copernicus University in Toruń, Poland)

2016 IMC, 4

Tags: IMC , IMC 2016 , Sets , set theory , college contests

Let $n\ge k$ be positive integers, and let $\mathcal{F}$ be a family of finite sets with the following properties: (i) $\mathcal{F}$ contains at least $\binom{n}{k}+1$ distinct sets containing exactly $k$ elements; (ii) for any two sets $A, B\in \mathcal{F}$, their union $A\cup B$ also belongs to $\mathcal{F}$. Prove that $\mathcal{F}$ contains at least three sets with at least $n$ elements. (Proposed by Fedor Petrov, St. Petersburg State University)

2016 IMC, 1

Tags: IMC , IMC 2016 , functions , function , real analysis , college contests

Let $f : \left[ a, b\right]\rightarrow\mathbb{R}$ be continuous on $\left[ a, b\right]$ and differentiable on $\left( a, b\right)$. Suppose that $f$ has infinitely many zeros, but there is no $x\in \left( a, b\right)$ with $f(x)=f'(x)=0$. (a) Prove that $f(a)f(b)=0$. (b) Give an example of such a function on $\left[ 0, 1\right]$. (Proposed by Alexandr Bolbot, Novosibirsk State University)