MathDB

2016 IMC

Part of IMC

Subcontests

(5)
5
2

IMC 2016, Problem 5

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

IMC 2016, Problem 10

Let AA be a n×nn\times n complex matrix whose eigenvalues have absolute value at most 11. Prove that ∥An∥≤nln⁡2∥A∥n−1. \|A^n\|\le \dfrac{n}{\ln 2} \|A\|^{n-1}. (Here ∥B∥=sup⁡∥x∥≤1∥Bx∥\|B\|=\sup\limits_{\|x\|\leq 1} \|Bx\| for every n×nn\times n matrix BB and ∥x∥=∑i=1n∣xi∣2\|x\|=\sqrt{\sum\limits_{i=1}^n |x_i|^2} for every complex vector x∈Cnx\in\mathbb{C}^n.)
(Proposed by Ian Morris and Fedor Petrov, St. Petersburg State University)
4
2

IMC 2016, Problem 4

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

IMC 2016, Problem 9

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

IMC 2016, Problem 3

Let nn be a positive integer. Also let a1,a2,…,ana_1, a_2, \dots, a_n and b1,b2,…,bnb_1,b_2,\dots, b_n be real numbers such that ai+bi>0a_i+b_i>0 for i=1,2,…,ni=1,2,\dots, n. Prove that ∑i=1naibi−bi2ai+bi≤∑i=1nai⋅∑i=1nbi−(∑i=1nbi)2∑i=1n(ai+bi)\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)

IMC 2016, Problem 8

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

IMC 2016, Problem 2

Let kk and nn be positive integers. A sequence (A1,…,Ak)\left( A_1, \dots , A_k \right) of n×nn\times n real matrices is preferred by Ivan the Confessor if Ai2≠0A_i^2\neq 0 for 1≤i≤k1\le i\le k, but AiAj=0A_iA_j=0 for 1≤i1\le i, j≤kj\le k with i≠ji\neq j. Show that k≤nk\le n in all preferred sequences, and give an example of a preferred sequence with k=nk=n for each nn.
(Proposed by Fedor Petrov, St. Petersburg State University)

IMC 2016, Problem 7

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

IMC 2016, Problem 1

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

IMC 2016, Problem 6

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