Olympiad problems

2004 IMC, 2

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

Let $f_1(x)=x^2-1$, and for each positive integer $n \geq 2$ define $f_n(x) = f_{n-1}(f_1(x))$. How many distinct real roots does the polynomial $f_{2004}$ have?

2023 IMC, 6

Tags: combinatorics , matrix , IMC , linear algebra , IMC 2023

Ivan writes the matrix $\begin{pmatrix} 2 & 3\\ 2 & 4\end{pmatrix}$ on the board. Then he performs the following operation on the matrix several times: [b]1.[/b] he chooses a row or column of the matrix, and [b]2.[/b] he multiplies or divides the chosen row or column entry-wise by the other row or column, respectively. Can Ivan end up with the matrix $\begin{pmatrix} 2 & 4\\ 2 & 3\end{pmatrix}$ after finitely many steps?

2007 IMC, 2

Tags: linear algebra , matrix , induction , IMC , college contests

Let $ n\ge 2$ be an integer. What is the minimal and maximal possible rank of an $ n\times n$ matrix whose $ n^{2}$ entries are precisely the numbers $ 1, 2, \ldots, n^{2}$?

2011 IMC, 3

Tags: logarithms , limit , IMC , college contests

Calculate $\displaystyle \sum_{n=1}^\infty \ln \left(1+\frac{1}{n}\right) \ln\left( 1+\frac{1}{2n}\right)\ln\left( 1+\frac{1}{2n+1}\right)$.

2009 IMC, 5

Tags: geometry , 3D geometry , sphere , IMC , college contests

Let $n$ be a positive integer. An $n-\emph{simplex}$ in $\mathbb{R}^n$ is given by $n+1$ points $P_0, P_1,\cdots , P_n$, called its vertices, which do not all belong to the same hyperplane. For every $n$-simplex $\mathcal{S}$ we denote by $v(\mathcal{S})$ the volume of $\mathcal{S}$, and we write $C(\mathcal{S})$ for the center of the unique sphere containing all the vertices of $\mathcal{S}$. Suppose that $P$ is a point inside an $n$-simplex $\mathcal{S}$. Let $\mathcal{S}_i$ be the $n$-simplex obtained from $\mathcal{S}$ by replacing its $i^{\text{th}}$ vertex by $P$. Prove that : \[ \sum_{j=0}^{n}v(\mathcal{S}_j)C(\mathcal{S}_j)=v(\mathcal{S})C(\mathcal{S}) \]

2023 IMC, 2

Tags: linear algebra , matrix , IMC , IMC 2023

Let $A$, $B$ and $C$ be $n \times n$ matrices with complex entries satisfying $$A^2=B^2=C^2 \text{ and } B^3 = ABC + 2I.$$ Prove that $A^6=I$.

2019 IMC, 10

Tags: probability , college contests , IMC

$2019$ points are chosen at random, independently, and distributed uniformly in the unit disc $\{(x,y)\in\mathbb R^2: x^2+y^2\le 1\}$. Let $C$ be the convex hull of the chosen points. Which probability is larger: that $C$ is a polygon with three vertices, or a polygon with four vertices? [i]Proposed by Fedor Petrov, St. Petersburg State University[/i]

2012 IMC, 3

Tags: group theory , abstract algebra , IMC , college contests

Given an integer $n>1$, let $S_n$ be the group of permutations of the numbers $1,\;2,\;3,\;\ldots,\;n$. Two players, A and B, play the following game. Taking turns, they select elements (one element at a time) from the group $S_n$. It is forbidden to select an element that has already been selected. The game ends when the selected elements generate the whole group $S_n$. The player who made the last move loses the game. The first move is made by A. Which player has a winning strategy? [i]Proposed by Fedor Petrov, St. Petersburg State University.[/i]

2008 IMC, 4

Tags: algebra , polynomial , pigeonhole principle , IMC , college contests

Let $ \mathbb{Z}[x]$ be the ring of polynomials with integer coefficients, and let $ f(x), g(x) \in\mathbb{Z}[x]$ be nonconstant polynomials such that $ g(x)$ divides $ f(x)$ in $ \mathbb{Z}[x]$. Prove that if the polynomial $ f(x)\minus{}2008$ has at least 81 distinct integer roots, then the degree of $ g(x)$ is greater than 5.

2009 IMC, 4

Tags: modular arithmetic , algebra , polynomial , IMC , college contests

Let $p$ be a prime number and $\mathbf{W}\subseteq \mathbb{F}_p[x]$ be the smallest set satisfying the following : [list] (a) $x+1\in \mathbf{W}$ and $x^{p-2}+x^{p-3}+\cdots +x^2+2x+1\in \mathbf{W}$ (b) For $\gamma_1,\gamma_2$ in $\mathbf{W}$, we also have $\gamma(x)\in \mathbf{W}$, where $\gamma(x)$ is the remainder $(\gamma_1\circ \gamma_2)(x)\pmod {x^p-x}$.[/list] How many polynomials are in $\mathbf{W}?$

2017 IMC, 4

Tags: imc 2017 , IMC , combinatorics , approximation , Probabilistic Method

There are $n$ people in a city, and each of them has exactly $1000$ friends (friendship is always symmetric). Prove that it is possible to select a group $S$ of people such that at least $\frac{n}{2017}$ persons in $S$ have exactly two friends in $S$.

2023 IMC, 1

Tags: calculus , derivative , functional equation , IMC , function , IMC 2023

Find all functions $f: \mathbb{R} \to \mathbb{R}$ that have a continuous second derivative and for which the equality $f(7x+1)=49f(x)$ holds for all $x \in \mathbb{R}$.

2013 IMC, 5

Tags: function , complex numbers , IMC , college contests

Does there exist a sequence $\displaystyle{\left( {{a_n}} \right)}$ of complex numbers such that for every positive integer $\displaystyle{p}$ we have that $\displaystyle{\sum\limits_{n = 1}^{ + \infty } {a_n^p} }$ converges if and only if $\displaystyle{p}$ is not a prime? [i]Proposed by Tomáš Bárta, Charles University, Prague.[/i]

2006 IMC, 1

Tags: induction , IMC , college contests

Let $V$ be a convex polygon. (a) Show that if $V$ has $3k$ vertices, then $V$ can be triangulated such that each vertex is in an odd number of triangles. (b) Show that if the number of vertices is not divisible with 3, then $V$ can be triangulated such that exactly 2 vertices have an even number of triangles.

2023 IMC, 3

Tags: algebra , polynomial , IMC , functional equation , IMC 2023

Find all polynomials $P$ in two variables with real coefficients satisfying the identity $$P(x,y)P(z,t)=P(xz-yt,xt+yz).$$

2020 IMC, 2

Tags: IMC , linear algebra , IMC 2020

$A, B$ are $n \times n$ matrices such that $\text{rank}(AB-BA+I) = 1.$ Prove that $\text{tr}(ABAB)-\text{tr}(A^2 B^2) = \frac{1}{2}n(n-1).$

2006 IMC, 6

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

The scores of this problem were: one time 17/20 (by the runner-up) one time 4/20 (by Andrei Negut) one time 1/20 (by the winner) the rest had zero... just to give an idea of the difficulty. Let $A_{i},B_{i},S_{i}$ ($i=1,2,3$) be invertible real $2\times 2$ matrices such that [list][*]not all $A_{i}$ have a common real eigenvector, [*]$A_{i}=S_{i}^{-1}B_{i}S_{i}$ for $i=1,2,3$, [*]$A_{1}A_{2}A_{3}=B_{1}B_{2}B_{3}=I$.[/list] Prove that there is an invertible $2\times 2$ matrix $S$ such that $A_{i}=S^{-1}B_{i}S$ for all $i=1,2,3$.

2014 IMC, 3

Tags: IMC , college contests , calculus , derivative , function

Let $f(x)=\frac{\sin x}{x}$, for $x>0$, and let $n$ be a positive integer. Prove that $|f^{(n)}(x)|<\frac{1}{n+1}$, where $f^{(n)}$ denotes the $n^{\mathrm{th}}$ derivative of $f$. (Proposed by Alexander Bolbot, State University, Novosibirsk)

2008 IMC, 5

Tags: group theory , abstract algebra , IMC , college contests

Does there exist a finite group $ G$ with a normal subgroup $ H$ such that $ |\text{Aut } H| > |\text{Aut } G|$? Disprove or provide an example. Here the notation $ |\text{Aut } X|$ for some group $ X$ denotes the number of isomorphisms from $ X$ to itself.

2008 IMC, 5

Tags: linear algebra , matrix , IMC , college contests

Let $ n$ be a positive integer, and consider the matrix $ A \equal{} (a_{ij})_{1\leq i,j\leq n}$ where $ a_{ij} \equal{} 1$ if $ i\plus{}j$ is prime and $ a_{ij} \equal{} 0$ otherwise. Prove that $ |\det A| \equal{} k^2$ for some integer $ k$.

2005 IMC, 1

Tags: linear algebra , matrix , IMC , college contests

Let $A$ be a $n\times n$ matrix such that $A_{ij} = i+j$. Find the rank of $A$. [hide="Remark"]Not asked in the contest: $A$ is diagonalisable since real symetric matrix it is not difficult to find its eigenvalues.[/hide]

2004 IMC, 3

Tags: inequalities , triangle inequality , IMC , college contests

Let $D$ be the closed unit disk in the plane, and let $z_1,z_2,\ldots,z_n$ be fixed points in $D$. Prove that there exists a point $z$ in $D$ such that the sum of the distances from $z$ to each of the $n$ points is greater or equal than $n$.

2009 IMC, 2

Tags: function , inequalities , IMC , college contests , Integral inequality

Suppose $f:\mathbb{R}\to \mathbb{R}$ is a two times differentiable function satisfying $f(0)=1,f^{\prime}(0)=0$ and for all $x\in [0,\infty)$, it satisfies \[ f^{\prime \prime}(x)-5f^{\prime}(x)+6f(x)\ge 0 \] Prove that, for all $x\in [0,\infty)$, \[ f(x)\ge 3e^{2x}-2e^{3x} \]

2006 IMC, 3

Tags: trigonometry , logarithms , IMC , college contests

Compare $\tan(\sin x)$ with $\sin(\tan x)$, for $x\in \left]0,\frac{\pi}{2}\right[$.

2008 IMC, 6

Tags: IMC , college contests

For a permutation $ \sigma\in S_n$ with $ (1,2,\dots,n)\mapsto(i_1,i_2,\dots,i_n)$, define \[ D(\sigma) \equal{} \sum_{k \equal{} 1}^n |i_k \minus{} k| \] Let \[ Q(n,d) \equal{} \left|\left\{\sigma\in S_n : D(\sigma) \equal{} d\right\}\right| \] Show that when $ d \geq 2n$, $ Q(n,d)$ is an even number.