Given a prime $p$ and positive integer $k$, an integer $n$ with $0 \le n < p$ is called a $(p, k)$-Hofstadterian residue if there exists an infinite sequence of integers $n_0, n_1, n_2, \ldots$ such that $n_0 \equiv n$ and $n_{i + 1}^k \equiv n_i \pmod{p}$ for all integers $i \ge 0$. If $f(p, k)$ is the number of $(p, k)$-Hofstadterian residues, then compute $\displaystyle \sum_{k = 1}^{2016} f(2017, k)$. [i]Proposed by Ashwin Sah[/i]

Let be an infinite sequence $ \left( c_n \right)_{n\ge 1} $ of positive real numbers, with $ c_1=1, $ and satisfying $$ c_{n+1}-\frac{1}{c_{n+1}} =c_n+\frac{1}{c_n} , $$ for all natural numbers $ n. $ Prove that: [b]a)[/b] there exists a natural number $ k $ such that the sequence $ \left( c_n^k+\frac{1}{c_n^k} \right)_{n\ge 1} $ is an arithmetic one. [b]b)[/b] there exist two sequences $ \left( u_n \right)_{n\ge 1} ,\left( v_n \right)_{n\ge 1} $ of nonegative integers such that $ c_n=\sqrt{u_n} +\sqrt{v_n} , $ for any natural number $ n. $

[u]Set 7[/u] [b]p19.[/b] Let circles $\omega_1$ and $\omega_2$, with centers $O_1$ and $O_2$, respectively, intersect at $X$ and $Y$ . A lies on $\omega_1$ and $B$ lies on $\omega_2$ such that $AO_1$ and $BO_2$ are both parallel to $XY$, and $A$ and $B$ lie on the same side of $O_1O_2$. If $XY = 60$, $\angle XAY = 45^o$, and $\angle XBY = 30^o$, then the length of $AB$ can be expressed in the form $\sqrt{a - b\sqrt2 + c\sqrt3}$, where $a, b, c$ are positive integers. Determine $a + b + c$. [b]p20.[/b] If $x$ is a positive real number such that $x^{x^2}= 2^{80}$, find the largest integer not greater than $x^3$. [b]p21.[/b] Justin has a bag containing $750$ balls, each colored red or blue. Sneaky Sam takes out a random number of balls and replaces them all with green balls. Sam notices that of the balls left in the bag, there are $15$ more red balls than blue balls. Justin then takes out $500$ of the balls chosen randomly. If $E$ is the expected number of green balls that Justin takes out, determine the greatest integer less than or equal to $E$. [u]Set 8[/u] These three problems are interdependent; each problem statement in this set will use the answers to the other two problems in this set. As such, let the positive integers $A, B, C$ be the answers to problems $22$, $23$, and $24$, respectively, for this set. [b]p22.[/b] Let $WXYZ$ be a rectangle with $WX =\sqrt{5B}$ and $XY =\sqrt{5C}$. Let the midpoint of $XY$ be $M$ and the midpoint of $YZ$ be $N$. If $XN$ and $W Y$ intersect at $P$, determine the area of $MPNY$ . [b]p23.[/b] Positive integers $x, y, z$ satisfy $$xy \equiv A \,\, (mod 5)$$ $$yz \equiv 2A + C\,\, (mod 7)$$ $$zx \equiv C + 3 \,\, (mod 9).$$ (Here, writing $a \equiv b \,\, (mod m)$ is equivalent to writing $m | a - b$.) Given that $3 \nmid x$, $3 \nmid z$, and $9 | y$, find the minimum possible value of the product $xyz$. [b]p24.[/b] Suppose $x$ and $y$ are real numbers such that $$x + y = A$$ $$xy =\frac{1}{36}B^2.$$ Determine $|x - y|$. [u]Set 9[/u] [b]p25. [/b]The integer $2017$ is a prime which can be uniquely represented as the sum of the squares of two positive integers: $$9^2 + 44^2 = 2017.$$ If $N = 2017 \cdot 128$ can be uniquely represented as the sum of the squares of two positive integers $a^2 +b^2$, determine $a + b$. [b]p26.[/b] Chef Celia is planning to unveil her newest creation: a whole-wheat square pyramid filled with maple syrup. She will use a square flatbread with a one meter diagonal and cut out each of the five polygonal faces of the pyramid individually. If each of the triangular faces of the pyramid are to be equilateral triangles, the largest volume of syrup, in cubic meters, that Celia can enclose in her pyramid can be expressed as $\frac{a-\sqrt{b}}{c}$ where $a, b$ and $c$ are the smallest possible possible positive integers. What is $a + b + c$? [b]p27.[/b] In the Cartesian plane, let $\omega$ be the circle centered at $(24, 7)$ with radius $6$. Points $P, Q$, and $R$ are chosen in the plane such that $P$ lies on $\omega$, $Q$ lies on the line $y = x$, and $R$ lies on the $x$-axis. The minimum possible value of $PQ+QR+RP$ can be expressed in the form $\sqrt{m}$ for some integer $m$. Find m. [u]Set 10[/u] [i]Deja vu?[/i] [b]p28. [/b] Let $ABC$ be a triangle with incircle $\omega$. Let $\omega$ intersect sides $BC$, $CA$, $AB$ at $D, E, F$, respectively. Suppose $AB = 7$, $BC = 12$, and $CA = 13$. If the area of $ABC$ is $K$ and the area of $DEF$ is $\frac{m}{n}\cdot K$, where $m$ and $n$ are relatively prime positive integers, then compute $m + n$. [b]p29.[/b] Sebastian is playing the game Split! again, but this time in a three dimensional coordinate system. He begins the game with one token at $(0, 0, 0)$. For each move, he is allowed to select a token on any point $(x, y, z)$ and take it off, replacing it with three tokens, one at $(x + 1, y, z)$, one at $(x, y + 1, z)$, and one at $(x, y, z + 1)$ At the end of the game, for a token on $(a, b, c)$, it is assigned a score $\frac{1}{2^{a+b+c}}$ . These scores are summed for his total score. If the highest total score Sebastian can get in $100$ moves is $m/n$, then determine $m + n$. [b]p30.[/b] Determine the number of positive $6$ digit integers that satisfy the following properties: $\bullet$ All six of their digits are $1, 5, 7$, or $8$, $\bullet$ The sum of all the digits is a multiple of $5$. [u]Set 11[/u] [b]p31.[/b] The triangular numbers are defined as $T_n =\frac{n(n+1)}{2}$. We also define $S_n =\frac{n(n+2)}{3}$. If the sum $$\sum_{i=16}^{32} \left(\frac{1}{T_i}+\frac{1}{S_i}\right)= \left(\frac{1}{T_{16}}+\frac{1}{S_{16}}\right)+\left(\frac{1}{T_{17}}+\frac{1}{S_{17}}\right)+...+\left(\frac{1}{T_{32}}+\frac{1}{S_{32}}\right)$$ can be written in the form $a/b$ , where $a$ and $b$ are positive integers with $gcd(a, b) = 1$, then find $a + b$. [b]p32.[/b] Farmer Will is considering where to build his house in the Cartesian coordinate plane. He wants to build his house on the line $y = x$, but he also has to minimize his travel time for his daily trip to his barnhouse at $(24, 15)$ and back. From his house, he must first travel to the river at $y = 2$ to fetch water for his animals. Then, he heads for his barnhouse, and promptly leaves for the long strip mall at the line $y =\sqrt3 x$ for groceries, before heading home. If he decides to build his house at $(x_0, y_0)$ such that the distance he must travel is minimized, $x_0$ can be written in the form $\frac{a\sqrt{b}-c}{d}$ , where $a, b, c, d$ are positive integers, $b$ is not divisible by the square of a prime, and $gcd(a, c, d) = 1$. Compute $a+b+c+d$. [b]p33.[/b] Determine the greatest positive integer $n$ such that the following two conditions hold: $\bullet$ $n^2$ is the difference of consecutive perfect cubes; $\bullet$ $2n + 287$ is the square of an integer. [u]Set 12[/u] The answers to these problems are nonnegative integers that may exceed $1000000$. You will be awarded points as described in the problems. [b]p34.[/b] The “Collatz sequence” of a positive integer n is the longest sequence of distinct integers $(x_i)_{i\ge 0}$ with $x_0 = n$ and $$x_{n+1} =\begin{cases} \frac{x_n}{2} & if \,\, x_n \,\, is \,\, even \\ 3x_n + 1 & if \,\, x_n \,\, is \,\, odd \end{cases}.$$ It is conjectured that all Collatz sequences have a finite number of elements, terminating at $1$. This has been confirmed via computer program for all numbers up to $2^{64}$. There is a unique positive integer $n < 10^9$ such that its Collatz sequence is longer than the Collatz sequence of any other positive integer less than $10^9$. What is this integer $n$? An estimate of $e$ gives $\max\{\lfloor 32 - \frac{11}{3}\log_{10}(|n - e| + 1)\rfloor, 0\}$ points. [b]p35.[/b] We define a graph $G$ as a set $V (G)$ of vertices and a set $E(G)$ of distinct edges connecting those vertices. A graph $H$ is a subgraph of $G$ if the vertex set $V (H)$ is a subset of $V (G)$ and the edge set $E(H)$ is a subset of $E(G)$. Let $ex(k, H)$ denote the maximum number of edges in a graph with $k$ vertices without a subgraph of $H$. If $K_i$ denotes a complete graph on $i$ vertices, that is, a graph with $i$ vertices and all ${i \choose 2}$ edges between them present, determine $$n =\sum_{i=2}^{2018} ex(2018, K_i).$$ An estimate of $e$ gives $\max\{\lfloor 32 - 3\log_{10}(|n - e| + 1)\rfloor, 0\}$ points. [b]p36.[/b] Write down an integer between $1$ and $100$, inclusive. This number will be denoted as $n_i$ , where your Team ID is $i$. Let $S$ be the set of Team ID’s for all teams that submitted an answer to this problem. For every ordered triple of distinct Team ID’s $(a, b, c)$ such that a, b, c ∈ S, if all roots of the polynomial $x^3 + n_ax^2 + n_bx + n_c$ are real, then the teams with ID’s $a, b, c$ will each receive one virtual banana. If you receive $v_b$ virtual bananas in total and $|S| \ge 3$ teams submit an answer to this problem, you will be awarded $$\left\lfloor \frac{32v_b}{3(|S| - 1)(|S| - 2)}\right\rfloor$$ points for this problem. If $|S| \le 2$, the team(s) that submitted an answer to this problem will receive $32$ points for this problem. PS. You had better use hide for answers. First sets have been posted [url=https://artofproblemsolving.com/community/c4h2777264p24369138]here[/url].Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Sequence of real numbers $a_0,a_1,\dots,a_{1389}$ are called concave if for each $0<i<1389$, $a_i\geq\frac{a_{i-1}+a_{i+1}}2$. Find the largest $c$ such that for every concave sequence of non-negative real numbers: \[\sum_{i=0}^{1389}ia_i^2\geq c\sum_{i=0}^{1389}a_i^2\]

An infinite increasing sequence $a_1 < a_2 < a_3 < \cdots$ of positive integers is called [i]central[/i] if for every positive integer $n$ , the arithmetic mean of the first $a_n$ terms of the sequence is equal to $a_n$. \\Show that there exists an infinite sequence $b_1, b_2, b_3, \dots$ of positive integers such that for every central sequence $a_1, a_2, a_3, \dots, $ there are infinitely many positive integers $n$ with $a_n = b_n$.

[u]Round 4[/u] [b]p13.[/b] What is the units digit of the number $(2^1 + 1)(2^2 - 1)(2^3 + 1)(2^4 - 1)...(2^{2010} - 1)$? [b]p14.[/b] Mr. Fat noted that on January $2$, $2010$, the display of the day is $01/02/2010$, and the sequence $01022010$ is a palindrome (a number that reads the same forwards and backwards). How many days does Mr. Fat need to wait between this palindrome day and the last palindrome day of this decade? [b]p15.[/b] Farmer Tim has a $30$-meter by $30$-meter by $30\sqrt2$-meter triangular barn. He ties his goat to the corner where the two shorter sides meet with a 60-meter rope. What is the area, in square meters, of the land where the goat can graze, given that it cannot get inside the barn? [b]p16.[/b] In triangle $ABC$, $AB = 3$, $BC = 4$, and $CA = 5$. Point $P$ lies inside the triangle and the distances from $P$ to two of the sides of the triangle are $ 1$ and $2$. What is the maximum distance from $P$ to the third side of the triangle? [u]Round 5[/u] [b]p17.[/b] Let $Z$ be the answer to the third question on this guts quadruplet. If $x^2 - 2x = Z - 1$, find the positive value of $x$. [b]p18.[/b] Let $X$ be the answer to the first question on this guts quadruplet. To make a FATRON2012, a cubical steel body as large as possible is cut out from a solid sphere of diameter $X$. A TAFTRON2013 is created by cutting a FATRON2012 into $27$ identical cubes, with no material wasted. What is the length of one edge of a TAFTRON2013? [b]p19.[/b] Let $Y$ be the smallest integer greater than the answer to the second question on this guts quadruplet. Fred posts two distinguishable sheets on the wall. Then, $Y$ people walk into the room. Each of the Y people signs up on $0, 1$, or $2$ of the sheets. Given that there are at least two people in the room other than Fred, how many possible pairs of lists can Fred have? [b]p20.[/b] Let $A, B, C$, be the respective answers to the first, second, and third questions on this guts quadruplet. At the Robot Design Convention and Showcase, a series of robots are programmed such that each robot shakes hands exactly once with every other robot of the same height. If the heights of the $16$ robots are $4$, $4$, $4$, $5$, $5$, $7$, $17$, $17$, $17$, $34$, $34$, $42$, $100$, $A$, $B$, and $C$ feet, how many handshakes will take place? [u]Round 6[/u] [b]p21.[/b] Determine the number of ordered triples $(p, q, r)$ of primes with $1 < p < q < r < 100$ such that $q - p = r - q$. [b]p22.[/b] For numbers $a, b, c, d$ such that $0 \le a, b, c, d \le 10$, find the minimum value of $ab + bc + cd + da - 5a - 5b - 5c - 5d$. [b]p23.[/b] Daniel has a task to measure $1$ gram, $2$ grams, $3$ grams, $4$ grams , ... , all the way up to $n$ grams. He goes into a store and buys a scale and six weights of his choosing (so that he knows the value for each weight that he buys). If he can place the weights on either side of the scale, what is the maximum value of $n$? [b]p24.[/b] Given a Rubik’s cube, what is the probability that at least one face will remain unchanged after a random sequence of three moves? (A Rubik’s cube is a $3$ by $3$ by $3$ cube with each face starting as a different color. The faces ($3$ by $3$) can be freely turned. A move is defined in this problem as a $90$ degree rotation of one face either clockwise or counter-clockwise. The center square on each face–six in total–is fixed.) PS. You should use hide for answers. First rounds have been posted [url=https://artofproblemsolving.com/community/c4h2766534p24230616]here[/url]. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

[b]p1.[/b] It’s currently $6:00$ on a $12$ hour clock. What time will be shown on the clock $100$ hours from now? Express your answer in the form hh : mm. [b]p2.[/b] A tub originally contains $10$ gallons of water. Alex adds some water, increasing the amount of water by 20%. Barbara, unhappy with Alex’s decision, decides to remove $20\%$ of the water currently in the tub. How much water, in gallons, is left in the tub? Express your answer as an exact decimal. [b]p3.[/b] There are $2000$ math students and $4000$ CS students at Berkeley. If $5580$ students are either math students or CS students, then how many of them are studying both math and CS? [b]p4.[/b] Determine the smallest integer $x$ greater than $1$ such that $x^2$ is one more than a multiple of $7$. [b]p5.[/b] Find two positive integers $x, y$ greater than $1$ whose product equals the following sum: $$9 + 11 + 13 + 15 + 17 + 19 + 21 + 23 + 25 + 27 + 29.$$ Express your answer as an ordered pair $(x, y)$ with $x \le y$. [b]p6.[/b] The average walking speed of a cow is $5$ meters per hour. If it takes the cow an entire day to walk around the edges of a perfect square, then determine the area (in square meters) of this square. [b]p7.[/b] Consider the cube below. If the length of the diagonal $AB$ is $3\sqrt3$, determine the volume of the cube. [img]https://cdn.artofproblemsolving.com/attachments/4/d/3a6fdf587c12f2e4637a029f38444914e161ac.png[/img] [b]p8.[/b] I have $18$ socks in my drawer, $6$ colored red, $8$ colored blue and $4$ colored green. If I close my eyes and grab a bunch of socks, how many socks must I grab to guarantee there will be two pairs of matching socks? [b]p9.[/b] Define the operation $a @ b$ to be $3 + ab + a + 2b$. There exists a number $x$ such that $x @ b = 1$ for all $b$. Find $x$. [b]p10.[/b] Compute the units digit of $2017^{(2017^2)}$. [b]p11.[/b] The distinct rational numbers $-\sqrt{-x}$, $x$, and $-x$ form an arithmetic sequence in that order. Determine the value of $x$. [b]p12.[/b] Let $y = x^2 + bx + c$ be a quadratic function that has only one root. If $b$ is positive, find $\frac{b+2}{\sqrt{c}+1}$. [b]p13.[/b] Alice, Bob, and four other people sit themselves around a circular table. What is the probability that Alice does not sit to the left or right of Bob? [b]p14.[/b] Let $f(x) = |x - 8|$. Let $p$ be the sum of all the values of $x$ such that $f(f(f(x))) = 2$ and $q$ be the minimum solution to $f(f(f(x))) = 2$. Compute $p \cdot q$. [b]p15.[/b] Determine the total number of rectangles ($1 \times 1$, $1 \times 2$, $2 \times 2$, etc.) formed by the lines in the figure below: $ \begin{tabular}{ | l | c | c | r| } \hline & & & \\ \hline & & & \\ \hline & & & \\ \hline & & & \\ \hline \end{tabular} $ [b]p16.[/b] Take a square $ABCD$ of side length $1$, and let $P$ be the midpoint of $AB$. Fold the square so that point $D$ touches $P$, and let the intersection of the bottom edge $DC$ with the right edge be $Q$. What is $BQ$? [img]https://cdn.artofproblemsolving.com/attachments/1/1/aeed2c501e34a40a8a786f6bb60922b614a36d.png[/img] [b]p17.[/b] Let $A$, $B$, and $k$ be integers, where $k$ is positive and the greatest common divisor of $A$, $B$, and $k$ is $1$. Define $x\# y$ by the formula $x\# y = \frac{Ax+By}{kxy}$ . If $8\# 4 = \frac12$ and $3\# 1 = \frac{13}{6}$ , determine the sum $A + B + k$. [b]p18.[/b] There are $20$ indistinguishable balls to be placed into bins $A$, $B$, $C$, $D$, and $E$. Each bin must have at least $2$ balls inside of it. How many ways can the balls be placed into the bins, if each ball must be placed in a bin? [b]p19.[/b] Let $T_i$ be a sequence of equilateral triangles such that (a) $T_1$ is an equilateral triangle with side length 1. (b) $T_{i+1}$ is inscribed in the circle inscribed in triangle $T_i$ for $i \ge 1$. Find $$\sum^{\infty}_{i=1} Area (T_i).$$ [b]p20.[/b] A [i]gorgeous [/i] sequence is a sequence of $1$’s and $0$’s such that there are no consecutive $1$’s. For instance, the set of all gorgeous sequences of length $3$ is $\{[1, 0, 0]$,$ [1, 0, 1]$, $[0, 1, 0]$, $[0, 0, 1]$, $[0, 0, 0]\}$. Determine the number of gorgeous sequences of length $7$. PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Given any integer $m>1$ prove that there exist infinitely many positive integers $n$ such that the last $m$ digits of $5^n$ are a sequence $a_m,a_{m-1},\ldots ,a_1=5\ (0\le a_j<10)$ in which each digit except the last is of opposite parity to its successor (i.e., if $a_i$ is even, then $a_{i-1}$ is odd, and if $a_i$ is odd, then $a_{i-1}$ is even).

If the terms of a sequence $a_{1}, a_{2}, \ldots$ are monotonic, and if $\sum_{n=1}^{\infty} a_n$ converges, show that $\sum_{n=1}^{\infty} n(a_{n} -a_{n+1 })$ converges.

Determine the maximum number of three-term arithmetic progressions which can be chosen from a sequence of $n$ real numbers \[a_1<a_2<\cdots<a_n.\]

Let $a_0$, $a_1$, $a_2$, ... be an infinite sequence of real numbers satisfying the equation $a_n=\left|a_{n+1}-a_{n+2}\right|$ for all $n\geq 0$, where $a_0$ and $a_1$ are two different positive reals. Can this sequence $a_0$, $a_1$, $a_2$, ... be bounded? [i]Proposed by Mihai Bălună, Romania[/i]

Fix a nonnegative integer $a_0$ to define a sequence of integers $a_0,a_1,\ldots$ by letting $a_k,k\geq 1$ be the smallest integer (strictly) greater than $a_{k-1}$ making $a_{k-1}+a_k{}$ into a perfect square. Let $S{}$ be the set of positive integers not expressible as the difference of two terms of the sequence $(a_k)_{k\geq 0}.$ Prove that $S$ is finite and determine its size in terms of $a_0.$

Given that $\{a_n\}$ is a sequence of integers satisfying the following condition for all positive integral values of $n$: $a_n+a_{n+1}=2a_{n+2}a_{n+3}+2016$. Find all possible values of $a_1$ and $a_2$

Jim starts with a positive integer $ n$ and creates a sequence of numbers. Each successive number is obtained by subtracting the largest possible integer square less than or equal to the current number until zero is reached. For example, if Jim starts with $ n=55$, then his sequence contains $ 5$ numbers: \begin{align*} &55\\ 55-7^2=&\ 6\\ 6-2^2=&\ 2\\ 2-1^2=&\ 1\\ 1-1^2=&\ 0 \end{align*}Let $ N$ be the smallest number for which Jim's sequence has 8 numbers. What is the units digit of $ N$? $ \textbf{(A)}\ 1 \qquad \textbf{(B)}\ 3 \qquad \textbf{(C)}\ 5 \qquad \textbf{(D)}\ 7 \qquad \textbf{(E)}\ 9$

Find all reals $a$ such that the sequence $\{x(n)\}$, $n=0,1,2, \ldots$ that satisfy: $x(0)=1996$ and $x_{n+1} = \frac{a}{1+x(n)^2}$ for any natural number $n$ has a limit as n goes to infinity.