We number both the rows and the columns of an $8 \times 8$ chessboard with the numbers $1$ to $8$. Some grains of rice are placed on each square, in such a way that the number of grains on each square is equal to the product of the row and column numbers of the square. How many grains of rice are there on the entire chessboard?

If $n$ is a positive integer such that $8n+1$ is a perfect square, then $\textbf{(A)}~n\text{ must be odd}$ $\textbf{(B)}~n\text{ cannot be a perfect square}$ $\textbf{(C)}~n\text{ cannot be a perfect square}$ $\textbf{(D)}~\text{None of the above}$

[u]Round 6 [/u] [b]p16.[/b] Let $a$ be a solution to $x^3 -x +1 = 0$. Find $a^6 -a^2 +2a$. [b]p17.[/b] For a positive integer $n$, $\phi (n)$ is the number of positive integers less than $n$ that are relatively prime to $n$. Compute the sum of all $n$ for which $\phi (n) = 24$. [b]p18.[/b] Let $x$ be a positive integer such that $x^2 \equiv 57$ (mod $59$). Find the least possible value of $x$. [u]Round 7[/u] [b]p19.[/b] In the diagram below, find the number of ways to color each vertex red, green, yellow or blue such that no two vertices of a triangle have the same color. [img]https://cdn.artofproblemsolving.com/attachments/1/e/01418af242c7e2c095a53dd23e997b8d1f3686.png[/img] [b]p20.[/b] In a set with $n$ elements, the sum of the number of ways to choose $3$ or $4$ elements is a multiple of the sumof the number of ways to choose $1$ or $2$ elements. Find the number of possible values of $n$ between $4$ and $120$ inclusive. [b]p21.[/b] In unit square $ABCD$, let $\Gamma$ be the locus of points $P$ in the interior of $ABCD$ such that $2AP < BP$. The area of $\Gamma$ can be written as $\frac{a\pi +b\sqrt{c}}{d}$ for integers $a,b,c,d$ with $c$ squarefree and $gcd(a,b,d) = 1$. Find $1000000a +10000b +100c +d$. [u]Round 8 [/u] [b]p22.[/b] Ephram, GammaZero, and Orz walk into a bar. Each write some permutation of the letters “LMT” once, then concatenate their permutations one after the other (i.e. LTMTLMTLM would be a possible string, but not LLLMMMTTT). Suppose that the probability that the string “LMT” appears in that order among the new $9$-character string can be written as $\frac{A}{B}$ for relatively prime positive integers $A$ and $B$. Find $1000A+B$. [b]p23.[/b] In $\vartriangle ABC$ with side lengths $AB = 27$, $BC = 35$, and $C A = 32$, let $D$ be the point at which the incircle is tangent to $BC$. The value of $\frac{\sin \angle C AD }{\sin\angle B AD}$ can be expressed as $\frac{A}{B}$ for relatively prime positive integers $A$ and $B$. Find $1000A+B$. [b]p24.[/b] Let $A$ be the greatest possible area of a square contained in a regular hexagon with side length $1$. Let B be the least possible area of a square that contains a regular hexagon with side length $1$. The value of $B-A$ can be expressed as $a\sqrt{b}-c$ for positive integers $a$, $b$, and $c$ with $b$ squarefree. Find $10000a +100b +c$. [u]Round 9[/u] [b]p25.[/b] Estimate how many days before today this problem was written. If your estimation is $E$ and the actual answer is $A$, you will receive $\max \left( \left \lfloor 10 - \left| \frac{E-A}{2} \right| \right \rfloor , 0 \right)$ points. [b]p26.[/b] Circle $\omega_1$ is inscribed in unit square $ABCD$. For every integer $1 < n \le 10,000$, $\omega_n$ is defined as the largest circle which can be drawn inside $ABCD$ that does not overlap the interior of any of $\omega_1$,$\omega_2$, $...$,$\omega_{n-1}$ (If there are multiple such $\omega_n$ that can be drawn, one is chosen at random). Let r be the radius of ω10,000. Estimate $\frac{1}{r}$ . If your estimation is $E$ and the actual answer is $A$, you will receive $\max \left( \left \lfloor 10 - \left| \frac{E-A}{200} \right| \right \rfloor , 0 \right)$ points. [b]p27.[/b] Answer with a positive integer less than or equal to $20$. We will compare your response with the response of every other team that answered this problem. When two equal responses are compared, neither team wins. When two unequal responses $A > B$ are compared, $A$ wins if $B | A$, and $B$ wins otherwise. If your team wins n times, you will receive $\left \lfloor \frac{n}{2} \right \rfloor$ points. PS. You should use hide for answers. Rounds 1-5 have been posted [url=https://artofproblemsolving.com/community/c3h3167135p28823324]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Find all positive integers $n$ such that $$\phi(n) + \sigma(n) = 2n + 8.$$

Let each of the vertices of a regular $9$-gon (polygon of 9 equal sides and equal angles) be coloured black or white . $(a).$ Show that there are two adjacent verices of same colour. $(b).$ Show there are three vertices of the same colour forming an isosceles triangle.

Let $S = \{A_1,A_2,\ldots ,A_k\}$ be a collection of subsets of an $n$-element set $A$. If for any two elements $x, y \in A$ there is a subset $A_i \in S$ containing exactly one of the two elements $x$, $y$, prove that $2^k\geq n$. [i]Yugoslavia[/i]

Let $S$ be a set of positive real numbers with five elements such that for any distinct $a,~ b,~ c$ in $S$, the number $ab + bc + ca$ is rational. Prove that for any $a$ and $b$ in $S$, $\tfrac{a}{b}$ is a rational number.

Find all functions $f:\mathbb{Z} \rightarrow \mathbb{Z}$ such that $$f(x+f(y+1))+f(xy)=f(x+1)(f(y)+1)$$ for any $x,y$ integers.

Each of the three large squares shown below is the same size. Segments that intersect the sides of the squares intersect at the midpoints of the sides. How do the shaded areas of these squares compare? [asy] unitsize(36); fill((0,0)--(1,0)--(1,1)--cycle,gray); fill((1,1)--(1,2)--(2,2)--cycle,gray); draw((0,0)--(2,0)--(2,2)--(0,2)--cycle); draw((1,0)--(1,2)); draw((0,0)--(2,2)); fill((3,1)--(4,1)--(4,2)--(3,2)--cycle,gray); draw((3,0)--(5,0)--(5,2)--(3,2)--cycle); draw((4,0)--(4,2)); draw((3,1)--(5,1)); fill((6,1)--(6.5,0.5)--(7,1)--(7.5,0.5)--(8,1)--(7.5,1.5)--(7,1)--(6.5,1.5)--cycle,gray); draw((6,0)--(8,0)--(8,2)--(6,2)--cycle); draw((6,0)--(8,2)); draw((6,2)--(8,0)); draw((7,0)--(6,1)--(7,2)--(8,1)--cycle); label("$I$",(1,2),N); label("$II$",(4,2),N); label("$III$",(7,2),N); [/asy] $\text{(A)}\ \text{The shaded areas in all three are equal.}$ $\text{(B)}\ \text{Only the shaded areas of }I\text{ and }II\text{ are equal.}$ $\text{(C)}\ \text{Only the shaded areas of }I\text{ and }III\text{ are equal.}$ $\text{(D)}\ \text{Only the shaded areas of }II\text{ and }III\text{ are equal.}$ $\text{(E)}\ \text{The shaded areas of }I, II\text{ and }III\text{ are all different.}$

Two different points $A, M$ are given in a plane, $AM = d > 0$. Let a number $v > 0$ be given. Construct a rhombus $ABCD$ with the height of length $v$ and $M$ being a midpoint of $BC$. Discuss conditions of solvability and determine number of solutions. Can the resulting quadrilateral $ABCD$ be a square?

On the sides (excluding its endpoints) $ AB,BC,CD,DA $ of a parallelogram consider the points $ M,N,P,Q, $ respectively, such that $ \overrightarrow{AP} +\overrightarrow{AN} +\overrightarrow{CQ} +\overrightarrow{CM} = 0. $ Show that $ QN, PM,AC $ are concurrent. [i]Adrian Ivan[/i]

We play a game. The pot starts at $\$0$. On every turn, you flip a fair coin. If you flip heads, I add $\$100$ to the pot. If you flip tails, I take all of the money out of the pot, and you are assessed a "strike". You can stop the game before any flip and collect the contents of the pot, but if you get 3 strikes, the game is over and you win nothing. Find, with proof, the expected value of your winnings if you follow an optimal strategy.

In a triangle $ABC$ let $E$ be the midpoint of the side $AC$ and $F$ the midpoint of the side $BC$. Let $G$ be the foot of the perpendicular from $C$ to $ AB$. Show that $\vartriangle EFG$ is isosceles if and only if $\vartriangle ABC$ is isosceles.

For every positive integer $ n$, let $ \phi(n)$ denotes the number of positive integers less than $ n$ that is relatively prime to $ n$ and $ \tau(n)$ denote the sum of all positive divisors of $ n$. Let $ n$ be a positive integer such that $ \phi(n)|n\minus{}1$ and that $ n$ is not a prime number. Prove that $ \tau(n)>2009$.

Let $ABCD$ be a convex quadrilateral, and write $\alpha=\angle DAB$, $\beta=\angle ADB$, $\gamma=\angle ACB$, $\delta= \angle DBC$ and $\epsilon=\angle DBA$. Assuming that $\alpha<\pi/2$, $\beta+\gamma=\pi /2$, and $\delta+2\epsilon=\pi$, prove that $(DB+BC)^2=AD^2+AC^2$.

Let $ S$ be a set of all positive integers which can be represented as $ a^2 \plus{} 5b^2$ for some integers $ a,b$ such that $ a\bot b$. Let $ p$ be a prime number such that $ p \equal{} 4n \plus{} 3$ for some integer $ n$. Show that if for some positive integer $ k$ the number $ kp$ is in $ S$, then $ 2p$ is in $ S$ as well. Here, the notation $ a\bot b$ means that the integers $ a$ and $ b$ are coprime.

The King gives the following task to his two wizards. The First Wizard should choose $7$ distinct positive integers with total sum $100$ and secretly submit them to the King. To the Second Wizard he should tell only the fourth largest number. The Second Wizard must figure out all the chosen numbers. Can the wizards succeed for sure? The wizards cannot discuss their strategy beforehand. (Mikhail Evdokimov)

Prinstan Trollner and Dukejukem are competing at the game show WASS. Both players spin a wheel which chooses an integer from $1$ to $50$ uniformly at random, and this number becomes their score. Dukejukem then flips a weighted coin that lands heads with probability $\tfrac{3}{5}$. If he flips heads, he adds $1$ to his score. A player wins the game if their score is higher than the other player's score. A player wins the game if their score is higher than the other player's score. The probability Dukejukem defeats the Trollner to win WASS equals $\tfrac{m}{n}$ where $m$ and $n$ are coprime positive integers. Computer $m+n$.

For every $m \geq 2$, let $Q(m)$ be the least positive integer with the following property: For every $n \geq Q(m)$, there is always a perfect cube $k^3$ in the range $n < k^3 \leq m \cdot n$. Find the remainder when \[ \sum_{m = 2}^{2017} Q(m) \] is divided by 1000.

The Integration Premier League has $n$ teams competing. The tournament follows a round-robin system, that is, where every pair of teams play each other exactly once. So every team plays exactly $n-1$ matches. The top $m \leq n$ temas at the end of the tournament qualify for the playoffs. Assume there are no tied matches. Let $A(m,n)$ be the minimum number of matches a team has to win to gurantee selection for the playoffs, regardless of what their run rate is. For example, $A(n,n) = 0$ (everyone qualifies anyway so no need to win!) and $A(1,n) = n-1$ (even if you lose to just one other team, they might defeat everyone and qualify instead of you). Answer the following: $(A)$ FInd the value of $A(2,4),A(2,6)$ and $A(4,10)$ with proof (explain why a smaller value can still lead to the team not qualifying, and show that the respective values themselves are enough). $(B)$ Show that $A(n-1,n) = \frac{n}{2}$ when $n$ even and $ = \frac{n+1}{2}$ when $n$ odd. $(C)$ For bonus marks, try to find a general pattern for $A(m,n)$.

Find the maximum value of the expression $ x+y+z, $ where $ x,y,z $ are real numbers satisfying $$ \left\{ \begin{matrix} x^2+yz\le 2 \\y^2+zx\le 2\\ z^2+xy\le 2 \end{matrix} \right. . $$

In a company of people some pairs are enemies. A group of people is called [i]unsociable[/i] if the number of members in the group is odd and at least $3$, and it is possible to arrange all its members around a round table so that every two neighbors are enemies. Given that there are at most $2015$ unsociable groups, prove that it is possible to partition the company into $11$ parts so that no two enemies are in the same part. [i]Proposed by Russia[/i]

Three cats--TheInnocentKitten, TheNeutralKitten, and TheGuiltyKitten labelled $P_1, P_2,$ and $P_3$ respectively with $P_{n+3} = P_{n}$--are playing a game with three rounds as follows: [list=1] [*] Each round has three turns. For round $r \in \{1,2,3\}$ and turn $t \in \{1,2,3\}$ in that round, player $P_{t+1-r}$ picks a non-negative integer. The turns in each round occur in increasing order of $t$, and the rounds occur in increasing order of $r$. $\newline \newline$ [*] [b]Motivations:[/b] Every player focuses primarily on maximizing the sum of their own choices and secondarily on minimizing the total of the other players’ sums. TheNeutralKitten and TheGuiltyKitten have the additional tertiary priority of minimizing TheInnocentKitten’s sum. $\newline \newline$ [*] For round $2$, player $P_{2}$ has no choice but to pick the number equal to what player $P_{1}$ chose in round $1$. Likewise, for round $3$, player $P_{3}$ must pick the number equal to what player $P_{2}$ chose in round $2$. $\newline \newline$ [*] If not all three players choose their numbers such that the values they chose in rounds 1,2,3 form an arithmetic progression in that order by the end of the game, all players' sums are set to $-1$ regardless of what they have chosen. $\newline \newline$ [*] If the sum of the choices in any given round is greater than $100$, all choices that round are set to $0$ at the end of that round. That is, rules $2$, $3$, and $4$ act as if each player chose $0$ that round. $\newline \newline$ [*] All players play optimally as per their motivations. Furthermore, all players know that all other players will play optimally (and so on.) [/list] Let $A$ and $B$ be TheInnocentKitten's sum and TheGuiltyKitten's sum respectively. Compute $1000A + B$ when all players play optimally. Proposed by Harry Chen (Extile)

At the math contest each participant met at least $3$ pals who he/she already knew. Prove that the Jury can choose an even number of participants (more than two) and arrange them around a table so that each participant be set between these who he/she knows.

Six children stand in a line outside their classroom. When they enter the classroom, they sit in a circle in random order. There are relatively prime positive integers $m$ and $n$ so that $\tfrac{m}{n}$ is the probability that no two children who stood next to each other in the line end up sitting next to each other in the circle. Find $m + n$.