Alphonse and Beryl play a game involving $n$ safes. Each safe can be opened by a unique key and each key opens a unique safe. Beryl randomly shuffles the $n$ keys, and after placing one key inside each safe, she locks all of the safes with her master key. Alphonse then selects $m$ of the safes (where $m < n$), and Beryl uses her master key to open just the safes that Alphonse selected. Alphonse collects all of the keys inside these $m$ safes and tries to use these keys to open up the other $n - m$ safes. If he can open a safe with one of the $m$ keys, he can then use the key in that safe to try to open any of the remaining safes, repeating the process until Alphonse successfully opens all of the safes, or cannot open any more. Let $P_m(n)$ be the probability that Alphonse can eventually open all $n$ safes starting from his initial selection of $m$ keys. (a) Show that $P_2(3) = \frac23$. (b) Prove that $P_1(n) = \frac1n$. (c) For all integers $n \geq 2$, prove that $$P_2(n) = \frac2n \cdot P_1(n-1) + \frac{n-2}{n} \cdot P_2(n-1).$$ (d) Determine a formula for $P_2 (n)$.

In a convex $n$-gon, several diagonals are drawn. Among these diagonals, a diagonal is called [i]good[/i] if it intersects exactly one other diagonal drawn (in the interior of the $n$-gon). Find the maximum number of good diagonals.

Each cell of a $10 \times 10$ board is painted red, blue or white, with exactly twenty of them red. No two adjacent cells are painted in the same colour. A domino consists of two adjacent cells, and it is said to be good if one cell is blue and the other is white. (a) Prove that it is always possible to cut out $30$ good dominoes from such a board. (b) Give an example of such a board from which it is possible to cut out $40$ good dominoes. (c) Give an example of such a board from which it is not possible to cut out more than $30$ good dominoes.

Find all positive integers $n$ for which all positive divisors of $n$ can be put into the cells of a rectangular table under the following constraints: [list] [*]each cell contains a distinct divisor; [*]the sums of all rows are equal; and [*]the sums of all columns are equal. [/list]

Given a sequence of integers $A_1,A_2,\cdots A_{99}$ such that for every sub-sequence that contains $m$ consecutive elements, there exist not more than $max\{ \frac{m}{3} ,1\}$ odd integers. Let $S=\{ (i,j) \ | i<j \}$ such that $A_i$ is even and $A_j$ is odd. Find $max\{ |S|\}$.

Two positive integers are written on the blackboard. Mary records in her notebook the square of the smaller number and replaces the larger number on the blackboard by the difference of the two numbers. With the new pair of numbers, she repeats the process, and continues until one of the numbers on the blackboard becomes zero. What will be the sum of the numbers in Mary's notebook at that point? (4)

Starting at a vertex $x_0$, we walk over the edges of a connected graph $G$ according to the following rules: 1. We never walk the same edge twice in the same direction. 2. Once we reach a vertex $x \ne x_0$, never visited before, we mark the edge by which we come to $x$. We can use this marked edge to leave vertex $x$ only if we already have traversed, in both directions, all other edges incident to $x$. Show that, regardless of the path followed, we will always be stuck at $x_0$ and that all other edges will have been traveled in both directions.

[b]8.1 [/b] Construct a quadrilateral using side lengths and distances between the midpoints of the diagonals. [b]8.2[/b] It is known that $a,b$ and $\sqrt{a}+\sqrt{b} $ are rational numbers. Prove that then $\sqrt{a}$, $\sqrt{b} $ are rational. [b]8.3 / 9.2[/b] Solve equation $x^3 - [x]=3$ [b]8.4[/b] Prove that if in a triangle the angle bisector of the vertex, bisects the angle between the median and the altitude, then the triangle either isosceles or right. . [b]8.5[/b] Given $n$ numbers $x_1, x_2, . . . , x_n$, each of which is equal to $+1$ or $-1$. At the same time $$x_1x_2 + x_2x_3 + . . . + x_{n-1}x_n + x_nx_1 = 0 .$$ Prove that $n$ is divisible by $4$. [b]8.6[/b] There are $n$ points marked on the circle, and it is known that for of any two, one of the arcs connecting them has a measure less than $120^0$.Prove that all points lie on an arc of size $120^0$. PS. You should use hide for answers.Collected [url=https://artofproblemsolving.com/community/c3983442_1961_leningrad_math_olympiad]here[/url].

Erica intends to construct a subset $T$ of $S=\{ I,J,K,L,M,N \}$, but if she is unsure about including an element $x$ of $S$ in $T$, she will write $x$ in bold and include it in $T$. For example, $\{ I,J \},$ $\{ J,\mathbf{K},L \},$ and $\{ \mathbf{I},\mathbf{J},\mathbf{M},\mathbf{N} \}$ are valid examples of $T$, while $\{ I,J,\mathbf{J},K \}$ is not. Find the total number of such subsets $T$ that Erica can construct.

Find the greatest constant $\lambda$ such that for any doubly stochastic matrix of order 100, we can pick $150$ entries such that if the other $9850$ entries were replaced by $0$, the sum of entries in each row and each column is at least $\lambda$. Note: A doubly stochastic matrix of order $n$ is a $n\times n$ matrix, all entries are nonnegative reals, and the sum of entries in each row and column is equal to 1.

Is it possible in a plane mark $10$ red, $10$ blue and $10$ green points (all distinct) such that three conditions hold: $i)$ For every red point $A$ there exists a blue point closer to point $A$ than any other green point $ii)$ For every blue point $B$ there exists a green point closer to point $B$ than any other red point $iii)$ For every green point $C$ there exists a red point closer to point $C$ than any other blue point

Alice plays the following game of solitaire on a $20 \times 20$ chessboard. She begins by placing $100$ pennies, $100$ nickels, $100$ dimes, and $100$ quarters on the board so that each of the $400$ squares contains exactly one coin. She then chooses $59$ of these coins and removes them from the board. After that, she removes coins, one at a time, subject to the following rules: - A penny may be removed only if there are four squares of the board adjacent to its square (up, down, left, and right) that are vacant (do not contain coins). Squares “off the board” do not count towards this four: for example, a non-corner square bordering the edge of the board has three adjacent squares, so a penny in such a square cannot be removed under this rule, even if all three adjacent squares are vacant. - A nickel may be removed only if there are at least three vacant squares adjacent to its square. (And again, “off the board” squares do not count.) - A dime may be removed only if there are at least two vacant squares adjacent to its square (“off the board” squares do not count). - A quarter may be removed only if there is at least one vacant square adjacent to its square (“off the board” squares do not count). Alice wins if she eventually succeeds in removing all the coins. Prove that it is impossiblefor her to win.

There are 2002 towns in a kingdom. Some of the towns are connected by roads in such a manner that, if all roads from one city closed, one can still travel between any two cities. Every year, the kingdom chooses a non-self-intersecting cycle of roads, founds a new town, connects it by roads with each city from the chosen cycle, and closes all the roads from the original cycle. After several years, no non-self-intersecting cycles remained. Prove that at that moment there are at least 2002 towns, exactly one road going out from each of them.

Let's call several numbers written in a row a 'combination of numbers'. In the country of Robotland, some combinations of numbers have been declared prohibited. It is known that there are a finite number of forbidden combinations and there is an infinite decimal fraction that does not contain forbidden combinations. Prove that there is an infinite periodic decimal fraction that does not contain prohibited combinations.

Let $x$ and $n$ be integers such that $1\le x\le n$. We have $x+1$ separate boxes and $n-x$ identical balls. Define $f(n,x)$ as the number of ways that the $n-x$ balls can be distributed into the $x+1$ boxes. Let $p$ be a prime number. Find the integers $n$ greater than $1$ such that the prime number $p$ is a divisor of $f(n,x)$ for all $x\in\{1,2,\ldots ,n-1\}$.

Is it possible to divide a polygon with $21$ sides into $2022$ triangles in such a way that among all the vertices there are not three collinear?

In a sports competition in which several tests are carried out, only the three athletes $A, B, C$. In each event, the winner receives $x$ points, the second receives $y$ points, and the third receives $z$ points. There are no ties, and the numbers $x, y, z$ are distinct positive integers with $x$ greater than $y$, and $y$ greater than $z$. At the end of the competition it turns out that $A$ has accumulated $20$ points, $B$ has accumulated $10$ points and $C$ has accumulated $9$ points. We know that athlete $A$ was second in the 100-meter event. Determine which of the three athletes he was second in the jumping event.

The Baltic Sea has $2016$ harbours. There are two-way ferry connections between some of them. It is impossible to make a sequence of direct voyages $C_1 - C_2 - ... - C_{1062}$ where all the harbours $C_1, . . . , C_{1062}$ are distinct. Prove that there exist two disjoint sets $A$ and $B$ of $477$ harbours each, such that there is no harbour in $A$ with a direct ferry connection to a harbour in $B.$

There are $ n \geq 5$ pairwise different points in the plane. For every point, there are just four points whose distance from which is $ 1$. Find the maximum value of $ n$.

Let $n>2$ be an integer. In a country there are $n$ cities and every two of them are connected by a direct road. Each road is assigned an integer from the set $\{1, 2,\ldots ,m\}$ (different roads may be assigned the same number). The [i]priority[/i] of a city is the sum of the numbers assigned to roads which lead to it. Find the smallest $m$ for which it is possible that all cities have a different priority.

There are lamps in every field of $n\times n$ table. At start all the lamps are off. A move consists of chosing $m$ consecutive fields in a row or a column and changing the status of that $m$ lamps. Prove that you can reach a state in which all the lamps are on only if $m$ divides $n.$

Each positive integer is coloured red or blue. A function $f$ from the set of positive integers to itself has the following two properties: (a) if $x\le y$, then $f(x)\le f(y)$; and (b) if $x,y$ and $z$ are (not necessarily distinct) positive integers of the same colour and $x+y=z$, then $f(x)+f(y)=f(z)$. Prove that there exists a positive number $a$ such that $f(x)\le ax$ for all positive integers $x$. [i](United Kingdom) Ben Elliott[/i]

Each two-digit is number is coloured in one of $k$ colours. What is the minimum value of $k$ such that, regardless of the colouring, there are three numbers $a$, $b$ and $c$ with different colours with $a$ and $b$ having the same units digit (second digit) and $b$ and $c$ having the same tens digit (first digit)?

On a table, there are $10\,000$ matches, two of which are inside a box. Ana and Beto take turns playing the following game. On each turn, a player adds to the box a number of matches equal to a proper divisor of the current number of matches in the box. The game ends when, for the first time, there are more than $2024$ matches in the box and the person who played the last turn is the winner. If Ana starts the game, determine who has a winning strategy.

In the mathematical talent show called “The $X^2$-factor” contestants are scored by a a panel of $8$ judges. Each judge awards a score of $0$ (‘fail’), $X$ (‘pass’), or $X^2$ (‘pass with distinction’). Three of the contestants were Ann, Barbara and David. Ann was awarded the same score as Barbara by exactly $4$ of the judges. David declares that he obtained different scores to Ann from at least $4$ of the judges, and also that he obtained different scores to Barbara from at least $4$ judges. In how many ways could scores have been allocated to David, assuming he is telling the truth?