There is an empty table with $2^{100}$ rows and $100$ columns. Alice and Eva take turns filling the empty cells of the first row of the table, Alice plays first. In each move, Alice chooses an empty cell and puts a cross in it; Eva in each move chooses an empty cell and puts a zero. When no empty cells remain in the first row, the players move on to the second row, and so on (in each new row Alice plays first). The game ends when all the rows are filled. Alice wants to make as many different rows in the table as possible, while Eva wants to make as few as possible. How many different rows will be there in the table if both follow their best strategies? Proposed by Denis Afrizonov

Find all permutations $a_1, a_2, \ldots, a_9$ of $1, 2, \ldots, 9$ such that \[ a_1+a_2+a_3+a_4=a_4+a_5+a_6+a_7= a_7+a_8+a_9+a_1 \] and \[ a_1^2+a_2^2+a_3^2+a_4^2=a_4^2+a_5^2+a_6^2+a_7^2= a_7^2+a_8^2+a_9^2+a_1^2 \]

Kevin colors three distinct squares in a $3\times 3$ grid red. Given that there exist two uncolored squares such that coloring one of them would create a horizontal or vertical red line, find the number of ways he could have colored the original three squares.

The Judgment of the Council of Sages proceeds as follows: the king arranges the sages in a line and places either a white hat, black hat or a red hat on each sage's head. Each sage can see the color of the hats of the sages in front of him, but not of his own hat or of the hats of the sages behind him. Then one by one (in an order of their choosing), each sage guesses a color. Afterward, the king executes those sages who did not correctly guess the color of their own hat. The day before, the Council meets and decides to minimize the number of executions. What is the smallest number of sages guaranteed to survive in this case? [i]K. Knop[/i] P.S. Of course, the sages hear the previous guesses. See also [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=530552[/url]

Let $A_{1}, ..., A_{n}$ be different subsets of an $n$-element set $X$. Show that there exists $x\in X$ such that the sets $A_{1}-\{x\}, A_{2}-\{x\}, ..., A_{n}-\{x\}$ are all different.

Let $n\geq 2$ be an integer. Let us call [i]interval[/i] a subset $A \subseteq \{1,2,\ldots,n\}$ for which integers $1\leq a < b\leq n$ do exist, such that $A = \{a,a+1,\ldots,b-1,b\}$. Let a family $\mathcal{A}$ of subsets $A_i \subseteq \{1,2,\ldots,n\}$, with $1\leq i \leq N$, be such that for any $1\leq i < j \leq N$ we have $A_i \cap A_j$ being an interval. Prove that $\displaystyle N \leq \left \lfloor n^2/4 \right \rfloor$, and that this bound is sharp. (Dan Schwarz - after an idea by Ron Graham)

Let $A$ be a set of $n\ge3$ points in the plane, no three of which are collinear. Show that there is a set $S$ of $2n-5$ points in the plane such that, for each triangle with vertices in $A$, there exists a point in $S$ which is strictly inside that triangle.

For each positive integer $ n$, let $ f(n)$ denote the number of ways of representing $ n$ as a sum of powers of 2 with nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For instance, $ f(4) \equal{} 4$, because the number 4 can be represented in the following four ways: 4; 2+2; 2+1+1; 1+1+1+1. Prove that, for any integer $ n \geq 3$ we have $ 2^{\frac {n^2}{4}} < f(2^n) < 2^{\frac {n^2}2}$.

Consider a game in the integer points of the real line, where an Angel tries to escape from a Devil. A positive integer $k$ is chosen, and the Angel and the Devil take turns playing. Initially, no point is blocked. The Angel, in point $A$, can move to any point $P$ such that $|AP| \le k$, as long as $P$ is not blocked. The Devil may block an arbitrary point. The Angel loses if it cannot move and wins if it does not lose in finitely many turns. Let $f(k)$ denote the least number of rounds the Devil takes to win. Prove that $$0.5 k \log_2 (k) (1 + o(1)) \le f(k) \le k \log_2(k) (1 +o(1)).$$ Note: $a(x) = b(x) (1+o(1))$ if $\lim_{x \to \infty} \frac{b(x)}{a(x)} = 1$.

How many 6-tuples $ (a_1,a_2,a_3,a_4,a_5,a_6)$ are there such that each of $ a_1,a_2,a_3,a_4,a_5,a_6$ is from the set $ \{1,2,3,4\}$ and the six expressions \[ a_j^2 \minus{} a_ja_{j \plus{} 1} \plus{} a_{j \plus{} 1}^2\] for $ j \equal{} 1,2,3,4,5,6$ (where $ a_7$ is to be taken as $ a_1$) are all equal to one another?

A traveller visited a village whose inhabitants either always tell the truth or always lie. The villagers stood in a circle facing the centre of the circle, and each villager announced whether the person standing to his right is a truth-teller. On the basis of this information, the traveller was able to determine what fraction of the villagers were liars. What was this fraction? (B, Frenkin)

An $n \times n$ board is given. In the top left corner cell there is a fox, whereas in the bottom left corner cell there is a rabbit. Every minute, the fox and the rabbit jump to a neighbouring cell at the same time. The fox can jump only to neighbouring cells that are below it or on its right, whereas the rabbit can only jump to the cells above it or in its right. They continue like this until they have no possible moves. The fox catches the rabbit if at a certain moment they are in the same cell, otherwise the rabbit gets away. Find all natural numbers $n$ for which the fox has a winning strategy to catch the rabbit. [i](Note: Two squares are considered neighbours if they have a common side.)[/i]

Let $G$ be a planar graph, which is also bipartite. Is it always possible to assign a vertex to each face of the graph such that no two faces have the same vertex assigned to them? [i]Submitted by Dávid Matolcsi, Budapest[/i]

[b]p1.[/b] Let $A = \{D,U,K,E\}$ and $B = \{M, A, T,H\}$. How many maps are there from $A$ to $B$? [b]p2.[/b] The product of two positive integers $x$ and $y$ is equal to $3$ more than their sum. Find the sum of all possible $x$. [b]p3.[/b] There is a bag with $1$ red ball and $1$ blue ball. Jung takes out a ball at random and replaces it with a red ball. Remy then draws a ball at random. Given that Remy drew a red ball, what is the probability that the ball Jung took was red? [b]p4.[/b] Let $ABCDE$ be a regular pentagon and let $AD$ intersect $BE$ at $P$. Find $\angle APB$. [b]p5.[/b] It is Justin and his $4\times 4\times 4$ cube again! Now he uses many colors to color all unit-cubes in a way such that two cubes on the same row or column must have different colors. What is the minimum number of colors that Justin needs in order to do so? [b]p6.[/b] $f(x)$ is a polynomial of degree $3$ where $f(1) = f(2) = f(3) = 4$ and $f(-1) = 52$. Determine $f(0)$. [b]p7.[/b] Mike and Cassie are partners for the Duke Problem Solving Team and they decide to meet between $1$ pm and $2$ pm. The one who arrives first will wait for the other for $10$ minutes, the lave. Assume they arrive at any time between $1$ pm and $2$ pm with uniform probability. Find the probability they meet. [b]p8.[/b] The remainder of $2x^3 - 6x^2 + 3x + 5$ divided by $(x - 2)^2$ has the form $ax + b$. Find $ab$. [b]p9.[/b] Find $m$ such that the decimal representation of m! ends with exactly $99$ zeros. [b]p10.[/b] Let $1000 \le n = \overline{DUKE} \le 9999$. be a positive integer whose digits $\overline{DUKE}$ satisfy the divisibility condition: $$1111 | \left( \overline{DUKE} + \overline{DU} \times \overline{KE} \right)$$ Determine the smallest possible value of $n$. PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

There are 2008 bags numbered from 1 to 2008, with 2008 frogs in each one of them. Two people play in turns. A play consists in selecting a bag and taking out of it any number of frongs (at least one), leaving $ x$ frogs in it ($ x\geq 0$). After each play, from each bag with a number higher than the selected one and having more than $ x$ frogs, some frogs scape until there are $ x$ frogs in the bag. The player that takes out the last frog from bag number 1 looses. Find and explain a winning strategy.

In town $ A,$ there are $ n$ girls and $ n$ boys, and each girl knows each boy. In town $ B,$ there are $ n$ girls $ g_1, g_2, \ldots, g_n$ and $ 2n \minus{} 1$ boys $ b_1, b_2, \ldots, b_{2n\minus{}1}.$ The girl $ g_i,$ $ i \equal{} 1, 2, \ldots, n,$ knows the boys $ b_1, b_2, \ldots, b_{2i\minus{}1},$ and no others. For all $ r \equal{} 1, 2, \ldots, n,$ denote by $ A(r),B(r)$ the number of different ways in which $ r$ girls from town $ A,$ respectively town $ B,$ can dance with $ r$ boys from their own town, forming $ r$ pairs, each girl with a boy she knows. Prove that $ A(r) \equal{} B(r)$ for each $ r \equal{} 1, 2, \ldots, n.$

A mathematical frog jumps along the number line. The frog starts at $1$, and jumps according to the following rule: if the frog is at integer $n$, then it can jump either to $n+1$ or to $n + 2^{m_n+1}$ where $2^{m_n}$ is the largest power of $2$ that is a factor of $n.$ Show that if $k \geq 2$ is a positive integer and $i$ is a nonnegative integer, then the minimum number of jumps needed to reach $2^ik$ is greater than the minimum number of jumps needed to reach $2^i.$

There is a rectangular plot of size $1 \times n$. This has to be covered by three types of tiles - red, blue and black. The red tiles are of size $1 \times 1$, the blue tiles are of size $1 \times 1$ and the black tiles are of size $1 \times 2$. Let $t_n$ denote the number of ways this can be done. For example, clearly $t_1 = 2$ because we can have either a red or a blue tile. Also $t_2 = 5$ since we could have tiled the plot as: two red tiles, two blue tiles, a red tile on the left and a blue tile on the right, a blue tile on the left and a red tile on the right, or a single black tile. [list=a] [*]Prove that $t_{2n+1} = t_n(t_{n-1} + t_{n+1})$ for all $n > 1$. [*]Prove that $t_n = \sum_{d \ge 0} \binom{n-d}{d}2^{n-2d}$ for all $n >0$. [/list] Here, \[ \binom{m}{r} = \begin{cases} \dfrac{m!}{r!(m-r)!}, &\text{ if $0 \le r \le m$,} \\ 0, &\text{ otherwise} \end{cases}\] for integers $m,r$.

Victor shuffles a standard 54-card deck then flips over cards one at a time onto a pile stopping after the first ace. However, if he ever reveals a joker he discards the entire pile, including the joker, and starts a new pile; for example, if the sequence of cards is 2-3-Joker-A, the pile ends with one card in it. Find the expected number of cards in the end pile.

For $n \ge 3$, it is given an $2n \times 2n$ board with black and white squares. It is known that all border squares are black and no $2 \times 2$ subboard has all four squares of the same color. Prove that there exists a $2 \times 2$ subboard painted like a chessboard, i.e. with two opposite black corners and two opposite white corners.

A binary sequence is a sequence in which each term is equal to $0$ or $1$. A binary sequence is called $\text{friendly}$ if each term is adjacent to at least on term that is equal to $1$. For example , the sequence $0,1,1,0,0,1,1,1$ is $\text{friendly}$. Let $F_{n}$ denote the number of $\text{friendly}$ binary sequences with $n$ terms. Find the smallest positive integer $n\ge 2$ such that $F_{n}>100$

Given is a prime number $p$ and natural $n$ such that $p \geq n \geq 3$. Set $A$ is made of sequences of lenght $n$ with elements from the set $\{0,1,2,...,p-1\}$ and have the following property: For arbitrary two sequence $(x_1,...,x_n)$ and $(y_1,...,y_n)$ from the set $A$ there exist three different numbers $k,l,m$ such that: $x_k \not = y_k$, $x_l \not = y_l$, $x_m \not = y_m$. Find the largest possible cardinality of $A$.

[u]Round 5[/u] [b]p13.[/b] Points $A, B, C$, and $D$ lie in a plane with $AB = 6$, $BC = 5$, and $CD = 5$, and $AB$ is perpendicular to $BC$. Point E lies on line $AD$ such that $D \ne E$, $AE = 3$ and $CE = 5$. Find $DE$. [b]p14.[/b] How many ordered pairs of integers $(x,y)$ are solutions to $x^2y = 36 + y$? [b]p15.[/b] Chicken nuggets come in boxes of two sizes, $a$ nuggets per box and $b$ nuggets per box. We know that $899$ nuggets is the largest number of nuggets we cannot obtain with some combination of $a$-sized boxes and $b$-sized boxes. How many different pairs $(a, b)$ are there with $a < b$? [u]Round 6[/u] [b]p16.[/b] You are playing a game with coins with your friends Alice and Bob. When all three of you flip your respective coins, the majority side wins. For example, if Alice, Bob, and you flip Heads, Tails, Heads in that order, then you win. If Alice, Bob, and you flip Heads, Heads, Tails in that order, then you lose. Notice that more than one person will “win.” Alice and Bob design their coins as follows: a value $p$ is chosen randomly and uniformly between $0$ and $1$. Alice then makes a biased coin that lands on heads with probability $p$, and Bob makes a biased coin that lands on heads with probability $1 -p$. You design your own biased coin to maximize your chance of winning without knowing $p$. What is the probability that you win? [b]p17.[/b] There are $N$ distinct students, numbered from $1$ to $N$. Each student has exactly one hat: $y$ students have yellow hats, $b$ have blue hats, and $r$ have red hats, where $y + b + r = N$ and $y, b, r > 0$. The students stand in a line such that all the $r$ people with red hats stand in front of all the $b$ people with blue hats. Anyone wearing red is standing in front of everyone wearing blue. The $y$ people with yellow hats can stand anywhere in the line. The number of ways for the students to stand in a line is $2016$. What is $100y + 10b + r$? [b]p18.[/b] Let P be a point in rectangle $ABCD$ such that $\angle APC = 135^o$ and $\angle BPD = 150^o$. Suppose furthermore that the distance from P to $AC$ is $18$. Find the distance from $P$ to $BD$. [u]Round 7 [/u] [b]p19.[/b] Let triangle $ABC$ be an isosceles triangle with $|AB| = |AC|$. Let $D$ and $E$ lie on $AB$ and $AC$, respectively. Suppose $|AD| = |BC| = |EC|$ and triangle $ADE$ is isosceles. Find the sum of all possible values of $\angle BAC$ in radians. Write your answer in the form $2 arcsin \left( \frac{a}{b}\right) + \frac{c}{d} \pi$, where $\frac{a}{b}$ and $\frac{c}{d}$ are in lowest terms, $-1 \le \frac{a}{b} \le 1$, and $-1 \le \frac{c}{d} \le 1$. [b]p20.[/b] Kevin is playing a game in which he aims to maximize his score. In the $n^{th}$ round, for $n \ge 1$, a real number between $0$ and $\frac{1}{3^n}$ is randomly generated. At each round, Kevin can either choose to have the randomly generated number from that round as his score and end the game, or he can choose to pass on the number and continue to the next round. Once Kevin passes on a number, he CANNOT claim that number as his score. Kevin may continue playing for as many rounds as he wishes. If Kevin plays optimally, the expected value of his score is $a + b\sqrt{c}$ where $a, b$, and $c$ are integers and $c$ is positive and not divisible by any positive perfect square other than $1$. What is $100a + 10b + c$? [b]p21.[/b] Lisa the ladybug (a dimensionless ladybug) lives on the coordinate plane. She begins at the origin and walks along the grid, at each step moving either right or up one unit. The path she takes ends up at $(2016, 2017)$. Define the “area” of a path as the area below the path and above the $x$-axis. The sum of areas over all paths that Lisa can take can be represented as as $a \cdot {{4033} \choose {2016}}$ . What is the remainder when $a$ is divided by $1000$? PS. You should use hide for answers. Rounds 1-4 have been posted [url=https://artofproblemsolving.com/community/c4h2782871p24446475]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $n$ be a natural number. Find the least natural number $k$ for which there exist $k$ sequences of $0$ and $1$ of length $2n+2$ with the following property: any sequence of $0$ and $1$ of length $2n+2$ coincides with some of these $k$ sequences in at least $n+2$ positions.

There are $17$ people at a party, and each has a reputation that is either $1$, $2$, $3$, $4$, or $5$. Some of them split into pairs under the condition that within each pair, the two people’s reputations differ by at most $1$. Compute the largest value of $k$ such that no matter what the reputations of these people are, they are able to form $k$ pairs