A building has some rooms and there is one or more than one doors between the rooms. We know that we can go from each room to another one. Two rooms $E,S$ has been labeled, and the room $S$ has exactly one door. Someone is in the room $S$ and wants to move to the room $E$. [list][list][list][list][list][list][img]http://s1.picofile.com/file/6475095570/image005.jpg[/img][/list][/list][/list][/list][/list][/list] A "[i]way[/i]" $P$ for moving between the rooms is an infinite sequence of $L$ and $R$. We say that someone moves according to the "[i]way[/i]" $P$, if he start moving from the room $S$, and after passing the $n$'th door, if $P_n$ is $R$, then he goes to the first door which is in the right side, and if $P_n$ is $L$, then he goes to the first door which is in the left side (obviously, if some room has exactly one door, then there is no difference between $L$ and $R$), and when he arrives to the room $E$, he stops moving. Prove that there exists a "[i]way[/i]" such that if the person move according to it, then he can arrive to the room $E$ of any building.

[b]p1.[/b] Let $2^k$ be the largest power of $2$ dividing $30! = 30 \cdot 29 \cdot 28 ... 2 \cdot 1$. Find $k$. [b]p2.[/b] Let $d(n)$ be the total number of digits needed to write all the numbers from $1$ to $n$ in base $10$, for example, $d(5) = 5$ and $d(20) = 31$. Find $d(2012)$. [b]p3.[/b] Jim and TongTong play a game. Jim flips $10$ coins and TongTong flips $11$ coins, whoever gets the most heads wins. If they get the same number of heads, there is a tie. What is the probability that TongTong wins? [b]p4.[/b] There are a certain number of potatoes in a pile. When separated into mounds of three, two remain. When divided into mounds of four, three remain. When divided into mounds of five, one remain. It is clear there are at least $150$ potatoes in the pile. What is the least number of potatoes there can be in the pile? [b]p5.[/b] Call an ordered triple of sets $(A, B, C)$ nice if $|A \cap B| = |B \cap C| = |C \cap A| = 2$ and $|A \cap B \cap C| = 0$. How many ordered triples of subsets of $\{1, 2, · · · , 9\}$ are nice? [b]p6.[/b] Brett has an $ n \times n \times n$ cube (where $n$ is an integer) which he dips into blue paint. He then cuts the cube into a bunch of $ 1 \times 1 \times 1$ cubes, and notices that the number of un-painted cubes (which is positive) evenly divides the number of painted cubes. What is the largest possible side length of Brett’s original cube? Note that $\lfloor x\rfloor$ denotes the largest integer less than or equal to $x$. [b]p7.[/b] Choose two real numbers $x$ and $y$ uniformly at random from the interval $[0, 1]$. What is the probability that $x$ is closer to $1/4$ than $y$ is to $1/2$? [b]p8. [/b] In triangle $ABC$, we have $\angle BAC = 20^o$ and $AB = AC$. $D$ is a point on segment $AB$ such that $AD = BC$. What is $\angle ADC$, in degree. [b]p9.[/b] Let $a, b, c, d$ be real numbers such that $ab + c + d = 2012$, $bc + d + a = 2010$, $cd + a + b = 2013$, $da + b + c = 2009$. Find $d$. [b]p10. [/b]Let $\theta \in [0, 2\pi)$ such that $\cos \theta = 2/3$. Find $\sum_{n=0}^{\infty}\frac{1}{2^n}\cos(n \theta)$ PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

For any positive integer $n$, let $f(n)$ be the number of subsets of $\{1, 2, . . . , n\}$ whose sum is equal to $n$. Does there exist infinitely many positive integers $m$ such that $f(m) = f(m + 1)$? (Note that each element in a subset must be distinct.)

A $3 \times 3$ grid of unit cells is given. A [i]snake of length $k$[/i] is an animal which occupies an ordered $k$-tuple of cells in this grid, say $(s_1, \dots, s_k)$. These cells must be pairwise distinct, and $s_i$ and $s_{i+1}$ must share a side for $i = 1, \dots, k-1$. After being placed in a finite $n \times n$ grid, if the snake is currently occupying $(s_1, \dots, s_k)$ and $s$ is an unoccupied cell sharing a side with $s_1$, the snake can [i]move[/i] to occupy $(s, s_1, \dots, s_{k-1})$ instead. The snake has [i]turned around[/i] if it occupied $(s_1, s_2, \dots, s_k)$ at the beginning, but after a finite number of moves occupies $(s_k, s_{k-1}, \dots, s_1)$ instead. Find the largest integer $k$ such that one can place some snake of length $k$ in a $3 \times 3$ grid which can turn around.

Let $p,q \in \mathbb N^{\ast}$, $p,q \geq 2$. We say that a set $X$ has the property $\left( \mathcal S \right)$ if no matter how we choose $p$ subsets $B_i \subset X$, $i = \overline{1,n}$, not necessarily distinct, each with $q$ elements, there is a subset $Y \subset X$ with $p$ elements s.t. the intersection of $Y$ with each of the $B_i$'s has an element at most, $i=\overline{1,p}$. Prove that: (a) if $p=4,q=3$ then any set composed of $9$ elements doesn't have $\left( \mathcal S \right)$; (b) any set $X$ composed of $pq-q$ elements doesn't have the property $\left( \mathcal S \right)$; (c) any set $X$ composed of $pq-q+1$ elements has the property $\left( \mathcal S \right)$. [i]Dan Schwarz[/i]

Consider the infinite grid of lattice points in $\mathbb{Z}^3$. Little D and Big Z play a game, where Little D first loses a shoe on an unmunched point in the grid. Then, Big Z munches a shoe-free plane perpendicular to one of the coordinate axes. They continue to alternate turns in this fashion, with Little D's goal to lose a shoe on each of $n$ consecutive lattice points on a line parallel to one of the coordinate axes. Determine all $n$ for which Little D can accomplish his goal. [i]David Yang.[/i]

We are numbering the rows and columns of a $29 \text{x} 29$ chess table with numbers $1, 2, ..., 29$ in order (Top row is numbered with $1$ and first columns is numbered with $1$ as well). We choose some of the squares in this chess table and for every selected square, we know that there exist at most one square having a row number greater than or equal to this selected square's row number and a column number greater than or equal to this selected square's column number. How many squares can we choose at most?

Let $n \ge 2$ be an integer. There are $n$ beads numbered $1, 2, \ldots, n$. Two necklaces made out of some of these beads are considered the same if we can get one by rotating the other (with no flipping allowed). For example, with $n \ge 5$, the necklace with four beads $1, 5, 3, 2$ in the clockwise order is same as the one with $5, 3, 2, 1$ in the clockwise order, but is different from the one with $1, 2, 3, 5$ in the clockwise order. We denote by $D_0(n)$ (respectively $D_1(n)$) the number of ways in which we can use all the beads to make an even number (resp. an odd number) of necklaces each of length at least $3$. Prove that $n - 1$ divides $D_1(n) - D_0(n)$.

In a tournament, every two of the $n$ players played exactly one match with each other (no draws). Prove that it is possible either (i) to partition the league in two groups $A$ and $B$ such that everybody in $A$ defeated everybody in $B$; or (ii) to arrange all the players in a chain $x_1, x_2, . . . , x_n, x_1$ in such a way that each player defeated his successor.

There are $2000$ cities in the country, some pairs of cities are connected by roads. It is known that no more than $N$ different non-self-intersecting cyclic routes of odd length. Prove that the country can be divided into $2N +2$ republics so that no two cities from the same republic are connected by a road.

There are $n$ coins in a row. Two players take turns picking a coin and flipping it. The location of the heads and tails should not repeat. Loses the one who can not make a move. Which of player can always win, no matter how his opponent plays?

Write the number $1000$ as the sum of at least two consecutive positive integers. How many (different) ways are there to write it?

Find the number of partitions of the set $\{1, 2, \cdots, n\}$ into three subsets $A_1,A_2,A_3$, some of which may be empty, such that the following conditions are satisfied: $(i)$ After the elements of every subset have been put in ascending order, every two consecutive elements of any subset have different parity. $(ii)$ If $A_1,A_2,A_3$ are all nonempty, then in exactly one of them the minimal number is even . [i]Proposed by Poland.[/i]

There are $100$ points on the plane, all pairwise distances between which are different. Is there always a polyline with vertices at these points, passing through each point once, in which the link lengths increase monotonously?

* Given a regular dodecahedron. Find how many ways are there to draw a plane through it so that its section of the dodecahedron is a regular hexagon?

There are $n$ cities in a country. Between any two cities there is at most one road. Suppose that the total number of roads is $n.$ Prove that there is a city such that starting from there it is possible to come back to it without ever travelling the same road twice.

At a conference there are $n$ mathematicians. Each of them knows exactly $k$ fellow mathematicians. Find the smallest value of $k$ such that there are at least three mathematicians that are acquainted each with the other two. [color=#BF0000]Rewording of the last line for clarification:[/color] Find the smallest value of $k$ such that there (always) exists $3$ mathematicians $X,Y,Z$ such that $X$ and $Y$ know each other, $X$ and $Z$ know each other and $Y$ and $Z$ know each other.

Elmo and Elmo's clone are playing a game. Initially, $n\geq 3$ points are given on a circle. On a player's turn, that player must draw a triangle using three unused points as vertices, without creating any crossing edges. The first player who cannot move loses. If Elmo's clone goes first and players alternate turns, who wins? (Your answer may be in terms of $n$.) [i]Proposed by Milan Haiman[/i]

A chess club consists of at least $10$ and at most $50$ members, where $G$ of them are female, and $B$ of them are male with $G>B$. In a chess tournament, each member plays with any other member exactly one time. At each game, the winner gains $1$, the loser gains $0$ and both player gains $1/2$ point when a tie occurs. At the tournament, it is observed that each member gained exactly half of his/her points from the games played against male members. How many different values can $B$ take? $ \textbf{(A)}\ 5 \qquad\textbf{(B)}\ 4 \qquad\textbf{(C)}\ 3 \qquad\textbf{(D)}\ 2 \qquad\textbf{(E)}\ 1 $

There are $2n$ points on a circle, $n$ are red and $n$ are blue. Janson found a red frog and a blue frog at a red point and a blue point on the circle respectively. Every minute, the red frog moves to the next red point in the clockwise direction and the blue frog moves to the next blue point in the anticlockwise direction. Prove that for any initial position of the two frogs, Janson can draw a line through the circle, such that the two frogs are always on opposite sides of the line.

There is a board with $2020$ squares in the bottom row and $2019$ in the top row, located as shown shown in the figure. [img]https://cdn.artofproblemsolving.com/attachments/f/3/516ad5485c399427638c3d1783593d79d83002.png[/img] In the bottom row the integers numbers from $ 1$ to $2020$ are placed in some order. Then in each box in the top row records the multiplication of the two numbers below it. How can they place the numbers in the bottom row so that the sum of the numbers in the top row be the smallest possible?

For a positive integer $n$, there are two countries $A$ and $B$ with $n$ airports each and $n^2-2n+ 2$ airlines operating between the two countries. Each airline operates at least one flight. Exactly one flight by one of the airlines operates between each airport in $A$ and each airport in $B$, and that flight operates in both directions. Also, there are no flights between two airports in the same country. For two different airports $P$ and $Q$, denote by "[i]$(P, Q)$-travel route[/i]" the list of airports $T_0, T_1, \ldots, T_s$ satisfying the following conditions. [list] [*] $T_0=P,\ T_s=Q$ [*] $T_0, T_1, \ldots, T_s$ are all distinct. [*] There exists an airline that operates between the airports $T_i$ and $T_{i+1}$ for all $i = 0, 1, \ldots, s-1$. [/list] Prove that there exist two airports $P, Q$ such that there is no or exactly one [i]$(P, Q)$-travel route[/i]. [hide=Graph Wording]Consider a complete bipartite graph $G(A, B)$ with $\vert A \vert = \vert B \vert = n$. Suppose there are $n^2-2n+2$ colors and each edge is colored by one of these colors. Define $(P, Q)-path$ a path from $P$ to $Q$ such that all of the edges in the path are colored the same. Prove that there exist two vertices $P$ and $Q$ such that there is no or only one $(P, Q)-path$. [/hide]

Let $A$ be the largest subset of $\{1,\dots,n\}$ such that for each $x\in A$, $x$ divides at most one other element in $A$. Prove that \[\frac{2n}3\leq |A|\leq \left\lceil \frac{3n}4\right\rceil. \]

[b]p1.[/b] Find the greatest integer $n$ such that $n \log_{10} 4$ does not exceed $\log_{10} 1998$. [b]p2.[/b] Rectangle $ABCD$ has sides $AB = CD = 12/5$, $BC = DA = 5$. Point $P$ is on $AD$ with $\angle BPC = 90^o$. Compute $BP + PC$. [b]p3.[/b] Compute the number of sequences of four decimal digits $(a, b, c, d)$ (each between $0$ and $9$ inclusive) containing no adjacent repeated digits. (That is, each digit is distinct from the digits directly before and directly after it.) [b]p4.[/b] Solve for $t$, $-\pi/4 \le t \le \pi/4 $: $$\sin^3 t + \sin^2 t \cos t + \sin t \cos^2 t + \cos^3 t =\frac{\sqrt6}{2}$$ [b]p5.[/b] Find all integers $n$ such that $n - 3$ divides $n^2 + 2$. [b]p6.[/b] Find the maximum number of bishops that can occupy an $8 \times 8$ chessboard so that no two of the bishops attack each other. (Bishops can attack an arbitrary number of squares in any diagonal direction.) [b]p7.[/b] Points $A, B, C$, and $D$ are on a Cartesian coordinate system with $A = (0, 1)$, $B = (1, 1)$, $C = (1,-1)$, and $D = (-1, 0)$. Compute the minimum possible value of $PA + PB + PC + PD$ over all points $P$. [b]p8.[/b] Find the number of distinct real values of $x$ which satisfy $$(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)(x-9)(x-10)+(1^2 \cdot 3^2\cdot 5^2\cdot 7^2\cdot 9^2)/2^{10} = 0.$$ PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $n$ and $k$ be positive integers with $k$ $\le$ $n$. In a group of $n$ people, each one or always speak the truth or always lie. Arnaldo can ask questions for any of these people provided these questions are of the type: “In set $A$, what is the parity of people who speak to true? ”, where $A$ is a subset of size $ k$ of the set of $n$ people. The answer can only be “$even$” or “$odd$”. a) For which values of $n$ and $k$ is it possible to determine which people speak the truth and which people always lie? b) What is the minimum number of questions required to determine which people speak the truth and which people always lie, when that number is finite?