A $9 \times 9$ chessboard with the standard checkered pattern has white squares at its four corners. What is the least number of rooks that can be placed on this board so that all the white squares are attacked? (A rook also attacks the square it is on, in addition to every other square in the same row or column.)

Can the numbers from 1 to 81 be written in a 9×9 board, so that the sum of numbers in each 3×3 square is the same? [i]S. Tokarev[/i]

Let $n$ and $k$ be positive integers, with $k \le n.$ Define a (simple, undirected) graph $G_{n,k}$ as follows: its vertices are all of the binary strings of length $n,$ and there is an edge between two strings if and only if they differ in exactly $k$ positions. If $c_{n,k}$ denotes the number of connected components of $G_{n,k},$ compute $$\sum_{n=1}^{10} \sum_{k=1}^n c_{n,k}.$$ (For example, $G_{3,2}$ has two connected components.)

$101$ people, sitting at a round table in any order, had $1,2,... , 101$ cards, respectively. A transfer is someone give one card to one of the two people adjacent to him. Find the smallest positive integer $k$ such that there always can through no more than $ k $ times transfer, each person hold cards of the same number, regardless of the sitting order.

1) Cells of $8 \times 8$ table contain pairwise distinct positive integers. Each integer is prime or a product of two primes. It is known that for any integer $a$ from the table there exists integer written in the same row or in the same column such that it is not relatively prime with $a$. Find maximum possible number of prime integers in the table. 2) Cells of $2n \times 2n$ table, $n \ge 2,$ contain pairwise distinct positive integers. Each integer is prime or a product of two primes. It is known that for any integer $a$ from the table there exist integers written in the same row and in the same column such that they are not relatively prime with $a$. Find maximum possible number of prime integers in the table.

Alphonse and Beryl play a game involving $n$ safes. Each safe can be opened by a unique key and each key opens a unique safe. Beryl randomly shuffles the $n$ keys, and after placing one key inside each safe, she locks all of the safes with her master key. Alphonse then selects $m$ of the safes (where $m < n$), and Beryl uses her master key to open just the safes that Alphonse selected. Alphonse collects all of the keys inside these $m$ safes and tries to use these keys to open up the other $n - m$ safes. If he can open a safe with one of the $m$ keys, he can then use the key in that safe to try to open any of the remaining safes, repeating the process until Alphonse successfully opens all of the safes, or cannot open any more. Let $P_m(n)$ be the probability that Alphonse can eventually open all $n$ safes starting from his initial selection of $m$ keys. (a) Show that $P_2(3) = \frac23$. (b) Prove that $P_1(n) = \frac1n$. (c) For all integers $n \geq 2$, prove that $$P_2(n) = \frac2n \cdot P_1(n-1) + \frac{n-2}{n} \cdot P_2(n-1).$$ (d) Determine a formula for $P_2 (n)$.

Let $A$ be a set of finite distinct positive real numbers. Two other sets $B$, $C$ are defined by: \[B = \left\{ {\frac{x}{y};x,y \in A} \right\},\; \; \; C = \left\{ {xy;x,y \in A} \right\}\] Prove that $\left| A \right|.\left| B \right| \le {\left| C \right|^2}$.

Let $S$ be a positive integer divisible by all the integers $1, 2,...,2015$ and $a_1, a_2,..., a_k$ numbers in $\{1, 2,...,2015\}$ such that $2S \le a_1 + a_2 + ... + a_k$. Prove that we can select from $a_1, a_2,..., a_k$ some numbers so that the sum of these selected numbers is equal to $S$. Lê Anh Vinh

Alice and Bob are playing a game. First, Alice chooses a partition $\mathcal{C}$ of the positive integers into a (not necessarily finite) set of sets, such that each positive integer is in exactly one of the sets in $\mathcal{C}$. Then Bob does the following operation a finite number of times. Choose a set $S \in \mathcal{C}$ not previously chosen, and let $D$ be the set of all positive integers dividing at least one element in $S$. Then add the set $D \setminus S$ (possibly the empty set) to $\mathcal{C}$. Bob wins if there are two equal sets in $\mathcal{C}$ after he has done all his moves, otherwise, Alice wins. Determine which player has a winning strategy.

We have $2^m$ sheets of paper, with the number $1$ written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are $a$ and $b$, then we erase these numbers and write the number $a + b$ on both sheets. Prove that after $m2^{m -1}$ steps, the sum of the numbers on all the sheets is at least $4^m$ . [i]Proposed by Abbas Mehrabian, Iran[/i]

In a country with $2015$ cities there is exactly one two-way flight between each city. The three flights made between three cities belong to at most two different airline companies. No matter how the flights are shared between some number of companies, if there is always a city in which $k$ flights belong to the same airline, what is the maximum value of $k$?

Each rational point on a real line is assigned an integer. Prove that there is a segment such that the sum of the numbers at its endpoints does not exceed twice the number at its midpoint.

Let $A$ be a set of positive integers. $A$ is called "balanced" if [and only if] the number of 3-element subsets of $A$ whose elements add up to a multiple of $3$ is equal to the number of 3-element subsets of $A$ whose elements add up to not a multiple of $3$. a. Find a 9-element balanced set. b. Prove that no set of $2013$ elements can be balanced.

A convicted person will be released when he reaches the top of a $100$-step staircase. But he cannot advance as he pleases, since he is obliged to go up one step each day of the odd-numbered months and go down one step each day of the even-numbered months. If it begins on January $ 1$, $2001$, what day will it be released?

For which positive integers $n \ge 3$ is it possible to mark $n$ points of a plane in such a way that, starting from one marked point and moving on each step to the marked point which is the second closest to the current point, one can walk through all the marked points and return to the initial one? For each point, the second closest marked point must be uniquely determined.

The integers $1$ through $1000$ are located on the circumference of a circle in natural order. Starting with $1$, every fifteenth number (i.e.,$1, 16, 31, \cdots$ ) is marked. The marking is continued until an already marked number is reached. How many of the numbers will be left unmarked?

Consider a point $O$ in the plane. Find all sets $S$ of at least two points in the plane such that if $A\in S$ ad $A\neq O$, then the circle with diameter $OA$ is in $S$. [i]Nikolai Nikolov, Slavomir Dinev[/i]

[u]Round 1[/u] [b]p1.[/b] A box contains $1$ ball labelledW, $1$ ball labelled $E$, $1$ ball labelled $L$, $1$ ball labelled $C$, $1$ ball labelled $O$, $8$ balls labelled $M$, and $1$ last ball labelled $E$. One ball is randomly drawn from the box. The probability that the ball is labelled $E$ is $\frac{1}{a}$ . Find $a$. [b]p2.[/b] Let $$G +E +N = 7$$ $$G +E +O = 15$$ $$N +T = 22.$$ Find the value of $T +O$. [b]p3.[/b] The area of $\vartriangle LMT$ is $22$. Given that $MT = 4$ and that there is a right angle at $M$, find the length of $LM$. [u]Round 2[/u] [b]p4.[/b] Kevin chooses a positive $2$-digit integer, then adds $6$ times its unit digit and subtracts $3$ times its tens digit from itself. Find the greatest common factor of all possible resulting numbers. [b]p5.[/b] Find the maximum possible number of times circle $D$ can intersect pentagon $GRASS'$ over all possible choices of points $G$, $R$, $A$, $S$, and $S'$. [b]p6.[/b] Find the sum of the digits of the integer solution to $(\log_2 x) \cdot (\log_4 \sqrt{x}) = 36$. [u]Round 3[/u] [b]p7.[/b] Given that $x$ and $y$ are positive real numbers such that $x^2 + y = 20$, the maximum possible value of $x + y$ can be written as $\frac{a}{b}$ where $a$ and $b$ are relatively prime positive integers. Find $a +b$. [b]p8.[/b] In $\vartriangle DRK$, $DR = 13$, $DK = 14$, and $RK = 15$. Let $E$ be the point such that $ED = ER = EK$. Find the value of $\lfloor DE +RE +KE \rfloor$. [b]p9.[/b] Subaru the frog lives on lily pad $1$. There is a line of lily pads, numbered $2$, $3$, $4$, $5$, $6$, and $7$. Every minute, Subaru jumps from his current lily pad to a lily pad whose number is either $1$ or $2$ greater, chosen at random from valid possibilities. There are alligators on lily pads $2$ and $5$. If Subaru lands on an alligator, he dies and time rewinds back to when he was on lily pad number $1$. Find how many times Subaru is expected to die before he reaches pad $7$. [u]Round 4[/u] [b]p10.[/b] Find the sum of the following series: $$\sum^{\infty}_{i=1} = \frac{\sum^i_{j=1} j}{2^i}=\frac{1}{2^1}+\frac{1+2}{2^2}+\frac{1+2+3}{2^3}+\frac{1+2+3+4}{2^4}+... $$ [b]p11.[/b] Let $\phi (x)$ be the number of positive integers less than or equal to $x$ that are relatively prime to $x$. Find the sum of all $x$ such that $\phi (\phi(x)) = x -3$. Note that $1$ is relatively prime to every positive integer. [b]p12.[/b] On a piece of paper, Kevin draws a circle. Then, he draws two perpendicular lines. Finally, he draws two perpendicular rays originating from the same point (an $L$ shape). What is the maximum number of sections into which the lines and rays can split the circle? [u]Round 5 [/u] [b]p13.[/b] In quadrilateral $ABCD$, $\angle A = 90^o$, $\angle C = 60^o$, $\angle ABD = 25^o$, and $\angle BDC = 5^o$. Given that $AB = 4\sqrt3$, the area of quadrilateral $ABCD$ can be written as $a\sqrt{b}$. Find $10a +b$. [b]p14.[/b] The value of $$\sum^6_{n=2} \left( \frac{n^4 +1}{n^4 -1}\right) -2 \sum^6_{n=2}\left(\frac{n^3 -n^2+n}{n^4 -1}\right)$$ can be written as $\frac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. Find $100m+n$. [b]p15.[/b] Positive real numbers $x$ and $y$ satisfy the following $2$ equations. $$x^{1+x^{1+x^{1+...}}}= 8$$ $$\sqrt[24]{y +\sqrt[24]{y + \sqrt[24]{y +...}}} = x$$ Find the value of $\lfloor y \rfloor$. PS. You should use hide for answers. Rounds 6-9 have been posted [url=https://artofproblemsolving.com/community/c3h3167130p28823260]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

For an integer $n \geq 3$, let $\mathcal M$ be the set $\{(x, y) | x, y \in \mathbb Z, 1 \leq x \leq n, 1 \leq y \leq n\}$ of points in the plane. What is the maximum possible number of points in a subset $S \subseteq \mathcal M$ which does not contain three distinct points being the vertices of a right triangle?

A plane is cut into unit squares, each of which is colored in black or white. It is known that each rectangle 3 x 4 or 4 x 3 contains exactly 8 white squares. In how many ways can this plane be colored?

[b]p1. [/b] A clock has a long hand for minutes and a short hand for hours. A placement of those hands is [i]natural [/i] if you will see it in a correctly functioning clock. So, having both hands pointing straight up toward $12$ is natural and so is having the long hand pointing toward $6$ and the short hand half-way between $2$ and $3$. A natural placement of the hands is symmetric if you get another natural placement by interchanging the long and short hands. One kind of symmetric natural placement is when the hands are pointed in exactly the same direction. Are there symmetric natural placements of the hands in which the two hands are not pointed in exactly the same direction? If so, describe one such placement. If not, explain why none are possible. [b]p2.[/b] Let $\frac{m}{n}$ be a fraction such that when you write out the decimal expansion of $\frac{m}{n}$ , it eventually ends up with the four digits $2001$ repeated over and over and over. Prove that $101$ divides $n$. [b]p3.[/b] Consider the following two questions: Question $1$: I am thinking of a number between $0$ and $15$. You get to ask me seven yes-or-no questions, and I am allowed to lie at most once in answering your questions. What seven questions can you ask that will always allow you to determine the number? Note: You need to come up with seven questions that are independent of the answers that are received. In other words, you are not allowed to say, "If the answer to question $1$ is yes, then question $2$ is XXX; but if the answer to question $1$ is no, then question $2$ is YYY." Question $2$: Consider the set $S$ of all seven-tuples of zeros and ones. What sixteen elements of $S$ can you choose so that every pair of your chosen seven-tuples differ in at least three coordinates? a. These two questions are closely related. Show that an answer to Question $1$ gives an answer to Question $2$. b. Answer either Question $1$ or Question $2$. [b]p4.[/b] You may wish to use the angle addition formulas for the sine and cosine functions: $\sin (\alpha + \beta) = \sin \alpha \cos \beta + \cos \alpha \sin \beta$ $\cos (\alpha + \beta) = \cos \alpha \cos \beta - \sin \alpha \sin \beta$ a) Prove the identity $(\sin x)(1 + 2 \cos 2x) = \sin (3x)$. b) For any positive integer $n$, prove the identity $$(sin x)(1 + 2 \cos 2x + 2\cos 4x + ... +2\cos 2nx) = \sin ((2n +1)x)$$ [b]p5.[/b] Define the set $\Omega$ in the $xy$-plane as the union of the regions bounded by the three geometric figures: triangle $A$ with vertices $(0.5, 1.5)$, $(1.5, 0.5)$ and $(0.5,-0.5)$, triangle $B$ with vertices $(-0.5,1.5)$, $(-1.5,-0.5)$ and $(-0.5, 0.5)$, and rectangle $C$ with corners $(0.5, 1.0)$, $(-0.5, 1.0)$, $(-0.5,-1.0)$, and $(0.5,-1.0)$. a. Explain how copies of $\Omega$ can be used to cover the $xy$-plane. The copies are obtained by translating $\Omega$ in the $xy$-plane, and copies can intersect only along their edges. b. We can define a transformation of the plane as follows: map any point $(x, y)$ to $(x + G, x + y + G)$, where $G = 1$ if $y < -2x$, $G = -1$ if $y > -2x$, and $G = 0$ if $y = -2x$. Prove that every point in $\Omega$ is transformed into another point in $\Omega$, and that there are at least two points in $\Omega$ that are transformed into the same point. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

An infinite squared sheet is given, with squares of side length $1$. The “distance” between two squares is defined as the length of the shortest path from one of these squares to the other if moving between them like a chess rook (measured along the trajectory of the centre of the rook). Determine the minimum number of colours with which it is possible to colour the sheet (each square being given a single colour) in such a way that each pair of squares with distance between them equal to $6$ units is given different colours. Give an example of such a colouring and prove that using a smaller number of colours we cannot achieve this goal. (AG Pechkovskiy, IV Itenberg)

In every unit square of a$ n \times n$ table ($n \ge 11$) a real number is written, such that the sum of the numbers in any $10 \times 10$ square is positive and the sum of the numbers in any $11\times 11$ square is negative. Determine all possible values for $n$

In order to study a certain ancient language, some researchers formatted its discovered words into expressions formed by concatenating letters from an alphabet containing only two letters. Along the study, they noticed that any two distinct words whose formatted expressions have an equal number of letters, greater than $ 2, $ differ by at least three letters. Prove that if their observation holds indeed, then the number of formatted expressions that have $ n\ge 3 $ letters is at most $ \left[ \frac{2^n}{n+1} \right] . $

There are $m$ boys and $n$ girls participate in a duet singing contest ($m,n\geq 2$). At the contest, each section there will be one show. And a show including some boy-girl duets where each boy-girl couple will sing with each other no more than one song and each participant will sing at least one song. Two show $A$ and $B$ are considered different if there is a boy-girl couple sing at show $A$ but not show $B$. The contest will end if and only if every possible shows are performed, and each show is performed exactly one time. a) A show is called [i]depend[/i] on a participant $X$ if we cancel all duets that $X$ perform, then there will be at least one another participant will not sing any song in that show. Prove that among every shows that depend on $X$, the number of shows with odd number of songs equal to the number of shows with even number of songs. b) Prove that the organizers can arrange the shows in order to make sure that the numbers of songs in two consecutive shows have different parity.