Olympiad problems

1999 IMC, 6

Let $A$ be a subset of $\mathbb{Z}/n\mathbb{Z}$ with at most $\frac{\ln(n)}{100}$ elements. Define $f(r)=\sum_{s\in A} e^{\dfrac{2 \pi i r s}{n}}$. Show that for some $r \ne 0$ we have $|f(r)| \geq \frac{|A|}{2}$.

2012 IMC, 1

Tags: function , IMC , college contests

For every positive integer $n$, let $p(n)$ denote the number of ways to express $n$ as a sum of positive integers. For instance, $p(4)=5$ because \[4=3+1=2+2=2+1+1=1+1+1.\] Also define $p(0)=1$. Prove that $p(n)-p(n-1)$ is the number of ways to express $n$ as a sum of integers each of which is strictly greater than 1. [i]Proposed by Fedor Duzhin, Nanyang Technological University.[/i]

2003 IMC, 4

Tags: IMC , college contests

Determine the set of all pairs (a,b) of positive integers for which the set of positive integers can be decomposed into 2 sets A and B so that $a\cdot A=b\cdot B$.

2020 IMC, 3

Tags: IMC , convex geometry , geometry , combinatorial geometry , advanced fields , IMC 2020

Let $d \ge 2$ be an integer. Prove that there exists a constant $C(d)$ such that the following holds: For any convex polytope $K\subset \mathbb{R}^d$, which is symmetric about the origin, and any $\varepsilon \in (0, 1)$, there exists a convex polytope $L \subset \mathbb{R}^d$ with at most $C(d) \varepsilon^{1-d}$ vertices such that \[(1-\varepsilon)K \subseteq L \subseteq K.\] Official definitions: For a real $\alpha,$ a set $T \in \mathbb{R}^d$ is a [i]convex polytope with at most $\alpha$ vertices[/i], if $T$ is a convex hull of a set $X \in \mathbb{R}^d$ of at most $\alpha$ points, i.e. $T = \{\sum\limits_{x\in X} t_x x | t_x \ge 0, \sum\limits_{x \in X} t_x = 1\}.$ Define $\alpha K = \{\alpha x | x \in K\}.$ A set $T \in \mathbb{R}^d$ is [i]symmetric about the origin[/i] if $(-1)T = T.$

2003 IMC, 1

Tags: limit , IMC , college contests

(a) Let $a_1,a_2,...$ be a sequenceof reals with $a_1=1$ and $a_{n+1}>\frac32 a_n$ for all $n$. Prove that $\lim_{n\rightarrow\infty}\frac{a_n}{\left(\frac32\right)^{n-1}}$ exists. (finite or infinite) (b) Prove that for all $\alpha>1$ there is a sequence $a_1,a_2,...$ with the same properties such that $\lim_{n\rightarrow\infty}\frac{a_n}{\left(\frac32\right)^{n-1}}=\alpha$

2006 IMC, 4

Tags: function , algebra , polynomial , rational function , IMC , college contests

Let f be a rational function (i.e. the quotient of two real polynomials) and suppose that $f(n)$ is an integer for infinitely many integers n. Prove that f is a polynomial.

2005 IMC, 5

Tags: IMC , college contests

Find all $ r > 0$ such that when $ f: \mathbb R^{2}\to \mathbb R$ is differentiable, $ \|\textrm{grad} \; f(0,0)\| \equal{} 1$, $ \|\textrm{grad} \; f(u) \minus{} \textrm{grad} \; f(v)\| \leq \| u \minus{} v\|$, then the max of $ f$ on the disk $ \|u\|\leq r$, is attained at exactly one point.

2017 IMC, 2

Tags: function , IMC , imc 2017 , calculus

Let $f:\mathbb R\to(0,\infty)$ be a differentiabe function, and suppose that there exists a constant $L>0$ such that $$|f'(x)-f'(y)|\leq L|x-y|$$ for all $x,y$. Prove that $$(f'(x))^2<2Lf(x)$$ holds for all $x$.

2013 IMC, 4

Tags: number theory , IMC , college contests

Does there exist an infinite set $\displaystyle{M}$ consisting of positive integers such that for any $\displaystyle{a,b \in M}$ with $\displaystyle{a < b}$ the sum $\displaystyle{a + b}$ is square-free? [b]Note.[/b] A positive integer is called square-free if no perfect square greater than $\displaystyle{1}$ divides it. [i]Proposed by Fedor Petrov, St. Petersburg State University.[/i]

2013 IMC, 1

Tags: linear algebra , matrix , vector , inequalities , IMC , college contests

Let $\displaystyle{A}$ and $\displaystyle{B}$ be real symmetric matrixes with all eigenvalues strictly greater than $\displaystyle{1}$. Let $\displaystyle{\lambda }$ be a real eigenvalue of matrix $\displaystyle{{\rm A}{\rm B}}$. Prove that $\displaystyle{\left| \lambda \right| > 1}$. [i]Proposed by Pavel Kozhevnikov, MIPT, Moscow.[/i]

1994 IMC, 1

Tags: IMC , real analysis

Let $f\in C^1[a,b]$, $f(a)=0$ and suppose that $\lambda\in\mathbb R$, $\lambda >0$, is such that $$|f'(x)|\leq \lambda |f(x)|$$ for all $x\in [a,b]$. Is it true that $f(x)=0$ for all $x\in [a,b]$?

2008 IMC, 2

Tags: vector , algebra , polynomial , IMC , college contests

Denote by $\mathbb{V}$ the real vector space of all real polynomials in one variable, and let $\gamma :\mathbb{V}\to \mathbb{R}$ be a linear map. Suppose that for all $f,g\in \mathbb{V}$ with $\gamma(fg)=0$ we have $\gamma(f)=0$ or $\gamma(g)=0$. Prove that there exist $c,x_0\in \mathbb{R}$ such that \[ \gamma(f)=cf(x_0)\quad \forall f\in \mathbb{V}\]

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)

2004 IMC, 4

Tags: linear algebra , matrix , algebra , polynomial , vector , IMC , college contests

For $n\geq 1$ let $M$ be an $n\times n$ complex array with distinct eigenvalues $\lambda_1,\lambda_2,\ldots,\lambda_k$, with multiplicities $m_1,m_2,\ldots,m_k$ respectively. Consider the linear operator $L_M$ defined by $L_MX=MX+XM^T$, for any complex $n\times n$ array $X$. Find its eigenvalues and their multiplicities. ($M^T$ denotes the transpose matrix of $M$).

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)

2005 IMC, 4

Tags: calculus , derivative , geometry , trapezoid , integration , rectangle , IMC

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a three times differentiable function. Prove that there exists $w \in [-1,1]$ such that \[ \frac{f'''(w)}{6} = \frac{f(1)}{2}-\frac{f(-1)}{2}-f'(0). \]

1994 IMC, 4

Tags: IMC , linear algebra

Let $\alpha\in\mathbb R\backslash \{ 0 \}$ and suppose that $F$ and $G$ are linear maps (operators) from $\mathbb R^n$ into $\mathbb R^n$ satisfying $F\circ G - G\circ F=\alpha F$. a) Show that for all $k\in\mathbb N$ one has $F^k\circ G-G\circ F^k=\alpha kF^k$. b) Show that there exists $k\geq 1$ such that $F^k=0$.

2004 IMC, 5

Tags: inequalities , IMC , college contests

Let $S$ be a set of $\displaystyle { 2n \choose n } + 1$ real numbers, where $n$ is an positive integer. Prove that there exists a monotone sequence $\{a_i\}_{1\leq i \leq n+2} \subset S$ such that \[ |x_{i+1} - x_1 | \geq 2 | x_i - x_1 | , \] for all $i=2,3,\ldots, n+1$.

2014 IMC, 5

Tags: IMC , geometry , geometric transformation , college contests

Let $A_{1}A_{2} \dots A_{3n}$ be a closed broken line consisting of $3n$ lines segments in the Euclidean plane. Suppose that no three of its vertices are collinear, and for each index $i=1,2,\dots,3n$, the triangle $A_{i}A_{i+1}A_{i+2}$ has counterclockwise orientation and $\angle A_{i}A_{i+1}A_{i+2} = 60º$, using the notation $A_{3n+1} = A_{1}$ and $A_{3n+2} = A_{2}$. Prove that the number of self-intersections of the broken line is at most $\frac{3}{2}n^{2} - 2n + 1$

1994 IMC, 5

Tags: IMC , calculus , real analysis

a) Let $f\in C[0,b]$, $g\in C(\mathbb R)$ and let $g$ be periodic with period $b$. Prove that $\int_0^b f(x) g(nx)\,\mathrm dx$ has a limit as $n\to\infty$ and $$\lim_{n\to\infty}\int_0^b f(x)g(nx)\,\mathrm dx=\frac 1b \int_0^b f(x)\,\mathrm dx\cdot\int_0^b g(x)\,\mathrm dx$$ b) Find $$\lim_{n\to\infty}\int_0^\pi \frac{\sin x}{1+3\cos^2nx}\,\mathrm dx$$

2006 IMC, 5

Tags: algebra , polynomial , Vieta , IMC , college contests

Show that there are an infinity of integer numbers $m,n$, with $gcd(m,n)=1$ such that the equation $(x+m)^{3}=nx$ has 3 different integer sollutions.

2004 IMC, 1

Tags: IMC , college contests

Let $S$ be an infinite set of real numbers such that $|x_1+x_2+\cdots + x_n | \leq 1 $ for all finite subsets $\{x_1,x_2,\ldots,x_n\} \subset S$. Show that $S$ is countable.

2020 IMC, 7

Tags: IMC , group theory , abstract algebra , superior algebra , IMC 2020

Let $G$ be a group and $n \ge 2$ be an integer. Let $H_1, H_2$ be $2$ subgroups of $G$ that satisfy $$[G: H_1] = [G: H_2] = n \text{ and } [G: (H_1 \cap H_2)] = n(n-1).$$ Prove that $H_1, H_2$ are conjugate in $G.$ Official definitions: $[G:H]$ denotes the index of the subgroup of $H,$ i.e. the number of distinct left cosets $xH$ of $H$ in $G.$ The subgroups $H_1, H_2$ are conjugate if there exists $g \in G$ such that $g^{-1} H_1 g = H_2.$

2023 IMC, 5

Tags: abstract algebra , combinatorics , permutations , probability , IMC , IMC 2023

Fix positive integers $n$ and $k$ such that $2 \le k \le n$ and a set $M$ consisting of $n$ fruits. A [i]permutation[/i] is a sequence $x=(x_1,x_2,\ldots,x_n)$ such that $\{x_1,\ldots,x_n\}=M$. Ivan [i]prefers[/i] some (at least one) of these permutations. He realized that for every preferred permutation $x$, there exist $k$ indices $i_1 < i_2 < \ldots < i_k$ with the following property: for every $1 \le j < k$, if he swaps $x_{i_j}$ and $x_{i_{j+1}}$, he obtains another preferred permutation. \\ Prove that he prefers at least $k!$ permutations.