A policeman is trying to catch a robber on a board of $2001\times2001$ squares. They play alternately, and the player whose trun it is moves to a space in one of the following directions: $\downarrow,\rightarrow,\nwarrow$. If the policeman is on the square in the bottom-right corner, he can go directly to the square in the upper-left corner (the robber can not do this). Initially the policeman is in the central square, and the robber is in the upper-left adjacent square. Show that: $a)$ The robber may move at least $10000$ times before the being captured. $b)$ The policeman has an strategy such that he will eventually catch the robber. Note: The policeman can catch the robber if he reaches the square where the robber is, but not if the robber enters the square occupied by the policeman.

In how many ways can the ”Nikolaus’ House” (see the picture) be drawn? Edges may not be erased nor duplicated, and no additional edges may be drawn. [img]https://cdn.artofproblemsolving.com/attachments/0/5/33795820e0335686b06255180af698e536a9be.png[/img]

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)$.

Prove that from every set of $n+1$ natural numbers, whose prime factors are in a given set of $n$ prime numbers, one can select several distinct numbers whose product is a perfect square.

Fix a convex $n > 3$ gon $A_{1}A_{2}...A_{n} $ and connect every two points with a road. Call this $n$-gon [i]crossy[/i] if no three roads intersect at a point inside the polygon. This $n$-gon is partitioned into a set $S$ of disjoint polygons formed by the roads. Label every intersection with an integer such that $A_{1}$ is non-zero. Call the labelling [i]basic[/i] if for every polygon in $S$, the sum of the labels of its vertices is $0$. $(a)$ Prove that there is a [i]basic[/i] labelling of a crossy $n$-gon when $n$ is even. $(b)$ Prove that there is no [i]basic[/i] labelling of a crossy $n$-gon when $n$ is odd.

In the plane there are $2014$ plotted points, such that no $3$ are collinear. For each pair of plotted points, draw the line that passes through them. prove that for every three of marked points there are always two that are separated by an amount odd number of lines.

We call a permutation $(a_1, a_2,\cdots , a_n)$ of the set $\{ 1,2,\cdots, n\}$ "good" if for any three natural numbers $i <j <k$, $n\nmid a_i+a_k-2a_j$ find all natural numbers $n\ge 3$ such that there exist a "good" permutation of a set $\{1,2,\cdots, n\}$.

Suppose there are several juice boxes, one of which is poisoned. You have $n$ guinea pigs to test the boxes. The testing happens in the following way: [list] [*] At each round, you can have the guinea pigs taste any number of juice boxes. [*] Conversely, a juice box can be tasted by any number of guinea pigs. [*] After the round ends, any guinea pigs who tasted the poisoned juice die. [/list] Suppose you have to find the poisoned juice box in at most $k$ rounds. What is the maximum number of juice boxes such that it is possible?

Consider a polyhedron having $100$ edges. (a) Find the maximal possible number of its edges which can be intersected by a plane (not containing any vertices of the polyhedron) if the polyhedron is convex. (b) Prove that for a non-convex polyhedron this number i. can be as great as $96$, ii. cannot be as great as $100$. (A Andjans, Riga

Two boys are given a bag of potatoes, each bag containing $150$ tubers. They take turns transferring the potatoes, where in each turn they transfer a non-zero tubers from their bag to the other boy's bag. Their moves must satisfy the following condition: In each move, a boy must move more tubers than he had in his bag before any of his previous moves (if there were such moves). So, with his first move, a boy can move any non-zero quantity, and with his fifth move, a boy can move $200$ tubers, if before his first, second, third and fourth move, the numbers of tubers in his bag was less than $200$. What is the maximal total number of moves the two boys can do? [i]Proposed by E. Molchanov[/i]

For any positive integer $n$, let $f(n)$ be the number of possible choices of signs $+\ \text{or}\ - $ in the algebraic expression $\pm 1\pm 2\ldots \pm n$, such that the obtained sum is zero. Show that $f(n)$ satisfies the following conditions: a) $f(n)=0$ for $n=1\pmod{4}$ or $n=2\pmod{4}$. b) $2^{\frac{n}{2}-1}\le f(n)\le 2^n-2^{\lfloor\frac{n}{2}\rfloor+1}$, for $n=0\pmod{4}$ or $n=3\pmod{4}$. [i]Ioan Tomsecu[/i]

For positive integers $p$, $q$ and $r$ we are given $p \cdot q \cdot r$ unit cubes. We drill a hole along the space diagonal of each of these cubes and then tie them to a very thin thread of length $p \cdot q \cdot r \cdot \sqrt{3}$ like a string of pearls. We now want to construct a cuboid of side lengths $p$, $q$ and $r$ out of the cubes, without tearing the thread. a) For which numbers $p$, $q$ and $r$ is this possible? b) For which numbers $p$, $q$ and $r$ is this possible in a way such that both ends of the thread coincide?

An $m \times n$ chessboard with $m,n \ge 2$ is given. Some dominoes are placed on the chessboard so that the following conditions are satisfied: (i) Each domino occupies two adjacent squares of the chessboard, (ii) It is not possible to put another domino onto the chessboard without overlapping, (iii) It is not possible to slide a domino horizontally or vertically without overlapping. Prove that the number of squares that are not covered by a domino is less than $\frac15 mn$.

Let $A$ and $E$ be opposite vertices of an octagon. A frog starts at vertex $A.$ From any vertex except $E$ it jumps to one of the two adjacent vertices. When it reaches $E$ it stops. Let $a_n$ be the number of distinct paths of exactly $n$ jumps ending at $E$. Prove that: \[ a_{2n-1}=0, \quad a_{2n}={(2+\sqrt2)^{n-1} - (2-\sqrt2)^{n-1} \over\sqrt2}. \]

The $2001 \times 2001$ trees in a park form a square grid. What is the largest number of trees that can be cut so that no tree stump can be seen from any other? (Each tree has zero width.)

The [i]binary sudoku[/i] is a puzzle in which a table should be filled with digits $0$ and $1$ such that in each row and column, the number of 0s is equal to the number of $1$s. Furthermore, there cannot exist three adjacent cells in a row or in a column such that they have the same digit written in them. Solving the given binary sudoku, what is the sum of the numbers in the two diagonals? [img]https://cdn.artofproblemsolving.com/attachments/a/8/be7de94ce02a90b3cabf1b9795b94ec7ec677f.png[/img]

$10$ people attended a party. For every $3$ people, there exist at least $2$ people who don’t know each other. Prove that there exist $4$ people who don’t know each other.

Initially, on the board, all integers from $1$ to $400$ are written. Two players play a game alternating their moves. In one move it is allowed to erase from the board any 3 integers, which form a triangle. The player, who can not perform a move loses. Who has a winning strategy?

For which integers $N\ge 3$ can we find $N$ points on the plane such that no three are collinear, and for any triangle formed by three vertices of the points’ convex hull, there is exactly one point within that triangle?

Let $m$ and $n$ be positive integers. For a connected simple graph $G$ on $n$ vertices and $m$ edges, we consider the number $N(G)$ of orientations of (all of) its edges so that, in the resulting directed graph, every vertex has even outdegree. Show that $N(G)$ only depends on $m$ and $n$, and determine its value.

There are $10001$ students at an university. Some students join together to form several clubs (a student may belong to different clubs). Some clubs join together to form several societies (a club may belong to different societies). There are a total of $k$ societies. Suppose that the following conditions hold: [i]i.)[/i] Each pair of students are in exactly one club. [i]ii.)[/i] For each student and each society, the student is in exactly one club of the society. [i]iii.)[/i] Each club has an odd number of students. In addition, a club with ${2m+1}$ students ($m$ is a positive integer) is in exactly $m$ societies. Find all possible values of $k$. [i]Proposed by Guihua Gong, Puerto Rico[/i]

When flipped, a coin has a probability $p$ of landing heads. When flipped twice, it is twice as likely to land on the same side both times as it is to land on each side once. What is the larger possible value of $p$?

Alice has six boxes labelled 1 through 6. She secretly chooses exactly two of the boxes and places a coin inside each. Bob is trying to guess which two boxes contain the coins. Each time Bob guesses, he does so by tapping exactly two of the boxes. Alice then responds by telling him the total number of coins inside the two boxes that he tapped. Bob successfully finds the two coins when Alice responds with the number 2. What is the smallest positive integer $n$ such that Bob can always find the two coins in at most $n$ guesses?

[b]p1.[/b] BmMT is in a week, and we don’t have any problems! Let’s write $1$ on the first day, $2$ on the second day, $4$ on the third, $ 8$ on the fourth, $16$ on the fifth, $32$ on the sixth, and $64$ on the seventh. After seven days, how many problems will we have written in total? [b]p2.[/b] $100$ students are taking a ten-point exam. $50$ students scored $8$ points, $30$ students scored $7$ points, and the rest scored $9$ points. What is the average score for the exam? [b]p3.[/b] Rebecca has four pairs of shoes. Rebecca may or may not wear matching shoes. However, she will always use a left-shoe for her left foot and a right-shoe for her right foot. How many ways can Rebecca wear shoes? [b]p4.[/b] A council of $111$ mathematicians voted on whether to hold their conference in Beijing or Shanghai. The outcome of an initial vote was $70$ votes in favor of Beijing, and 41 votes in favor of Shanghai. If the vote were to be held again, what is the minimum number of mathematicians that would have to change their votes in order for Shanghai to win a majority of votes? [b]p5.[/b] What is the area of the triangle bounded by the line $20x + 16y = 160$, the $x$-axis, and the $y$-axis? [b]p6.[/b] Suppose that $3$ runners start running from the start line around a circular $800$-meter track and that their speeds are $100$, $160$, and $200$ meters per minute, respectively. How many minutes will they run before all three are next at the start line at the same time? [b]p7.[/b] Brian’s lawn is in the shape of a circle, with radius $10$ meters. Brian can throw a frisbee up to $50$ meters from where he stands. What is the area of the region (in square meters) in which the frisbee can land, if Brian can stand anywhere on his lawn? [b]p8.[/b] A seven digit number is called “bad” if exactly four of its digits are $0$ and the rest are odd. How many seven digit numbers are bad? [b]p9.[/b] Suppose you have a $3$-digit number with only even digits. What is the probability that twice that number also has only even digits? [b]p10.[/b] You have a flight on Air China from Beijing to New York. The flight will depart any time between $ 1$ p.m. and $6$ p.m., uniformly at random. Your friend, Henry, is flying American Airlines, also from Beijing to New York. Henry’s flight will depart any time between $3$ p.m. and $5$ p.m., uniformly at random. What is the probability that Henry’s flight departs before your flight? [b]p11.[/b] In the figure below, three semicircles are drawn outside the given right triangle. Given the areas $A_1 = 17$ and $A_2 = 14$, find the area $A_3$. [img]https://cdn.artofproblemsolving.com/attachments/4/4/28393acb3eba83a5a489e14b30a3e84ffa60fb.png[/img] [b]p12.[/b] Consider a circle of radius $ 1$ drawn tangent to the positive $x$ and $y$ axes. Now consider another smaller circle tangent to that circle and also tangent to the positive $x$ and $y$ axes. Find the radius of the smaller circle. [img]https://cdn.artofproblemsolving.com/attachments/7/4/99b613d6d570db7ee0b969f57103d352118112.png[/img] [b]p13.[/b] The following expression is an integer. Find this integer: $\frac{\sqrt{20 + 16\frac{\sqrt{20+ 16\frac{20 + 16...}{2}}}{2}}}{2}$ [b]p14.[/b] Let $2016 = a_1 \times a_2 \times ... \times a_n$ for some positive integers $a_1, a_2, ... , a_n$. Compute the smallest possible value of $a_1 + a_2 + ...+ a_n$. [b]p15.[/b] The tetranacci numbers are defined by the recurrence $T_n = T_{n-1} + T_{n-2} + T_{n-3} + T_{n-4}$ and $T_0 = T_1 = T_2 = 0$ and $T_3 = 1$. Given that $T_9 = 29$ and $T_{14} = 773$, calculate $T_{15}$. [b]p16.[/b] Find the number of zeros at the end of $(2016!)^{2016}$. Your answer should be an integer, not its prime factorization. [b]p17.[/b] A DJ has $7$ songs named $1, 2, 3, 4, 5, 6$, and $7$. He decides that no two even-numbered songs can be played one after the other. In how many different orders can the DJ play the $7$ songs? [b]p18.[/b] Given a cube, how many distinct ways are there (using $6$ colors) to color each face a distinct color? Colorings are distinct if they cannot be transformed into one another by a sequence of rotations. [b]p19. [/b]Suppose you have a triangle with side lengths $3, 4$, and $5$. For each of the triangle’s sides, draw a square on its outside. Connect the adjacent vertices in order, forming $3$ new triangles (as in the diagram). What is the area of this convex region? [img]https://cdn.artofproblemsolving.com/attachments/4/c/ac4dfb91cd055badc07caface93761453049fa.png[/img] [b]p20.[/b] Find $x$ such that $\sqrt{c +\sqrt{c - x}} = x$ when $c = 4$. PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

On a $1000\times 1000$-board we put dominoes, in such a way that each domino covers exactly two squares on the board. Moreover, two dominoes are not allowed to be adjacent, but are allowed to touch in a vertex. Determine the maximum number of dominoes that we can put on the board in this way. [i]Attention: you have to really prove that a greater number of dominoes is impossible. [/i]