uniolympiads Ελληνικά

IMC 2016

All the problems of the year on one page, as on the contest paper.

Official files

  1. Problem 1 (Day 1)

    Let f ⁣:[a,b]→Rf\colon [a, b] \to \mathbb{R} be continuous on [a,b][a, b] and differentiable on (a,b)(a, b). Suppose that ff has infinitely many zeros, but there is no x∈(a,b)x \in (a, b) 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][0, 1].

    Hints and solution

  2. Problem 2 (Day 1)

    Let kk and nn be positive integers. A sequence (A1,…,Ak)(A_1, \dots, A_k) of n×nn \times n real matrices is preferred by Ivan the Confessor if Ai2≠0A_i^2 \ne 0 for 1≤i≤k1 \le i \le k, but AiAj=0A_iA_j = 0 for 1≤i,j≤k1 \le i, j \le k with i≠ji \ne 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.

    Hints and solution

  3. Problem 3 (Day 1)

    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{\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)}.

    Hints and solution

  4. Problem 4 (Day 1)

    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.

    Hints and solution

  5. Problem 5 (Day 1)

    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⁡(π)\operatorname{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⁡(π)\operatorname{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}.

    Hints and solution

  6. Problem 6 (Day 2)

    Let (x1,x2,… )(x_1, x_2, \dots) be a sequence of positive real numbers satisfying ∑n=1∞xn2n−1=1\sum_{n=1}^{\infty} \frac{x_n}{2n-1} = 1. Prove that

    ∑k=1∞∑n=1kxnk2≤2.\sum_{k=1}^{\infty} \sum_{n=1}^{k} \frac{x_n}{k^2} \le 2.

    Hints and solution

  7. Problem 7 (Day 2)

    Today, Ivan the Confessor prefers continuous functions f ⁣:[0,1]→Rf\colon [0, 1] \to \mathbb{R} satisfying f(x)+f(y)≥∣x−y∣f(x) + f(y) \ge |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.

    Hints and solution

  8. Problem 8 (Day 2)

    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\colon \mathbb{Z}_n \to \mathbb{Z}_n satisfying the following three properties:

    (i) f(x)≠xf(x) \ne 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 \pmod 4.

    Hints and solution

  9. Problem 9 (Day 2)

    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, \dots, x_k) \in \mathbb{Z}^k of the inequality ∣x1∣+⋯+∣xk∣≤n|x_1| + \dots + |x_k| \le n. Prove that for every n≥1n \ge 1, we have f(n−1)f(n+1)≤f(n)2f(n-1)f(n+1) \le f(n)^2.

    Hints and solution

  10. Problem 10 (Day 2)

    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 \frac{n}{\ln 2} \|A\|^{n-1}.

    (Here ∥B∥=sup⁡∥x∥≤1∥Bx∥\|B\| = \sup_{\|x\| \le 1} \|Bx\| for every n×nn \times n matrix BB and ∥x∥=∑i=1n∣xi∣2\|x\| = \sqrt{\sum_{i=1}^{n} |x_i|^2} for every complex vector x∈Cnx \in \mathbb{C}^n.)

    Hints and solution