A collection of $2n$ letters contains $2$ each of $n$ different letters. The collection is partitioned into $n$ pairs, each pair containing $2$ letters, which may be the same or different. Denote the number of distinct partitions by $u_n$. (Partitions differing in the order of the pairs in the partition or in the order of the two letters in the pairs are not considered distinct.) Prove that $u_{n+1}=(n+1)u_n - \frac{n(n-1)}{2} u_{n-2}.$ [i]Similar Problem :[/i] A pack of $2n$ cards contains $n$ pairs of $2$ identical cards. It is shuffled and $2$ cards are dealt to each of $n$ different players. Let $p_n$ be the probability that every one of the $n$ players is dealt two identical cards. Prove that $\frac{1}{p_{n+1}}=\frac{n+1}{p_n} + \frac{n(n-1)}{2p_{n-2}}.$

[b]p1.[/b] Two proper ordinary fractions are given. The first has a numerator that is $5$ less than the denominator, and the second has a numerator that is $1998$ less than the denominator. Can their sum have a numerator greater than its denominator? [b]p2.[/b] On New Year's Eve, geraniums, crocuses and cacti stood in a row (from left to right) on the windowsill. Every morning, Masha, wiping off the dust, swaps the places of the flower on the right and the flower in the center. During the day, Tanya, while watering flowers, swaps places between the one in the center and the one on the left. In what order will the flowers be in $365$ days on the next New Year's Eve? [b]p3.[/b] The number $x$ is such that $15\%$ of it and $33\%$ of it are positive integers. What is the smallest number $x$ (not necessarily an integer!) with this property? [b]p4.[/b] In the quadrilateral $ABCD$, the extensions of opposite sides $AB$ and $CD$ intersect at an angle of $20^o$; the extensions of opposite sides $BC$ and $AD$ also intersect at an angle of $20^o$. Prove that two angles in this quadrilateral are equal and the other two differ by $40^o$. [b]p5.[/b] Given two positive integers $a$ and $b$. Prove that $a^ab^b\ge a^ab^a.$ [b]p6.[/b] The square is divided by straight lines into $25$ rectangles (fig.). The areas of some of They are indicated in the figure (not to scale). Find the area of the rectangle marked with a question mark. [img]https://cdn.artofproblemsolving.com/attachments/0/9/591c93421067123d50382744f9d28357acf83a.png[/img] [b]p7.[/b] A radio-controlled toy leaves a certain point. It moves in a straight line, and on command can turn left exactly $ 17^o$ (relative to the previous direction of movement). What is the smallest number of commands required for the toy to pass through the starting point again? [b]p8.[/b] In expression $$(a-b+c)(d+e+f)(g-h-k)(\ell +m- n)(p + q)$$ opened the brackets. How many members will there be? How many of them will be preceded by a minus sign? [b]p9.[/b] In some countries they decided to hold popular elections of the government. Two-thirds of voters in this country are urban and one-third are rural. The President must propose for approval a draft government of $100$ people. It is known that the same percentage of urban (rural) residents will vote for the project as there are people from the city (rural) in the proposed project. What is the smallest number of city residents that must be included in the draft government so that more than half of the voters vote for it? [b]p10.[/b] Vasya and Petya play such a game on a $10 \times 10 board$. Vasya has many squares the size of one cell, Petya has many corners of three cells (fig.). They are walking one by one - first Vasya puts his square on the board, then Petya puts his corner, then Vasya puts another square, etc. (You cannot place pieces on top of others.) The one who cannot make the next move loses. Vasya claims that he can always win, no matter how hard Petya tries. Is Vasya right? [img]https://cdn.artofproblemsolving.com/attachments/f/1/3ddec7826ff6eb92471855322e3b9f01357116.png[/img] PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c2416727_soros_olympiad_in_mathematics]here.[/url]

In the Duma there are 1600 delegates, who have formed 16000 committees of 80 persons each. Prove that one can find two committees having no fewer than four common members. [i]A. Skopenkov[/i]

Is it possible to write positive integers from $1$ to $2025$ in the cells of a \( 45 \times 45 \) grid such that each number is used exactly once, and at the same time, each written number is either greater than all the numbers located in its side-adjacent cells or smaller than all the numbers located in its side-adjacent cells? [i]Proposed by Anton Trygub[/i]

In a regular polygon with $134$ sides, $67$ diagonals are drawn so that exactly one diagonal emerges from each vertex. We call the [i]length[/i] of a diagonal the number of sides of the polygon included between the vertices of the diagonal and which is less than or equal to $67$. If we order the [i]lengths [/i] of the diagonals in ascending order, we obtain a succession of $67$ numbers $(d_1,d_2,...,d_{67})$. It will be possible to draw diagonals such that a) $(d_1,d_2,...,d_{67})=\underbrace{2 ... 2}_{6},\underbrace{3 ... 3}_{61}$ ? b) $(d_1,d_2,...,d_{67}) =\underbrace{3 ... 3}_{8},\underbrace{6 ... 6}_{55}.\underbrace{8 ... 8}_{4} $ ?

A container contains five red balls. On each turn, one of the balls is selected at random, painted blue, and returned to the container. The expected number of turns it will take before all five balls are colored blue is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

The entries of a $7 \times 5$ table are filled with numbers so that in each $2 \times 3$ rectangle (vertical or horizontal) the sum of numbers is $0$. For $100$ dollars Peter may choose any single entry and learn the number in it. What is the least amount of dollars he should spend in order to learn the total sum of numbers in the table for sure?

On a $999\times 999$ board a [i]limp rook[/i] can move in the following way: From any square it can move to any of its adjacent squares, i.e. a square having a common side with it, and every move must be a turn, i.e. the directions of any two consecutive moves must be perpendicular. A [i]non-intersecting route[/i] of the limp rook consists of a sequence of pairwise different squares that the limp rook can visit in that order by an admissible sequence of moves. Such a non-intersecting route is called [i]cyclic[/i], if the limp rook can, after reaching the last square of the route, move directly to the first square of the route and start over. How many squares does the longest possible cyclic, non-intersecting route of a limp rook visit? [i]Proposed by Nikolay Beluhov, Bulgaria[/i]

Several positive integers are written in a row. Iteratively, Alice chooses two adjacent numbers $x$ and $y$ such that $x>y$ and $x$ is to the left of $y$, and replaces the pair $(x,y)$ by either $(y+1,x)$ or $(x-1,x)$. Prove that she can perform only finitely many such iterations. [i]Proposed by Warut Suksompong, Thailand[/i]

Suppose $A_1,A_2,\cdots ,A_n \subseteq \left \{ 1,2,\cdots ,2018 \right \}$ and $\left | A_i \right |=2, i=1,2,\cdots ,n$, satisfying that $$A_i + A_j, \; 1 \le i \le j \le n ,$$ are distinct from each other. $A + B = \left \{ a+b|a\in A,\,b\in B \right \}$. Determine the maximal value of $n$.

The positive integers $1,2,...,121$ are arranged in the squares of a $11 \times 11$ table. Dima found the product of numbers in each row and Sasha found the product of the numbers in each column. Could they get the same set of $11$ numbers? [i]Proposed by S. Berlov[/i]

One hundred friends, including Alice and Bob, live in several cities. Alice has determined the distance from her city to the city of each of the other 99 friends and totaled these 99 numbers. Alice’s total is 1000 km. Bob similarly totaled his distances to everyone else. What is the largest total that Bob could have obtained? (Consider the cities as points on the plane; if two people live in the same city, the distance between their cities is considered zero).

A pair of words consisting only of the letters $a$ and $b$ (with repetitions) is [i]good[/i] if it is $(a,b)$ or of one of the forms $(uv, v)$, $(u, uv)$, where $(u,v)$ is a good pair. Prove that if $(\alpha, \beta)$ is a good pair, then there exists a palindrome $\gamma$ such that $\alpha\beta = a\gamma b$.

There are $2^n$ words of length $n$ over the alphabet $\{0, 1\}$. Prove that the following algorithm generates the sequence $w_0, w_1, \ldots, w_{2^n-1}$ of all these words such that any two consecutive words differ in exactly one digit. (1) $w_0 = 00 \ldots 0$ ($n$ zeros). (2) Suppose $w_{m-1} = a_1a_2 \ldots a_n,\quad a_i \in \{0, 1\}$. Let $e(m)$ be the exponent of $2$ in the representation of $n$ as a product of primes, and let $j = 1 + e(m)$. Replace the digit $a_j$ in the word $w_{m-1}$ by $1 - a_j$. The obtained word is $w_m$.

At a given plane with $2,000$ lines, all those with an odd number of different points of intersection with intersecting lines. a) Can there be an odd number of red lines if in the plane given there are no parallel lines? b) Can there be an odd number of red lines if none of any 3 given lines intersect at one point?

Given a regular $72$-gon. Lenya and Kostya play the game "Make an equilateral triangle." They take turns marking with a pencil on one still unmarked angle of the $72$-gon: Lenya uses red. Kostya uses blue. Lenya starts the game, and the one who marks first wins if its color is three vertices that are the vertices of some equilateral triangle, if all the vertices are marked and no such a triangle exists, the game ends in a draw. Prove that Kostya can play like this so as not to lose.

Students are in classroom with $n$ rows. In each row there are $m$ tables. It's given that $m,n \geq 3$. At each table there is exactly one student. We call neighbours of the student students sitting one place right, left to him, in front of him and behind him. Each student shook hands with his neighbours. In the end there were $252$ handshakes. How many students were in the classroom?

Three of the $16$ squares from a $4 \times 4$ grid of squares are selected at random. The probability that at least one corner square of the grid is selected is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$. $ \begin{tabular}{ | l | c | c | r| } \hline & & & \\ \hline & & & \\ \hline & & & \\ \hline & & & \\ \hline \end{tabular} $

a) In how many ways can we read the word SARAJEVO from the table below, if it is allowed to jump from cell to an adjacent cell (by vertex or a side) cell? b) After the letter in one cell was deleted, only $525$ ways to read the word SARAJEVO remained. Find all possible positions of that cell.

Different points $A_1, A_2,..., A_n$ in the plane ($n> 3$) are such that the triangle $A_iA_jA_k$ is obtuse for all the different $i,j,k \in\{1,2,...,n\}$. Prove that there is a point $A_{n + 1}$ in the plane, such that the triangle $A_iA_jA_{n + 1}$ is obtuse for all different $i,j \in\{1,2,...,n\}$

Given a set $X=\{x_1,\ldots,x_n\}$ of natural numbers in which for all $1< i \leq n$ we have $1\leq x_i-x_{i-1}\leq 2$, call a real number $a$ [b]good[/b] if there exists $1\leq j \leq n$ such that $2|x_j-a|\leq 1$. Also a subset of $X$ is called [b]compact[/b] if the average of its elements is a good number. Prove that at least $2^{n-3}$ subsets of $X$ are compact. [i]Proposed by Mahyar Sefidgaran[/i]

Vaggelis has a box that contains $2015$ white and $2015$ black balls. In every step, he follows the procedure below: He choses randomly two balls from the box. If they are both blacks, he paints one white and he keeps it in the box, and throw the other one out of the box. If they are both white, he keeps one in the box and throws the other out. If they are one white and one black, he throws the white out, and keeps the black in the box. He continues this procedure, until three balls remain in the box. He then looks inside and he sees that there are balls of both colors. How many white balls does he see then, and how many black?

Let $ n$ and $ k$ be positive integers such that $ \frac{1}{2} n < k \leq \frac{2}{3} n.$ Find the least number $ m$ for which it is possible to place $ m$ pawns on $ m$ squares of an $ n \times n$ chessboard so that no column or row contains a block of $ k$ adjacent unoccupied squares.

Daan distributes the numbers $1$ to $9$ over the nine squares of a $3\times 3$-table (each square receives exactly one number). Then, in each row, Daan circles the median number (the number that is neither the smallest nor the largest of the three). For example, if the numbers $8, 1$, and $2$ are in one row, he circles the number $2$. He does the same for each column and each of the two diagonals. If a number is already circled, he does not circle it again. He calls the result of this process a [i]median table[/i]. Above, you can see a median table that has $5$ circled numbers. (a) What is the [b]smallest [/b] possible number of circled numbers in a median table? [i] Prove that a smaller number is not possible and give an example in which a minimum number of numbers is circled.[/i] (b) What is the [b]largest [/b] possible number of circled numbers in a median table? [i]Prove that a larger number is not possible and give an example in which a maximum number of numbers is circled.[/i] [asy] unitsize (0.8 cm); int i; for (i = 0; i <= 3; ++i) { draw((0,i)--(3,i)); draw((i,0)--(i,3)); } draw(Circle((0.5,2.5),0.3)); draw(Circle((2.5,2.5),0.3)); draw(Circle((1.5,1.5),0.3)); draw(Circle((2.5,1.5),0.3)); draw(Circle((1.5,0.5),0.3)); label("$8$", (0.5,2.5)); label("$1$", (1.5,2.5)); label("$2$", (2.5,2.5)); label("$7$", (0.5,1.5)); label("$6$", (1.5,1.5)); label("$3$", (2.5,1.5)); label("$9$", (0.5,0.5)); label("$5$", (1.5,0.5)); label("$4$", (2.5,0.5)); [/asy]

The company has $100$ people. For any $k$, we can find a group of $k$ people such that there are two (different from them) strangers, each of them knows all of these $k$ people. At what maximum $k$ is this possible?