Unofficial archive — problems, solutions & results © IMC, reproduced with permission.

Studolymp / IMC / 2022

IMC 2022
contestants 663 · problems 8 (4+4) · scale 0–10 · per-problem yes

Problems

Day 1

P1

Let f:[0,1](0,)f : [0, 1] \to (0, \infty) be an integrable function such that f(x)f(1x)=1f(x) \cdot f(1 - x) = 1 for all x[0,1]x \in [0, 1]. Prove that 01f(x)dx1.\int_0^1 f(x)\,dx \ge 1. (proposed by Mike Daas, Universiteit Leiden)

P2

Let nn be a positive integer. Find all n×nn \times n real matrices AA with only real eigenvalues satisfying A+Ak=ATA + A^k = A^T for some integer knk \ge n.

(ATA^T denotes the transpose of AA.)

(proposed by Camille Mau, Nanyang Technological University)

P3

Let pp be a prime number. A flea is staying at point 0 of the real line. At each minute, the flea has three possibilities: to stay at its position, or to move by 1 to the left or to the right. After p1p - 1 minutes, it wants to be at 0 again. Denote by f(p)f(p) the number of its strategies to do this (for example, f(3)=3f(3) = 3: it may either stay at 0 for the entire time, or go to the left and then to the right, or go to the right and then to the left). Find f(p)f(p) modulo pp.

(proposed by Fedor Petrov, St. Petersburg)

P4

Let n>3n > 3 be an integer. Let Ω\Omega be the set of all triples of distinct elements of {1,2,,n}\{1, 2, \dots, n\}. Let mm denote the minimal number of colours which suffice to colour Ω\Omega so that whenever 1a<b<c<dn1 \le a < b < c < d \le n, the triples {a,b,c}\{a, b, c\} and {b,c,d}\{b, c, d\} have different colours. Prove that 1100loglognm100loglogn.\frac{1}{100} \log\log n \leqslant m \leqslant 100 \log\log n. (proposed by Danila Cherkashin, St. Petersburg)

Day 2

P5

We colour all the sides and diagonals of a regular polygon PP with 43 vertices either red or blue in such a way that every vertex is an endpoint of 20 red segments and 22 blue segments. A triangle formed by vertices of PP is called monochromatic if all of its sides have the same colour. Suppose that there are 2022 blue monochromatic triangles. How many red monochromatic triangles are there?

(proposed by Mike Daas, Universiteit Leiden)

P6

Let p>2p > 2 be a prime number. Prove that there is a permutation (x1,x2,,xp1)(x_1, x_2, \dots, x_{p-1}) of the numbers (1,2,,p1)(1, 2, \dots, p-1) such that x1x2+x2x3++xp2xp12(modp).x_1 x_2 + x_2 x_3 + \dots + x_{p-2} x_{p-1} \equiv 2 \pmod p. (proposed by Giorgi Arabidze, Tbilisi Free University, Georgia)

P7

Let A1,A2,,AkA_1, A_2, \dots, A_k be n×nn \times n idempotent complex matrices such that AiAj=AjAifor all ij.A_i A_j = -A_j A_i \quad \text{for all } i \ne j. Prove that at least one of the given matrices has rank nk\le \dfrac{n}{k}.

(A matrix AA is called idempotent if A2=AA^2 = A.)

(proposed by Danila Belousov, Novosibirsk)

P8

Let n,k3n, k \ge 3 be integers, and let SS be a circle. Let nn blue points and kk red points be chosen uniformly and independently at random on the circle SS. Denote by FF the intersection of the convex hull of the red points and the convex hull of the blue points. Let mm be the number of vertices of the convex polygon FF (in particular, m=0m = 0 when FF is empty). Find the expected value of mm.

(proposed by Fedor Petrov, St. Petersburg)