Let $f_0$ be the function from $\mathbb{Z}^2$ to $\{0,1\}$ such that $f_0(0,0)=1$ and $f_0(x,y)=0$ otherwise. For each positive integer $m$, let $f_m(x,y)$ be the remainder when \[ f_{m-1}(x,y) + \sum_{j=-1}^{1} \sum_{k=-1}^{1} f_{m-1}(x+j,y+k) \] is divided by $2$. Finally, for each nonnegative integer $n$, let $a_n$ denote the number of pairs $(x,y)$ such that $f_n(x,y) = 1$. Find a closed form for $a_n$. [i]Proposed by Bobby Shen[/i]

Let $m$ and $n$ be positive integers. Find all pairs of non-negative integers $a$ and $b$ that always satisfy the following condition: Given any configuration of $m$ white dots and $n$ black dots on a circle, there always exist a line cutting the circle into two arcs, one of which consists of exactly $a$ white dots and $b$ black dots. [i]Proposed by Tan Min Heng[/i]

Consider a $m\times n$ rectangular board consisting of $mn$ unit squares. Two of its unit squares are called [i]adjacent[/i] if they have a common edge, and a [i]path[/i] is a sequence of unit squares in which any two consecutive squares are adjacent. Two parths are called [i]non-intersecting[/i] if they don't share any common squares. Each unit square of the rectangular board can be colored black or white. We speak of a [i]coloring[/i] of the board if all its $mn$ unit squares are colored. Let $N$ be the number of colorings of the board such that there exists at least one black path from the left edge of the board to its right edge. Let $M$ be the number of colorings of the board for which there exist at least two non-intersecting black paths from the left edge of the board to its right edge. Prove that $N^{2}\geq M\cdot 2^{mn}$.

Given that $n$ elements $a_1, a_2,\dots, a_n$ are organized into $n$ pairs $P_1, P_2, \dots, P_n$ in such a way that two pairs $P_i, P_j$ share exactly one element when $(a_i, a_j)$ is one of the pairs, prove that every element is in exactly two of the pairs.

[b]p1.[/b] What is $20\times 19 + 20 \div (2 - 7)$? [b]p2.[/b] Will has three spinners. The first has three equally sized sections numbered $1$, $2$, $3$; the second has four equally sized sections numbered $1$, $2$, $3$, $4$; and the third has five equally sized sections numbered $1$, $2$, $3$, $4$, $5$. When Will spins all three spinners, the probability that the same number appears on all three spinners is $p$. Compute $\frac{1}{p}$. [b]p3.[/b] Three girls and five boys are seated randomly in a row of eight desks. Let $p$ be the probability that the students at the ends of the row are both boys. If $p$ can be expressed in the form $\frac{m}{n}$ for relatively prime positive integers $m$ and $n$, compute $m + n$. [b]p4.[/b] Jaron either hits a home run or strikes out every time he bats. Last week, his batting average was $.300$. (Jaron's batting average is the number of home runs he has hit divided by the number of times he has batted.) After hitting $10$ home runs and striking out zero times in the last week, Jaron has now raised his batting average to $.310$. How many home runs has Jaron now hit? [b]p5.[/b] Suppose that the sum $$\frac{1}{1 \cdot 4} +\frac{1}{4 \cdot 7}+ ...+\frac{1}{97 \cdot 100}$$ is expressible as $\frac{m}{n}$ for relatively prime positive integers $m$ and $n$. Compute $m + n$. [b]p6.[/b] Let $ABCD$ be a unit square with center $O$, and $\vartriangle OEF$ be an equilateral triangle with center $A$. Suppose that $M$ is the area of the region inside the square but outside the triangle and $N$ is the area of the region inside the triangle but outside the square, and let $x = |M -N|$ be the positive difference between $M$ and $N$. If $$x =\frac1 8(p -\sqrt{q})$$ for positive integers $p$ and $q$, find $p + q$. [b]p7.[/b] Find the number of seven-digit numbers such that the sum of any two consecutive digits is divisible by $3$. For example, the number $1212121$ satisfies this property. [b]p8.[/b] There is a unique positive integer $x$ such that $x^x$ has $703$ positive factors. What is $x$? [b]p9.[/b] Let $x$ be the number of digits in $2^{2019}$ and let $y$ be the number of digits in $5^{2019}$. Compute $x + y$. [b]p10.[/b] Let $ABC$ be an isosceles triangle with $AB = AC = 13$ and $BC = 10$. Consider the set of all points $D$ in three-dimensional space such that $BCD$ is an equilateral triangle. This set of points forms a circle $\omega$. Let $E$ and $F$ be points on $\omega$ such that $AE$ and $AF$ are tangent to $\omega$. If $EF^2$ can be expressed in the form $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers, determine $m + n$. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

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]

1400 real numbers are given. Prove that one can choose three of them like $x,y,z$ such that : $$\left|\frac{(x-y)(y-z)(z-x)}{x^4+y^4+z^4+1}\right| < 0.009$$

Let $B$ be a set of $k$ sequences each having $n$ terms equal to $1$ or $-1$. The product of two such sequences $(a_1, a_2, \ldots , a_n)$ and $(b_1, b_2, \ldots , b_n)$ is defined as $(a_1b_1, a_2b_2, \ldots , a_nb_n)$. Prove that there exists a sequence $(c_1, c_2, \ldots , c_n)$ such that the intersection of $B$ and the set containing all sequences from $B$ multiplied by $(c_1, c_2, \ldots , c_n)$ contains at most $\frac{k^2}{2^n}$ sequences.

Initially, each unit square of an $n \times n$ grid is colored red, yellow or blue. In each round, perform the following operation for every unit square simultaneously: [list] [*] For a red square, if there is a yellow square that has a common edge with it, then color it yellow. [*] For a yellow square, if there is a blue square that has a common edge with it, then color it blue. [*] For a blue square, if there is a red square that has a common edge with it, then color it red. [/list] It is known that after several rounds, all unit squares of this $n \times n$ grid have the same color. Prove that the grid has became monochromatic no later than the end of the $(2n-2)$-th round.

Let $ n$, $ k$, $ p$ be positive integers with $ 2 \le k \le \frac {n}{p \plus{} 1}$. Let $ n$ distinct points on a circle be given. These points are colored blue and red so that exactly $ k$ points are blue and, on each arc determined by two consecutive blue points in clockwise direction, there are at least $ p$ red points. How many such colorings are there?

A tiling of the plane with polygons consists of placing the polygons in the plane so that interiors of polygons do not overlap, each vertex of one polygon coincides with a vertex of another polygon, and no point of the plane is left uncovered. A unit polygon is a polygon with all sides of length one. It is quite easy to tile the plane with infinitely many unit squares. Likewise, it is easy to tile the plane with infinitely many unit equilateral triangles. (a) Prove that there is a tiling of the plane with infinitely many unit squares and infinitely many unit equilateral triangles in the same tiling. (b) Prove that it is impossible to find a tiling of the plane with infinitely many unit squares and finitely many (and at least one) unit equilateral triangles in the same tiling.

Consider the sets $A_1,A_2,\dots,A_n$. Set $A_k$ is composed of $k$ disjoint intervals on the real axis ($k=1,2,\dots,n$). Prove that from the intervals contained by these sets, one can choose $\left\lfloor\frac{n+1}2\right\rfloor$ intervals such that they belong to pairwise different sets $A_k$, and no two of these intervals have a common point.

A number from $1$ to $144$ is guessed. You are allowed to select a subset of the set of numbers from $ 1$ to $144$ and ask whether the guessed number belongs to it. For the answer “yes” you have to pay $2$ rubles, for the answer “no” - $1$ ruble. What is the smallest amount of money needed to surely guess that?

There are $n ( \ge 3) $ students in a class. Some students are friends each other, and friendship is always mutual. There are $ s ( \ge 1 ) $ couples of two students who are friends, and $ t ( \ge 1 ) $ triples of three students who are each friends. For two students $ x, y $ define $ d(x,y)$ be the number of students who are both friends with $ x $ and $ y $. Prove that there exist three students $ u, v, w $ who are each friends and satisfying \[ d(u,v) + d(v,w) + d(w,u) \ge \frac{9t}{s} . \]

Two points are selected independently and uniformly at random inside a regular hexagon. Compute the probability that a line passing through both of the points intersects a pair of opposite edges of the hexagon.

China Mathematical Olympiad 2018 Q6 Given the positive integer $n ,k$ $(n>k)$ and $ a_1,a_2,\cdots ,a_n\in (k-1,k)$ ,if positive number $x_1,x_2,\cdots ,x_n$ satisfying:For any set $\mathbb{I} \subseteq \{1,2,\cdots,n\}$ ,$|\mathbb{I} |=k$,have $\sum_{i\in \mathbb{I} }x_i\le \sum_{i\in \mathbb{I} }a_i$ , find the maximum value of $x_1x_2\cdots x_n.$

How many triangles are in this figure? [asy] import olympiad; pair A = (0,0); pair B = (0,1); pair C = (0,2); pair D = (0,3); pair E = (0,4); pair F = (1,0); pair G = (2,0); pair H = (3,0); pair I = (4,0); pair J = (1,4); pair K = (2,4); pair L = (3,4); pair M = (4,4); pair N = (4,3); pair O = (4,2); pair P = (4,1); draw(A--E--I--A); draw(M--E--I--M); draw(B--F); draw(C--G); draw(D--H); draw(L--N); draw(O--K); draw(P--J); draw(B--F); draw(B--F); draw(H--P); draw(G--O); draw(F--N); draw(B--L); draw(C--K); draw(D--J); draw(A--M); [/asy] $(A) 56$ $(B) 60$ $(C) 64$ $(D) 68$

A game is played on an $m \times n$ chessboard. At the beginning, there is a coin on one of the squares. Two players take turns to move the coin to an adjacent square (horizontally or vertically). The coin may never be moved to a square that has been occupied before. If a player cannot move any more, he loses. Prove: [list] [*] If the size (number of squares) of the board is even, then the player to move first has a winning strategy, regardless of the initial position. [*] If the size of the board is odd, then the player to move first has a winning strategy if and only if the coin is initially placed on a square whose colour is not the same as the colour of the corners. [/list]

There are $n$ balls numbered from $1$ to $n$, and $2n-1$ boxes numbered from $1$ to $2n-1$. For each $i$, ball number $i$ can only be put in the boxes with numbers from $1$ to $2i-1$. Let $k$ be an integer from $1$ to $n$. In how many ways we can choose $k$ balls, $k$ boxes and put these balls in the selected boxes so that each box has exactly one ball?

(Game) In an Indian reservatory there are $15$ totem poles arranged according to the left figure. Silent Stream and Red Fire used to play the following game: In turns they stretch ropes between two-two poles in such a way that every stretched rope is parallel to a side of the big triangle and no rope can go along a pole that is already touched by another rope. Furthermore, if instead of a rope one can stretch out a straight line extension of the rope, then one should stretch out this extension. The one who cannot stretch out more rope according to the rules loses. [i]Win two games in a row against the organizers! You can decide that you want to start or to be the second player. The figure on the right depicts the first three steps of a game. First Silent Stream stretches the blue rope, then Red Fire stretches the red one, finally Silent Stream stretches the blue one.[/i] [img]https://cdn.artofproblemsolving.com/attachments/f/8/3b8b9e38a8a477da288566ecb26036bfc7e615.png[/img]

Prove that there exists an undirected graph having $ 2004 $ vertices such that for any $ \in\{ 1,2,\ldots ,1002 \} , $ there exists at least two vertices whose orders are $ n. $

In a tournament each player played exactly one game against each of the other players. In each game the winner was awarded 1 point, the loser got 0 points, and each of the two players earned 1/2 point if the game was a tie. After the completion of the tournament, it was found that exactly half of the points earned by each player were earned against the ten players with the least number of points. (In particular, each of the ten lowest scoring players earned half of her/his points against the other nine of the ten). What was the total number of players in the tournament?

A game in a casino uses the diagram shown. At the start a ball appears at $S$. Each time the player presses a button, the ball moves to one of the adjacent letters with equal probability. The game ends when one of the following two things happens: (i) The ball returns to $S$, the player loses. (ii) The ball reaches $G$, the player wins. Find the probability that the player wins and the expected duration of a game.

An even number of politicians are sitting at a round table. After a break, they come back and sit down again in arbitrary places. Show that there must be two people with the same number of people sitting between them as before the break.. [b]Additional problem:[/b] Solve the problem when the number of people is in a form $6k+3$.

We consider the division of a chess board $8 \times 8$ in p disjoint rectangles which satisfy the conditions: [b]a)[/b] every rectangle is formed from a number of full squares (not partial) from the 64 and the number of white squares is equal to the number of black squares. [b]b)[/b] the numbers $\ a_{1}, \ldots, a_{p}$ of white squares from $p$ rectangles satisfy $a_1, , \ldots, a_p.$ Find the greatest value of $p$ for which there exists such a division and then for that value of $p,$ all the sequences $a_{1}, \ldots, a_{p}$ for which we can have such a division. [color=#008000]Moderator says: see [url]https://artofproblemsolving.com/community/c6h58591[/url][/color]