3.2.1 Problem Portfolio
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: 11/11
Let $n \ge 7$ be a positive integer. Weronika has an $n \times n$ field of unit squares in which to graze her $n$ elephants. To stop the elephants escaping, the border of the field is fenced off.
Weronika has to place each elephant in a unit square inside the field such that there is at most one elephant in each row and at most one elephant in each column. She also wants to put additional fences inside the field. A single fence covers the edge between two unit squares. She wants to add these fences so that the elephants are separated and unable to meet (a elephant can move between two unit squares if they share an edge that has not been covered by a fence, and two elephants can meet if they can move to two unit squares sharing an edge that has not been covered by a fence).
What is the minimum number of fences Weronika has to add so that both conditions can hold (the initial placement of the $n$ elephants having at most one elephant per row and column, and them not being able to meet afterwards) as a function of $n$?
Remark: Weronika places the elephants and the fences, and wants the minimum given the ability to choose both.
Manu is writing an ebook about sunglasses, but because of a problem with his $\LaTeX$ compiler, the $N$ pages of the pdf appear in a completely random order. Thankfully, Brigitte has vibe-coded some software to help Manu fix his pdf. Her program can do two different actions:
-
Reverse the order of the pages in the pdf, putting the first page in the last position, the second page in the penultimate position, and so forth, up to putting the last page in the first position.
-
If the first page is page number $M$, the program can order the $M$ first pages of the pdf, but in decreasing order.
For instance, if the order of the pages is currently $3, 4, 2, 5, 1$ then choosing the first action would give $1, 5, 2, 4, 3$, whilst choosing the second action would instead give $4, 3, 2, 5, 1$.
Prove that even with this terrible program, Manu can eventually put his pdf back in the right order.
Let $n$ be a positive integer. There is a magical door at Hogwarts with levers labelled from $1$ to $n$. Lever $i$ can either be up or down, and toggling between the two costs $2^{i-1}$ Galleons. Every possible combination of lever positions makes the door lead to a different location. Initially, all the levers are down.
The $2^n$ members of Dumbledore’s Army are being chased by Voldemort and want to use the magical door to split up so that each person travels to a different location. What is the minimum amount of Galleons they have to spend in total?
Remark: Dumbledore’s Army may send a member through the door before switching any lever.
There are finitely many integers on a board, all of which are at least $2$. Pingu repeatedly carries out the following step: first, Pingu chooses an integer $n \ge 2$ that is coprime to every integer currently on the board. Pingu then replaces each integer $x$ on the board with the unique integer $y \in {1, 2, \dots, n-1}$ such that $xy \equiv 1 \pmod n$.
Pingu stops as soon as there is a $1$ anywhere on the board at the end of a step. If at this point, there is also a number different from $1$ on the board, Pingu loses. Otherwise, if all the numbers are $1$, Pingu wins. Prove that Pingu can always win, regardless of the starting integers.
Example: In a step, if Pingu chooses $n = 11$, Pingu replaces $3, 8, 13, 8$ with $4, 7, 6, 7$.
We call a strictly increasing sequence $a_1, a_2, \dots, a_{2026}$ of positive integers indivisible if for all $2 \le k \le 2026$, the sum of any $k$ consecutive terms is not divisible by $k$.
Prove that an indivisible sequence exists and determine the smallest possible value of the last term in an indivisible sequence.
Let $n$ be a positive integer. Archi and Baldibus are constructing a number on a blackboard, one digit at a time. To start, Archi writes down one of the nine digits from $1$ to $9$. Then, starting with Baldibus, the two players alternate the following:
-
Baldibus appends one of the ten digits from $0$ to $9$ to the end of the current number.
-
Archi prepends one of the nine digits from $1$ to $9$ to the front of the current number.
Archi wins if, immediately after Archi writes a digit, the number on the board is divisible by $n$. Determine the values of $n$ for which Archi can guarantee a win, no matter what Baldibus does.
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.
During the World Cup, there are $n$ different Panini stickers to collect. Marco’s friends are trying to complete their collection, but nobody has a full set of stickers yet! A pair of his friends are said to be wholesome if their combined collection has at least one of each sticker.
Marco knows the contents of everyone’s collections, and wants to take them all to a restaurant for his birthday. However, he doesn’t want any wholesome pairs sitting at the same table.
-
Show that Marco might need to reserve at least $n$ different tables.
-
Show that $n$ tables will always be enough for Marco to achieve his goal.
Let $k$ be a circle centered at $O$ and let $X, A, Y$ be three points on $k$ in this order such that the tangent to the circumcircle of triangle $OXA$ through $X$ and the tangent to the circumcircle of $OAY$ through $Y$ are parallel. Show that $XAY = 120^\circ$ if $A$ lies on the minor arc $XY$.
Remark: The minor arc $XY$ is the shorter arc of the circle $k$ linking $X$ and $Y$.
A school class of $n \geq 2$ children is taking several group pictures. For every group with at least one child, there is exactly one picture depicting this specific group. The pictures are now hung up in different rooms in the school, such that every child appears in at most one photo per room.
-
Show that this is possible if the school has $2^{n-1}$ rooms.
-
Show that this is not possible if the school has less than $2^{n-1}$ rooms.
Let $(m, n)$ be a pair of positive integers. Julia has carefully planted $m$ rows of$n$ dandelions in an $m \times n$ array in her back garden. Now, Jana and Viviane decide to play a game with a lawnmower they just found.
Taking alternating turns and starting with Jana, they can mow down all the dandelions in a straight horizontal or vertical line (and they must mow down at least one dandelion!). The winner is the player who mows down the final dandelion.
Determine all pairs $(m, n)$ for which Jana has a winning strategy.