Problem Portfoli
This is the collection of my original problems that have appeared in mathematical Olympiads. For some of them, partial credit goes to my colleagues. Problems are stated as they appeared in the competition, with minor stylistic adjustments.Displayed: 36/36
Leo’s garden has now been passed on to his niece Batlpàsz, who is a bit disappointed by her inheritance at first. However, one day, she gets a letter from Frieder telling her that there is buried treasure under one of the $2025$ gnomes in the garden, but she doesn’t know which one. Some pairs of gnomes are directly connected by a dirt path, and at most three dirt paths meet at each gnome. Bàtlpasz can get from any gnome to any other gnome by walking along some of the dirt paths. However, removing any single dirt path would split the gnomes into exactly two separate connected groups, with no way to get from one group to the other. In the middle of each dirt path is a fairy that can tell Batlpàsz which direction along the path she has to go to get to the gnome with the treasure. Every morning for a fortnight, Batlpàsz may ask a fairy for help. After the fourteenth question, if Batlpàsz has not found the location of the treasure, it will vanish. Can Batlpàsz always find the treasure, no matter how the dirt paths are arranged?
Let $\alpha$ be a real number satisfying $0 < \alpha < 180$. For Leo’s birthday, Frieder has placed $2025$ gnomes at arbitrary points inside his garden. No three gnomes are collinear and no two gnomes coincide. Each gnome has a field of view spanning $\alpha$ degrees (including the boundary). After Frieder places the gnomes down, Leo wants to rotate the gnomes such that, for each gnome, the number of other gnomes it sees is different. Determine all values of $\alpha$ for which Leo can achieve this, regardless of how the gnomes are placed.
Let $n$ be a positive integer and let $P(x)$ denote the polynomial
\[x^n + a_{n-1}x^{n-1} + \dots + a_1 x + a_0\]with real coefficients and $a_0 \neq 0$, whose $n$ roots are all pairwise distinct, positive real numbers. Assuming that $P(x)$ divides $P(2x)P(x/2)$, prove that
\[\frac{a_{n-1} a_1}{a_0} \ge \frac{9n^2}8.\]Let $n,a,b$ be positive integers with $n \geq 2$. Aru and Wero are playing a game on a $n\times n$ grid. At the beginning, there is a single pebble in the bottom-left corner. A move consists of removing one pebble from some non-empty square $S$ and performing at least one (possibly both) of:
- adding $a$ pebbles to the right neighbour of $S$;
- adding $b$ pebbles to the upper neighbour of $S$.
Aru starts and they alternate moves. The first player that cannot make a move loses. Determine who, if anyone, has a winning strategy in terms of $n, a, b$.
Determine all triples of positive integers $(p, q, a)$ such that $p$ and $q$ are prime numbers and
\[p^q - q^a = 2025.\]Let $a,b$ be positive integers. Prove that the expression
\[\frac{\gcd(a+b,ab)}{\gcd(a,b)}\]is always a positive integer, and determine all possible values it can take.
Determine all positive integers $n$ satisfying all of the following properties:
- there exist exactly three distinct prime numbers dividing $n$,
- $n$ is equal to $\binom{m}{3}$ for some positive integer $m$, and
- $n+1$ is a perfect square.
If $a$ and $b$ are positive integers, we say that $a$ almost divides $b$ if $a$ divides at least one of $b-1$ and $b+1$. We call a positive integer $n$ almost prime if the following holds: for any positive integers $a$, $b$ such that $n$ almost divides $ab$, we have that $n$ almost divides at least one of $a$ and $b$. Determine all almost prime numbers.
Determine all positive integers $n$ with the property that for each divisor $x$ of $n$ there exists a divisor $y$ of $n$ such that $x+y\mid n$.
Remark: The divisors may be negative.
Determine all triples $(a,b,n)$ of positive integers where $a$ divides $n$, $b$ divides $n$, and
\[(a+1)(b+1) = n.\]Let $n$ be a positive integer. Annalena has $n$ different bowls numbered $1$ to $n$ and also $n$ apples, $2n$ bananas and $5n$ strawberries. She wants to combine ingredients in each bowl to make fruit salad. The fruit salad is delicious if it contains strictly more strawberries than bananas and strictly more bananas than apples. How many ways are there for Annalena to distribute all the fruits to make delicious fruit salad in each of the different bowls?
Remark: A delicious fruit salad is allowed to not contain any apples.
Let $G$ be a graph whose vertices are the integers. Assume that any two integers are connected by a finite path in $G$. For two integers $x$ and $y$, we denote by $d(x,y)$ the length of the shortest path from $x$ to $y$, where the length of a path is the number of edges in it. Assume that $d(x,y)\mid x-y$ for all $x,y\in\mathbb{Z}$ and define $S(G) = {d(x,y)\mid x,y\in\mathbb{Z}}$. Find all possible sets $S(G)$.
Let $S$ be a non-empty set of positive integers such that for any $n\in S$, all positive divisors of $2^n+1$ are also in $S$. Prove that $S$ contains an integer of the form
\[(p_1 p_2 \dots p_{2023})^{2023},\]where $p_1,p_2, \ldots, p_{2023}$ are distinct prime numbers, all greater than $2023$.
Let $x,y$ and $a_0,a_1,a_2,\dots$ be integers satisfying $a_0 = a_1 = 0$ and
\[a_{n+2} = x\cdot a_{n+1} + y\cdot a_n + 1\]for all integers $n\geq 0$. Let $p$ be any prime number. Show that $\gcd(a_p,a_{p+1})$ is either equal to $1$ or greater than $\sqrt{p}$.
The wizards Albus and Brian are playing a game on a square of side length $2n+1$ metres surrounded by lava. In the centre of the square there sits a toad. In a turn, a wizard chooses a direction parallel to a side of the square and enchants the toad. This will cause the toad to jump $d$ metres in the chosen direction, where $d$ is initially equal to $1$ and increases by $1$ after each jump. The wizard who sends the toad into the lava loses. Albus begins and they take turns. Depending on $n$, determine which wizard has a winning strategy.
Let $ABC$ be an acute triangle with incentre $I$. On its circumcircle, let $M_A,M_B$ and $M_C$ be the midpoints of minor arcs $BC,CA$ and $AB$ respectively. Prove that the reflection of $M_A$ over the line $IM_B$ lies on the circumcircle of the triangle $IM_BM_C$.
On note $\mathbb{Z}$ l’ensemble des entiers relatifs. Trouver toutes les fonctions $f\colon\mathbb{Z}\to\mathbb{Z}$ telles que, pour tous les entiers $m$ et $n$:
\[f(m + n) + f(m)f(n) = n^2(f(m) + 1) + m^2(f(n) + 1) + mn(2 - mn).\]Let $n$ be a positive integer. There are $n$ purple and $n$ white cows queuing in a line in some order. Tim wishes to sort the cows by colour, such that all purple cows are at the front of the line. At each step, he is only allowed to swap two adjacent groups of equally many consecutive cows. What is the minimal number of steps Tim needs to be able to fulfil his wish, regardless of the initial alignment of the cows?
Example: For instance, Tim can perform the following three swaps:
\[W\underline{PW}\overline{PP}W \longrightarrow \underline{W}\overline{P}PPWW \longrightarrow P\underline{WP}\overline{PW}W \longrightarrow PPWWPW\]Let $n$ be a positive integer. Anna and Beatrice play a game with a deck of $n$ cards labelled with the numbers $1,2,\dots,n$. Initially, the deck is shuffled. The players take turns, starting with Anna. At each turn, if $k$ denotes the number written on the topmost card, then the player first looks at all the cards and then rearranges the $k$ topmost cards. If, after rearranging, the topmost card shows the number $k$ again, then the player has lost and the game ends. Otherwise, the turn of the other player begins. Determine, depending on the initial shuffle, if either player has a winning strategy, and if so, who does.
Let $ABCD$ be a convex quadrilateral such that the circle with diameter $AB$ is tangent to the line $CD$, and the circle with diameter $CD$ is tangent to the line $AB$. Prove that the two intersection points of these circles and the point $AC\cap BD$ are collinear.
Let $n$ be a positive integer. Prove that there exists a finite sequence $S$ consisting of only zeros and ones, satisfying the following property: For any positive integer $d\geq 2$, when $S$ is interpreted as a number in base $d$, the resulting number is non-zero and divisible by $n$.
Remark: The sequence $S = s_ks_{k-1}\cdots s_1s_0$ interpreted in base $d$ is the number $\sum_{i = 0}^k s_id^i$.
Let $ABC$ be a triangle and let $P$ be a point in the interior of the side $BC$. Let $I_1$ and $I_2$ be the incenters of the triangles $APB$ and $APC$, respectively. Let $X$ be the closest point to $A$ on the line $AP$ such that $XI_1$ is perpendicular to $XI_2$. Prove that the distance $AX$ is independent of the choice of $P$.
For an integer $a\geq 2$, denote by $\delta(a)$ the second largest divisor of $a$. Let $(a_n)_{n\geq 1}$ be a sequence of integers such that $a_1\geq 2$ and
\[a_{n+1} = a_n + \delta(a_n)\]for all $n\geq 1$. Prove that there exists a positive integer $k$ such that $a_k$ is divisible by $3^{2022}$.
Let $n\geq 2$ be an integer. Switzerland and Liechtenstein are performing their annual festive show. There is a field subdivided into $n \times n$ squares, in which the bottom-left square contains a red house with $k$ Swiss gymnasts, and the top-right square contains a blue house with $k$ Liechtensteiner gymnasts. Every other square only has enough space for a single gymnast at a time. Each second either a Swiss gymnast or a Liechtensteiner gymnast moves. The Swiss gymnasts moves to either the square immediately above or to the right and the Liechtensteiner gymnasts moves either to the square immediately below or to the left. The goal is to move all the Swiss gymnasts to the blue house and all the Liechtensteiner gymnasts to the red house, with the caveat that a gymnast cannot enter a house until all the gymnasts of the other nationality have left. Determine the largest $k$ in terms of $n$ for which this is possible.
Let $\mathbb{N}$ be the set of positive integers. Find all functions $f\colon \mathbb{N} \to \mathbb{N}$ such that both
- $f(f(m)f(n)) = mn$
- $f(2022a+1) = 2022a+1$
hold for all positive integers $m,n$ and $a$.
Let $n$ be a positive integer. Prove that the numbers
\[1^1,\ 3^3,\ 5^5,\ \dots,\ (2^n-1)^{2^n-1}\]all give different remainders when divided by $2^n$.
We call a positive integer silly if the sum of its positive divisors is a square. Prove that there are infinitely many silly numbers.
Let $n$ be a positive integer. Some of the squares of a $3n \times 3n$ board are marked. For any marked square $T$, we denote by $\ell(T)$ the number of marked squares in the same row to the left of $T$ and by $d(T)$ the number of marked squares in the same column below $T$. Determine the maximal number of marked squares given that $\ell(T)+d(T)$ is even for every marked square $T$.
Let $m\geq n$ be positive integers. Frieder is given $mn$ posters of Linus with different integer dimensions $k \times l$ with $1 \le k \le m$ and $1 \le l \le n$. He must put them all up one by one on his bedroom wall without rotating them. Every time he puts up a poster, he can either put it on an empty spot on the wall, or on a spot where it entirely covers a single visible poster and does not overlap any other visible poster. Determine the minimal area of the wall that will be covered by posters.
Let $\mathbb{N}$ be the set of positive integers. Let $f\colon \mathbb{N}\to \mathbb{N}$ be a function such that for every $n\in \mathbb{N}$
\[f(n)-n < 2021 \quad \text{and} \quad \underbrace{f(f(\cdots f(f}_{f(n)}(n))\cdots)) = n.\]Prove that $f(n) = n$ for infinitely many $n\in \mathbb{N}$.
Anaëlle has $2n$ stones labelled $1,2,3,\ldots,2n$ as well as a red box and a blue box. She wants to put each of the $2n$ stones into one of the two boxes such that the stones $k$ and $2k$ are in different boxes for all $k=1,2,\dots,n$. How many possibilities does Anaëlle have to do so?
Remark: Partial points are awarded for computing the number of possibilities for any particular integer $n \geq 3$.
Find all functions $f: \mathbb{R}\to \mathbb{R}$ such that $0\leq f(x)\leq 2x$ for all $x\geq 0$ and such that for all $x,y\in \mathbb{R}$
\[f(x+y)=f(x+f(y)).\]Prove that for every positive integer $n$, there exists a finite subset of the squares of an infinite chessboard that can be tiled with indistinguishable $1\times 2$ dominoes in exactly $n$ ways.
Let $ABC$ be a triangle with circumcircle $k$. Let $A_1,B_1$ and $C_1$ be points on the interior of the sides $BC,CA$ and $AB$ respectively. Let $X$ be a point on $k$ and denote by $Y$ the second intersection of the circumcircles of $BC_1X$ and $CB_1X$. Define the points $P$ and $Q$ to be the intersections of $BY$ with $B_1A_1$ and $CY$ with $C_1A_1$, respectively. Prove that $A$ lies on the line $PQ$.
Let $\varphi$ denote the Euler phi-function. Prove that for every positive integer $n$ we have
\[2^{n(n+1)}\mid 32\cdot\varphi\left(2^{2^n}-1\right).\]Let $ABC$ be an acute triangle. Denote by $M_A$, $M_B$ and $M_C$ the midpoints of sides $BC$, $CA$ and $AB$, respectively. Let $M_A’$, $M_B’$ and $M_C’$ be respectively the midpoints of the minor arcs $BC$, $CA$ and $AB$ on the circumcircle of $ABC$. Let $P_A$ be the intersection of the lines $M_BM_C$ and the perpendicular to $M_B’ M_C’$ containing $A$. Let $P_B$ and $P_C$ be defined analogously. Prove that the lines $M_AP_A$, $M_BP_B$ and $M_CP_C$ meet at a point.