On a circle $4n$ points are chosen ($n \ge 1$). The points are alternately colored yellow and blue. The yellow points are divided into $n$ pairs and the points in each pair are connected with a yellow line segment. In the same manner the blue points are divided into $n$ pairs and the points in each pair are connected with a blue segment. Assume that no three of the segments pass through a single point. Show that there are at least $n$ intersection points of blue and yellow segments.

[b]p1.[/b] Warren interrogates the $25$ members of his cabinet, each of whom always lies or always tells the truth. He asks them all, “How many of you always lie?” He receives every integer answer from $1$ to $25$ exactly once. Find the actual number of liars in his cabinet. [b]p2.[/b] Abraham thinks of distinct nonzero digits $E$, $M$, and $C$ such that $E +M = \overline{CC}$. Help him evaluate the sum of the two digit numbers $\overline{EC}$ and $\overline{MC}$. (Note that $\overline{CC}$, $\overline{EC}$, and $\overline{MC}$ are read as two-digit numbers.) [b]p3.[/b] Let $\omega$, $\Omega$, $\Gamma$ be concentric circles such that $\Gamma$ is inside $\Omega$ and $\Omega$ is inside $\omega$. Points $A,B,C$ on $\omega$ and $D,E$ on $\Omega$ are chosen such that line $AB$ is tangent to $\Omega$, line $AC$ is tangent to $\Gamma$, and line $DE$ is tangent to $\Gamma$. If $AB = 21$ and $AC = 29$, find $DE$. [b]p4.[/b] Let $a$, $b$, and $c$ be three prime numbers such that $a + b = c$. If the average of two of the three primes is four less than four times the fourth power of the last, find the second-largest of the three primes. [b]p5.[/b] At Stillwells Ice Cream, customers must choose one type of scoop and two different types of toppings. There are currently $630$ different combinations a customer could order. If another topping is added to the menu, there would be $840$ different combinations. If, instead, another type of scoop were added to the menu, compute the number of different combinations there would be. [b]p6.[/b] Eleanor the ant takes a path from $(0, 0)$ to $(20, 24)$, traveling either one unit right or one unit up each second. She records every lattice point she passes through, including the starting and ending point. If the sum of all the $x$-coordinates she records is $271$, compute the sum of all the $y$-coordinates. (A lattice point is a point with integer coordinates.) [b]p7.[/b] Teddy owns a square patch of desert. He builds a dam in a straight line across the square, splitting the square into two trapezoids. The perimeters of the trapezoids are$ 64$ miles and $76$ miles, and their areas differ by $135$ square miles. Find, in miles, the length of the segment that divides them. [b]p8.[/b] Michelle is playing Spot-It with a magical deck of $10$ cards. Each card has $10$ distinct symbols on it, and every pair of cards shares exactly $1$ symbol. Find the minimum number of distinct symbols on all of the cards in total. [b]p9.[/b] Define the function $f(n) = \frac{1}{2^n} + \frac{1}{3^n} + \frac{1}{4^n} + ...$ for integers $n \ge 2$. Find $$f(2) + f(4) + f(6) + ... .$$ [b]p10.[/b] There are $9$ indistinguishable ants standing on a $3\times 3$ square grid. Each ant is standing on exactly one square. Compute the number of different ways the ants can stand so that no column or row contains more than $3$ ants. [b]p11.[/b] Let $s(N)$ denote the sum of the digits of $N$. Compute the sum of all two-digit positive integers $N$ for which $s(N^2) = s(N)^2$. [b]p12.[/b] Martha has two square sheets of paper, $A$ and $B$. With each sheet, she repeats the following process four times: fold bottom side to top side, fold right side to left side. With sheet $A$, she then makes a cut from the top left corner to the bottom right. With sheet $B$, she makes a cut from the bottom left corner to the top right. Find the total number of pieces of paper yielded from sheets $A$ and sheets $B$. [img]https://cdn.artofproblemsolving.com/attachments/f/6/ff3a459a135562002aa2c95067f3f01441d626.png[/img] [b]p13.[/b] Let $x$ and $y$ be positive integers such that gcd $(x^y, y^x) = 2^{28}$. Find the sum of all possible values of min $(x, y)$. [b]p14.[/b] Convex hexagon $TRUMAN$ has opposite sides parallel. If each side has length $3$ and the area of this hexagon is $5$, compute $$TU \cdot RM \cdot UA \cdot MN \cdot AT \cdot NR.$$ [b]p15.[/b] Let $x$, $y$, and $z$ be positive real numbers satisfying the system $$\begin{cases} x^2 + xy + y^2 = 25\\ y^2 + yz + z^2 = 36 \\ z^2 + zx + x^2 = 49 \end{cases}$$ Compute $x^2 + y^2 + z^2$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $n$, $(n \geq 3)$ be a positive integer and the set $A$={$1,2,...,n$}. All the elements of $A$ are randomly arranged in a sequence $(a_1,a_2,...,a_n)$. The pair $(a_i,a_j)$ forms an $inversion$ if $1 \leq i \leq j \leq n$ and $a_i > a_j$. In how many different ways all the elements of the set $A$ can be arranged in a sequence that contains exactly $3$ inversions?

On the board is written an integer $N \geq 2$. Two players $A$ and $B$ play in turn, starting with $A$. Each player in turn replaces the existing number by the result of performing one of two operations: subtract 1 and divide by 2, provided that a positive integer is obtained. The player who reaches the number 1 wins. Determine the smallest even number $N$ requires you to play at least $2015$ times to win ($B$ shifts are not counted).

In Wonderland, the government of each country consists of exactly $a$ men and $b$ women, where $a$ and $b$ are fixed natural numbers and $b > 1$. For improving of relationships between countries, all possible working groups consisting of exactly one government member from each country, at least $n$ among whom are women, are formed (where $n$ is a fixed non-negative integer). The same person may belong to many working groups. Find all possibilities how many countries can be in Wonderland, given that the number of all working groups is prime.

Several dwarves were lined up in a row, and then they lined up in a row in a different order. Is it possible that exactly one third of the dwarves have both of their neighbours remained and exactly one third of the dwarves have only one of their neighbours remained, if the number of the dwarves is a) 6; b) 9?

There is a $19\times19$ board. Is it possible to mark some $1\times 1$ squares so that each of $10\times 10$ squares contain different number of marked squares?

Let $n \ge 3$ be a positive integer. We call a $3 \times 3$ grid [i]beautiful[/i] if the cell located at the center is colored white and all other cells are colored black, or if it is colored black and all other cells are colored white. Determine the minimum value of $a+b$ such that there exist positive integers $a$, $b$ and a coloring of an $a \times b$ grid with black and white, so that it contains $n^2 - n$ [i]beautiful[/i] subgrids.

In an exhibition where $2015$ paintings are shown, every participant picks a pair of paintings and writes it on the board. Then, Fake Artist (F.A.) chooses some of the pairs on the board, and marks one of the paintings in all of these pairs as "better". And then, Artist's Assistant (A.A.) comes and in his every move, he can mark $A$ better then $C$ in the pair $(A,C)$ on the board if for a painting $B$, $A$ is marked as better than $B$ and $B$ is marked as better than $C$ on the board. Find the minimum possible value of $k$ such that, for any pairs of paintings on the board, F.A can compare $k$ pairs of paintings making it possible for A.A to compare all of the remaining pairs of paintings. [b]P.S:[/b] A.A can decide $A_1>A_n$ if there is a sequence $ A_1 > A_2 > A_3 > \dots > A_{n-1} > A_n$ where $X>Y$ means painting $X$ is better than painting $Y$.

Dima invented a secret code in which every letter is replaced by a word no longer than $10$ letters. A code is called “good” if every encoded word can be decoded in only one way. Serjozha (with the help of a computer) checked that for Dima’s code, every possible word of at most $10000$ letters can be decoded in only one way. Does it follow that Dima’s code is good? (Note that Dima and Serjozha are Russian, so they use the Cyrillic alphabet, which has $ 33$ letters! A word is any sequence of letters.) (D Piontkovskiy, S Shalunov)

Let $x_1,\ldots,x_n$ be a sequence with each term equal to $0$ or $1$. Form a triangle as follows: its first row is $x_1,\ldots,x_n$ and if a row if $a_1, a_2, \ldots, a_m$, then the next row is $a_1 + a_2, a_2 + a_3, \ldots, a_{m-1} + a_m$ where the addition is performed modulo $2$ (so $1+1=0$). For example, starting from $1$, $0$, $1$, $0$, the second row is $1$, $1$, $1$, the third one is $0$, $0$ and the fourth one is $0$. A sequence is called good it is the same as the sequence formed by taking the last element of each row, starting from the last row (so in the above example, the sequence is $1010$ and the corresponding sequence from last terms is $0010$ and they are not equal in this case). How many possibilities are there for the sequence formed by taking the first element of each row, starting from the last row, which arise from a good sequence?

A white plane is partitioned onto cells (in a usual way). A finite number of cells are coloured black. Each black cell has an even (0, 2 or 4) adjacent (by the side) white cells. Prove that one may colour each white cell in green or red such that every black cell will have equal number of red and green adjacent cells.

Let $n$ be an integer greater than $1$. A certain school has $1+2+\dots+n$ students and $n$ classrooms, with capacities for $1, 2, \dots, n$ people, respectively. The kids play a game in $k$ rounds as follows: in each round, when the bell rings, the students distribute themselves among the classrooms in such a way that they don't exceed the room capacities, and if two students shared a classroom in a previous round, they cannot do it anymore in the current round. For each $n$, determine the greatest possible value of $k$. [i]Proposed by Victor Domínguez[/i]

In a country every two towns are connected by exactly one one-way road. Each road is intended either for cars or for cyclists. The roads cross only in towns, otherwise interchanges are used as road junctions. Show that there is a town from which you can go to any other town without changing the means of transport.

On a mathematical competition $ n$ problems were given. The final results showed that: (i) on each problem, exactly three contestants scored $ 7$ points; (ii) for each pair of problems, exactly one contestant scored $ 7$ points on both problems. Prove that if $ n \geq 8$, then there is a contestant who got $ 7$ points on each problem. Is this statement necessarily true if $ n \equal{} 7$?

Thirty two pairs of identical twins are lined up in an $8\times 8$ formation. Prove that it is possible to choose $32 $ persons, one from each pair of twins, so that there is at least one chosen person in each row and in each column

Catherine has a plate containing $300$ circular crumbling mooncakes, arranged as follows: [asy] unitsize(10); for (int i = 0; i < 16; ++i){ for (int j = 0; j < 3; ++j){ draw(circle((sqrt(3)*i,j),0.5)); draw(circle((sqrt(3)*(i+0.5),j-0.5),0.5)); } } dot((16*sqrt(3)+.5,.75)); dot((16*sqrt(3)+1,.75)); dot((16*sqrt(3)+1.5,.75)); [/asy] (This continues for $100$ total columns). She wants to pick some of the mooncakes to eat, however whenever she takes a mooncake all adjacent mooncakes will be destroyed and cannot be eaten. Let $M$ be the maximal number of mooncakes she can eat, and let $n$ be the number of ways she can pick $M$ mooncakes to eat (Note: the order in which she picks mooncakes does not matter). Compute the ordered pair ($M$, $n$).

A $100\times 100$ chessboard is cut into dominoes ($1\times 2$ rectangles). Two persons play the following game: At each turn, a player glues together two adjacent cells (which were formerly separated by a cut-edge). A player loses if, after his turn, the $100\times 100$ chessboard becomes connected, i. e. between any two cells there exists a way which doesn't intersect any cut-edge. Which player has a winning strategy - the starting player or his opponent?

Alice and Bob play a game on a connected graph with $2n$ vertices, where $n\in \mathbb{N}$ and $n>1$.. Alice and Bob have tokens named A and B respectively. They alternate their turns with Alice going first. Alice gets to decide the starting positions of A and B. Every move, the player with the turn moves their token to an adjacent vertex. Bob's goal is to catch Alice, and Alice's goal is to prevent this. Note that positions of A, B are visible to both Alice and Bob at every moment. Provided they both play optimally, what is the maximum possible number of edges in the graph if Alice is able to evade Bob indefinitely? [i]Proposed by Shashank Ingalagavi and Vighnesh Sangle[/i]

Let $n \ge 3$ be an odd integer. In a $2n \times 2n$ board, we colour $2(n-1)^2$ cells. What is the largest number of three-square corners that can surely be cut out of the uncoloured figure? [i]Proposed by G. Sharafetdinova[/i]

Let $\sigma, \tau$ be two permutations of the quantity $\{1, 2,. . . , n\}$. Prove that there is a function $f: \{1, 2,. . . , n\} \to \{-1, 1\}$ such that for any $1 \le i \le j \le n$, we have $\left|\sum_{k=i}^{j} f(\sigma (k)) \right| \le 2$ and $\left|\sum_{k=i}^{j} f(\tau (k))\right| \le 2$

In a sports meeting a total of $m$ medals were awarded over $n$ days. On the first day one medal and $\frac{1}{7}$ of the remaining medals were awarded. On the second day two medals and $\frac{1}{7}$ of the remaining medals were awarded, and so on. On the last day, the remaining $n$ medals were awarded. How many medals did the meeting last, and what was the total number of medals ?

The lines $\ell_1$ and \ell_2 are parallel. The points $A_1,A_2, ...,A_7$ are on $\ell_1$ and the points $B_1,B_2,...,B_8$ are on $\ell_2$. The points are arranged in such a way that the number of internal intersections among the line segments is maximized (example Figure). The [b]greatest number[/b] of intersection points is [img]https://cdn.artofproblemsolving.com/attachments/4/9/92153dce5a48fcba0f5175d67e0750b7980e84.png[/img] A. $580$ B. $585$ C. $588$ D. $590$ E. $593$

Fix an integer $n \ge 2$ and let $A$ be an $n\times n$ array with $n$ cells cut out so that exactly one cell is removed out of every row and every column. A [i]stick [/i] is a $1\times k$ or $k\times 1$ subarray of $A$, where $k$ is a suitable positive integer. (a) Determine the minimal number of [i]sticks [/i] $A$ can be dissected into. (b) Show that the number of ways to dissect $A$ into a minimal number of [i]sticks [/i] does not exceed $100^n$. proposed by Palmer Mebane and Nikolai Beluhov [hide=a few comments]a variation of part a, was [url=https://artofproblemsolving.com/community/c6h1389637p7743073]problem 5[/url] a variation of part b, was posted [url=https://artofproblemsolving.com/community/c6h1389663p7743264]here[/url] this post was made in order to complete the post collection of RMM Shortlist 2017[/hide]

Prove that from a set of ten distinct two-digit numbers, it is always possible to find two disjoint subsets whose members have the same sum.