IMC 2016

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)

Let $k$ and $n$ be positive integers. A sequence $\left( A_1, \dots , A_k \right)$ of $n\times n$ real matrices is preferred 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)

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{ \sum_{i=1}^n a_i\cdot \sum_{i=1}^n b_i - \left( \sum_{i=1}^n b_i\right) ^2}{ \sum_{i=1}^n (a_i+b_i)}$$ .

(Proposed by Daniel Strzelecki, Nicolaus Copernicus University in Toruń, Poland)

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)

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)

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

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)

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)

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)

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)