There are at least $3$ subway stations in a city. In this city, there exists a route that passes through more than $L$ subway stations, without revisiting. Subways run both ways, which means that if you can go from subway station A to B, you can also go from B to A. Prove that at least one of the two holds. $\text{(i)}$. There exists three subway stations $A$, $B$, $C$ such that there does not exist a route from $A$ to $B$ which doesn't pass through $C$. $\text{(ii)}$. There is a cycle passing through at least $\lfloor \sqrt{2L} \rfloor$ stations, without revisiting a same station more than once.

A numerist has $n$ eurodollars and distributes them to two bank accounts $A, B$ in Germany and Switzerland, whereby the Eurodollars cannot be split into smaller monetary units due to the lack of a suitable name. In order to hide all money from the tax authorities if necessary, he would like to be able to move all of his money to account $B$. Due to the immense bureaucracy, money is only allowed to be moved between two accounts if the deposited amount in one account is double. Of course, he can carry out several such transfers in a row. Show that the number of ways to initially distribute the money appropriately is a power of two.

Given a square $100\times 100$ on the sheet of cross-lined paper. There are several broken lines drawn inside the square. Their links consist of the small squares sides. They are neither pairwise- nor self-intersecting (have no common points). Their ends are on the big square boarder, and all the other vertices are in the big square interior. Prove that there exists (in addition to four big square angles) a node (corresponding to the cross-lining family, inside the big square or on its side) that does not belong to any broken line.

Let $a$ and $b$ be positive integers, and let $A$ and $B$ be finite sets of integers satisfying (i) $A$ and $B$ are disjoint; (ii) if an integer $i$ belongs to either to $A$ or to $B$, then either $i+a$ belongs to $A$ or $i-b$ belongs to $B$. Prove that $a\left\lvert A \right\rvert = b \left\lvert B \right\rvert$. (Here $\left\lvert X \right\rvert$ denotes the number of elements in the set $X$.)

You are given $n$ squares, not necessarily all of the same size, which have total area 1. Is it always possible to place them without overlapping in a square of area 2?

Let's consider words over the alphabet $\{a,b\}$ to be sequences of $a$ and $b$ with finite length. We say $u \leq v$ if $u$ is a subword of $v$ if we can get $u$ erasing some letter of $v$ (for example $aba \leq abbab$). We say that $u$ differentiates the words $x$ and $y$ if $u \leq x$ but $u \not\leq y$ or vice versa. Let $m$ and $l$ be positive integers. We say that two words are $m-$equivalents if there does not exist some $u$ with length smaller than $m$ that differentiates $x$ and $y$. a) Show that, if $2m \leq l$, there exists two distinct words with length $l$ \ $m-$equivalents. b) Show that, if $2m > l$, any two distinct words with length $l$ aren't $m-$equivalent.

A $50$-card deck consists of $4$ cards labeled " i" for $i = 1, 2,..., 12$ and $2$ cards labeled "$13$". If Bob randomly chooses $2$ cards from the deck without replacement, what is the probability that his $2$ cards have the same label?

Prove that in a finite group G the number of subgroups with index n is at most $| G |^{2 \log_2 n}$.

In a $2\times n$ array we have positive reals s.t. the sum of the numbers in each of the $n$ columns is $1$. Show that we can select a number in each column s.t. the sum of the selected numbers in each row is at most $\frac{n+1}4$.

Two courier companies offer services in the country of Old Aland. For any two towns, at least one of the companies offers a direct link in both directions between them. Additionally, each company is willing to chain together deliveries (so if they offer a direct link from $A$ to $B$, and $B$ to $C$, and $C$ to $D$ for instance, they will deliver from $A$ to $D$.) Show that at least one of the two companies must be able to deliver packages between any two towns in Old Aland.

Let $n$ be an odd integer. Consider a square lattice of size $n \times n$, consisting of $n^2$ unit squares and $2n(n +1)$ edges. All edges are painted in red or blue so that the number of red edges does not exceed $n^2$. Prove that there is a cell that has at least three blue edges.

There are $2020$ groups, each of which consists of a boy and a girl, such that each student is contained in exactly one group. Suppose that the students shook hands so that the following conditions are satisfied: [list] [*] boys didn't shake hands with boys, and girls didn't shake hands with girls; [*] in each group, the boy and girl had shake hands exactly once; [*] any boy and girl, each in different groups, didn't shake hands more than once; [*] for every four students in two different groups, there are at least three handshakes. [/list] Prove that one can pick $4038$ students and arrange them at a circular table so that every two adjacent students had shake hands.

Yor and Fiona are playing a match of tennis against each other. The first player to win $6$ games wins the match (while the other player loses the match). Yor has currently won $2$ games, while Fiona has currently won $0$ games. Each game is won by one of the two players: Yor has a probability of $\frac23$ to win each game, while Fiona has a probability of $\frac13$ to win each game. Then, $\frac{m}{n}$ is the probability Fiona wins the tennis match, for relatively prime integers $m,n$. Compute $m$.

The points of this lattice $4\times 4 = 16$ points can be vertices of squares. [asy] unitsize(1 cm); int i, j; for (i = 0; i <= 3; ++i) { draw((i,0)--(i,3)); draw((0,i)--(3,i)); } draw((1,1)--(2,2)--(1,3)--(0,2)--cycle); for (i = 0; i <= 3; ++i) { for (j = 0; j <= 3; ++j) { dot((i,j)); }} [/asy] Calculate the number of different squares that can be formed in a lattice of $100\times 100$ points.

There are $n$ MOPpers $p_1,...,p_n$ designing a carpool system to attend their morning class. Each $p_i$'s car fits $\chi (p_i)$ people ($\chi : \{p_1,...,p_n\} \to \{1,2,...,n\}$). A $c$-fair carpool system is an assignment of one or more drivers on each of several days, such that each MOPper drives $c$ times, and all cars are full on each day. (More precisely, it is a sequence of sets $(S_1, ...,S_m)$ such that $|\{k: p_i\in S_k\}|=c$ and $\sum_{x\in S_j} \chi(x) = n$ for all $i,j$. ) Suppose it turns out that a $2$-fair carpool system is possible but not a $1$-fair carpool system. Must $n$ be even? [i]Proposed by Nathan Ramesh and Palmer Mebane

Let $X$ and $Y$ be two finite subsets of the half-open interval $[0, 1)$ such that $0 \in X \cap Y$ and $x + y = 1$ for no $x \in X$ and no $y \in Y$. Prove that the set $\{x + y - \lfloor x + y \rfloor : x \in X \textrm{ and } y \in Y\}$ has at least $|X| + |Y| - 1$ elements. [i]***[/i]

Maria has a board of size $n \times n$, initially with all the houses painted white. Maria decides to paint black some houses on the board, forming a mosaic, as shown in the figure below, as follows: she paints black all the houses from the edge of the board, and then leaves white the houses that have not yet been painted. Then she paints the houses on the edge of the next remaining board again black, and so on. a) Determine a value of $n$ so that the number of black houses equals $200$. b) Determine the smallest value of $n$ so that the number of black houses is greater than $2012$.

100 people from 50 countries, two from each countries, stay on a circle. Prove that one may partition them onto 2 groups in such way that neither no two countrymen, nor three consecutive people on a circle, are in the same group.

Natural numbers from $1$ to $200$ were divided into $50$ sets. Prove that one of them contains three numbers that are the lengths of the sides of some triangle

Random sequences $a_1, a_2, . . .$ and $b_1, b_2, . . .$ are chosen so that every element in each sequence is chosen independently and uniformly from the set $\{0, 1, 2, 3, . . . , 100\}$. Compute the expected value of the smallest nonnegative integer $s$ such that there exist positive integers $m$ and $n$ with $$s =\sum^m_{i=1} a_i =\sum^n_{j=1}b_j .$$

For all positive integers $n$, let $p(n)$ be the number of non-decreasing sequences of positive integers such that for each sequence, the sum of all terms of the sequence is equal to $n$. Prove that \[\dfrac{1+p(1)+p(2) + \dots + p(n-1)}{p(n)} \leq \sqrt {2n}.\]

[b]p1.[/b] A matrix is a rectangular array of numbers. For example, $\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$ and $\begin{pmatrix} 1 & 3 \\ 2 & 4 \end{pmatrix}$ are $2 \times 2$ matrices. A [i]saddle [/i] point in a matrix is an entry which is simultaneously the smallest number in its row and the largest number in its column. a. Write down a $2 \times 2$ matrix which has a saddle point, and indicate which entry is the saddle point. b. Write down a $2 \times 2$ matrix which has no saddle point c. Prove that a matrix of any size, all of whose entries are distinct, can have at most one saddle point. [b]p2.[/b] a. Find four different pairs of positive integers satisfying the equation $\frac{7}{m}+\frac{11}{n}=1$. b. Prove that the solutions you have found in part (a) are all possible pairs of positive integers satisfying the equation $\frac{7}{m}+\frac{11}{n}=1$. [b]p3.[/b] Let $ABCD$ be a quadrilateral, and let points $M, N, O, P$ be the respective midpoints of sides $AB$, $BC$, $CD$, $DA$. a. Show, by example, that it is possible that $ABCD$ is not a parallelogram, but $MNOP$ is a square. Be sure to prove that your construction satisfies all given conditions. b. Suppose that $MO$ is perpendicular to $NP$. Prove that $AC = BD$. [b]p4.[/b] A [i]Pythagorean triple[/i] is an ordered collection of three positive integers $(a, b, c)$ satisfying the relation $a^2 + b^2 = c^2$. We say that $(a, b, c)$ is a [i]primitive [/i] Pythagorean triple if $1$ is the only common factor of $a, b$, and $c$. a. Decide, with proof, if there are infinitely many Pythagorean triples. b. Decide, with proof, if there are infinitely many primitive Pythagorean triples of the form $(a, b, c)$ where $c = b + 2$. c. Decide, with proof, if there are infinitely many primitive Pythagorean triples of the form $(a, b, c)$ where $c = b + 3$. [b]p5.[/b] Let $x$ and $y$ be positive real numbers and let $s$ be the smallest among the numbers $\frac{3x}{2}$,$\frac{y}{x}+\frac{1}{x}$ and $\frac{3}{y}$. a. Find an example giving $s > 1$. b. Prove that for any positive $x$ and $y,s <2$. c. Find, with proof, the largest possible value of $s$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Find all sets of six points in the plane, no three collinear, such that if we partition the set into two sets, then the obtained triangles are congruent.

Let $\leftarrow$ denote the left arrow key on a standard keyboard. If one opens a text editor and types the keys "ab$\leftarrow$ cd $\leftarrow \leftarrow$ e $\leftarrow \leftarrow$ f", the result is "faecdb". We say that a string $B$ is [i]reachable[/i] from a string $A$ if it is possible to insert some amount of $\leftarrow$'s in $A$, such that typing the resulting characters produces $B$. So, our example shows that "faecdb" is reachable from "abcdef". Prove that for any two strings $A$ and $B$, $A$ is reachable from $B$ if and only if $B$ is reachable from $A$.

[b]p1.[/b] Compute the sum of sharp angles at all five nodes of the star below. ( [url=http://www.math.msu.edu/~mshapiro/NewOlympiad/Olymp2009/10_12_2009.pdf]figure missing[/url] ) [b]p2.[/b] Arrange the integers from $1$ to $15$ in a row so that the sum of any two consecutive numbers is a perfect square. In how many ways this can be done? [b]p3.[/b] Prove that if $p$ and $q$ are prime numbers which are greater than $3$ then $p^2 -q^2$ is divisible by $ 24$. [b]p4.[/b] A city in a country is called Large Northern if comparing to any other city of the country it is either larger or farther to the North (or both). Similarly, a city is called Small Southern. We know that in the country all cities are Large Northern city. Show that all the cities in this country are simultaneously Small Southern. [b]p5.[/b] You have four tall and thin glasses of cylindrical form. Place on the flat table these four glasses in such a way that all distances between any pair of centers of the glasses' bottoms are equal. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].