HMMT 2011

Alice and Barbara play a game on a blackboard. At the start, zero is written on the board. Alice goes first, and the players alternate turns. On her turn, each player replaces $x$ - the number written on the board - with any real number $y$, subject to the constraint that $0<y-x<1$. (a) [10] If the first player to write a number greater than or equal to 2010 wins, determine, with proof, who has the winning strategy. (b) [10] If the first player to write a number greater than or equal to 2010 on her 2011th turn or later wins (if a player writes a number greater than or equal to 2010 on her 2010th turn or earlier, she loses immediately), determine, with proof, who has the winning strategy.

Rachel and Brian are playing a game in a grid with 1 row of 2011 squares. Initially, there is one white checker in each of the first two squares from the left, and one black checker in the third square from the left. At each stage, Rachel can choose to either run or fight. If Rachel runs, she moves the black checker 1 unit to the right, and Brian moves each of the white checkers one unit to the right. If Rachel chooses to fight, she pushes the checker immediately to the left of the black checker 1 unit to the left, the black checker is moved 1 unit to the right, and Brian places a new white checker in the cell immediately to the left of the black one. The game ends when the black checker reaches the last cell. How many different final configurations are possible?

Let $n$ be a positive integer, and let $a_{1}, a_{2}, \ldots, a_{n}$ be a set of positive integers such that $a_{1}=2$ and $a_{m}=\varphi\left(a_{m+1}\right)$ for all $1 \leq m \leq n-1$, where, for all positive integers $k, \varphi(k)$ denotes the number of positive integers less than or equal to $k$ that are relatively prime to $k$. Prove that $a_{n} \geq 2^{n-1}$.

Let $a, b$, and $c$ be complex numbers such that $|a|=|b|=|c|=|a+b+c|=1$. If $|a-b|=|a-c|$ and $b \neq c$, prove that $|a+b||a+c|=2$.

Let $a$ and $b$ be positive real numbers. Define two sequences of real numbers $\left\{a_{n}\right\}$ and $\left\{b_{n}\right\}$ for all positive integers $n$ by $(a+b i)^{n}=a_{n}+b_{n} i$. Prove that

$$\frac{\left|a_{n+1}\right|+\left|b_{n+1}\right|}{\left|a_{n}\right|+\left|b_{n}\right|} \geq \frac{a^{2}+b^{2}}{a+b}$$

for all positive integers $n$.

Prove that whenever the player must choose the side of a coin, the optimal strategy is to choose heads if more coins have been determined tails than heads and to choose tails if more coins have been determined heads than tails.

Let $T$ denote the number of coins determined tails and $H$ denote the number of coins determined heads at the end of the game. Let $p_{m}(k)$ be the probability that $|T-H|=k$ after a game with $4 m$ coins, assuming that the player follows the optimal strategy outlined in problem 6. Clearly $p_{m}(k)=0$ if $k$ is an odd integer, so we need only consider the case when $k$ is an even integer. (By definition, $p_{0}(0)=1$ and $p_{0}(k)=0$ for $\left.k \geq 1\right)$. Prove that $p_{m}(0) \geq p_{m+1}(0)$ for all nonnegative integers $m$.

(a) [5] Find $a_{1}, a_{2}$, and $a_{3}$, so that the following equation holds for all $m \geq 1$ :

$$p_{m}(0)=a_{1} p_{m-1}(0)+a_{2} p_{m-1}(2)+a_{3} p_{m-1}(4)$$

(b) [5] Find $b_{1}, b_{2}, b_{3}$, and $b_{4}$, so that the following equation holds for all $m \geq 1$ :

$$p_{m}(2)=b_{1} p_{m-1}(0)+b_{2} p_{m-1}(2)+b_{3} p_{m-1}(4)+b_{4} p_{m-1}(6)$$

(c) [5] Find $c_{1}, c_{2}, c_{3}$, and $c_{4}$, so that the following equation holds for all $m \geq 1$ and $j \geq 2$ :

$$p_{m}(2 j)=c_{1} p_{m-1}(2 j-2)+c_{2} p_{m-1}(2 j)+c_{3} p_{m-1}(2 j+2)+c_{4} p_{m-1}(2 j+4)$$

We would now like to examine the behavior of $p_{m}(k)$ as $m$ becomes arbitrarily large; specifically, we would like to discern whether $\lim _{m \rightarrow \infty} p_{m}(0)$ exists and, if it does, to determine its value. Let $\lim _{m \rightarrow \infty} p_{m}(k)=A_{k}$. (a) [5] Prove that $\frac{2}{3} p_{m}(k) \geq p_{m}(k+2)$ for all $m$ and $k$. (b) [10] Prove that $A_{0}$ exists and that $A_{0}>0$. Feel free to assume the result of analysis that a non-increasing sequence of real numbers that is bounded below by a constant converges to a limit that is greater than or equal to $c$.

Once it has been demonstrated that $\lim _{n \rightarrow \infty} p_{n}(0)$ exists and is greater than 0 , it follows that $\lim _{n \rightarrow \infty} p_{n}(k)$ exists and is greater than 0 for all even positive integers $k$ and that $\sum_{k=0}^{\infty} A_{2 k}=1$. It also follows that $A_{0}=a_{1} A_{0}+a_{2} A_{2}+a_{3} A_{4}, A_{2}=b_{1} A_{0}+b_{2} A_{2}+b_{3} A_{4}+b_{4} A_{6}$, and $A_{2 j}=c_{1} A_{2 j-2}+c_{2} A_{2 j}+$ $c_{3} A_{2 j+2}+c_{4} A_{2 j+4}$ for all positive integers $j \geq 2$, where $a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}, b_{4}$, and $c_{1}, c_{2}, c_{3}, c_{4}$ are the constants you found in problem 8. Assuming these results, determine, with proof, the value of $A_{0}$.

Let $A B C$ be a non-isosceles, non-right triangle, let $\omega$ be its circumcircle, and let $O$ be its circumcenter. Let $M$ be the midpoint of segment $B C$. Let the circumcircle of triangle $A O M$ intersect $\omega$ again at $D$. If $H$ is the orthocenter of triangle $A B C$, prove that $\angle D A H=\angle M A O$.

Let $A B C$ be a triangle, and let $E$ and $F$ be the feet of the altitudes from $B$ and $C$, respectively. If $A$ is not a right angle, prove that the circumcenter of triangle $A E F$ lies on the incircle of triangle $A B C$ if and only if the incenter of triangle $A B C$ lies on the circumcircle of triangle $A E F$.

Given positive integers $a$ and $b$ such that $a>b$, define a sequence of ordered pairs $\left(a_{l}, b_{l}\right)$ for nonnegative integers $l$ by $a_{0}=a, b_{0}=b$, and $\left(a_{l+1}, b_{l+1}\right)=\left(b_{l}, a_{l} \bmod b_{l}\right)$, where, for all positive integers $x$ and $y, x \bmod y$ is defined to be the remainder left by $x$ upon division by $y$. Define $f(a, b)$ to be the smallest positive integer $j$ such that $b_{j}=0$. Given a positive integer $n$, define $g(n)$ to be $\max _{1 \leq k \leq n-1} f(n, k)$. (a) [15] Given a positive integer $m$, what is the smallest positive integer $n_{m}$ such that $g\left(n_{m}\right)=m$ ? (b) [15] What is the second smallest?

Given a positive integer $n$, a sequence of integers $a_{1}, a_{2}, \ldots, a_{r}$, where $0 \leq a_{i} \leq k$ for all $1 \leq i \leq r$, is said to be a " $k$-representation" of $n$ if there exists an integer $c$ such that

$$\sum_{i=1}^{r} a_{i}=\sum_{i=1}^{r} a_{i} k^{c-i}=n .$$

Prove that every positive integer $n$ has a $k$-representation, and that the $k$-representation is unique if and only if 0 does not appear in the base- $k$ representation of $n-1$.

Denote $\{1,2, \ldots, n\}$ by $[n]$, and let $S$ be the set of all permutations of [ $n$ ]. Call a subset $T$ of $S$ good if every permutation $\sigma$ in $S$ may be written as $t_{1} t_{2}$ for elements $t_{1}$ and $t_{2}$ of $T$, where the product of two permutations is defined to be their composition. Call a subset of $U$ of $S$ extremely good if every permutation $\sigma$ in $S$ may be written as $s^{-1} u s$ for elements $s$ of $S$ and $u$ of $U$. Let $\tau$ be the smallest value of $|T| /|S|$ for all good subsets $T$, and let $v$ be the smallest value of $|U| /|S|$ for all extremely good subsets $U$. Prove that $\sqrt{v} \geq \tau$.

Tom, Dick, and Harry play a game in which they each pick an integer between 1 and 2011. Tom picks a number first and informs Dick and Harry of his choice. Then Dick picks a different number and informs Harry of his choice. Finally, Harry picks a number different from both Tom's and Dick's. After all the picks are complete, an integer is randomly selected between 1 and 2011. The player whose number is closest wins 2 dollars, unless there is a tie, in which case each of the tied players wins 1 dollar. If Tom knows that Dick and Harry will each play optimally and select randomly among equally optimal choices, there are two numbers Tom can pick to maximize his expected profit; what are they?

Let $a, b$, and $c$ be complex numbers such that $|a|=|b|=|c|=|a+b+c|=1$. If $|a-b|=|a-c|$ and $b \neq c$, evaluate $|a+b||a+c|$.

Let $x$ and $y$ be complex numbers such that $|x|=|y|=1$. (a) [15] Determine the maximum value of $|1+x|+|1+y|-|1+x y|$. (b) [15] Determine the maximum value of $|1+x|+|1+x y|+\left|1+x y^{2}\right|+\ldots+\left|1+x y^{2011}\right|-1006|1+y|$.

Let $a, b$, and $c$ be complex numbers such that $|a|=|b|=|c|=1$. If

$$\frac{a^{2}}{b c}+\frac{b^{2}}{c a}+\frac{c^{2}}{a b}=1$$

as well, determine the product of all possible values of $|a+b+c|$.

(a) [20] Alice and Barbara play a game on a blackboard. At the start, zero is written on the board. The players alternate turns. On her turn, each player replaces $x$ - the number written on the board - with any real number $y$, subject to the constraint that $0<y-x<1$. The first player to write a number greater than or equal to 2010 wins. If Alice goes first, determine, with proof, who has the winning strategy. (b) [20] Alice and Barbara play a game on a blackboard. At the start, zero is written on the board. The players alternate turns. On her turn, each player replaces $x$ - the number written on the board - with any real number $y$, subject to the constraint that $y-x \in(0,1)$. The first player to write a number greater than or equal to 2010 on her 2011th turn or later wins. If a player writes a number greater than or equal to 2010 on her 2010th turn or before, she loses immediately. If Alice goes first, determine, with proof, who has the winning strategy.

Let $n$ be a positive integer such that $n>2$. Prove that $\varphi(n)$ is even.

Let $n$ be an even positive integer. Prove that $\varphi(n) \leq \frac{n}{2}$.

Let $n$ be a positive integer, and let $a_{1}, a_{2}, \ldots, a_{n}$ be a set of positive integers such that $a_{1}=2$ and $a_{m}=\varphi\left(a_{m+1}\right)$ for all $1 \leq m \leq n-1$. Prove that $a_{n} \geq 2^{n-1}$.

Let $A B C$ be a non-isosceles, non-right triangle, let $\omega$ be its circumcircle, and let $O$ be its circumcenter. Let $M$ be the midpoint of segment $B C$. Let the tangents to $\omega$ at $B$ and $C$ intersect at $X$. Prove that $\angle O A M=\angle O X A$. (Hint: use SAS similarity).

Let the circumcircle of triangle $A O M$ intersect $\omega$ again at $D$. Prove that points $A, D$, and $X$ are collinear.

Let $H$ be the intersection of the three altitudes of triangle $A B C$. (This point is usually called the orthocenter). Prove that $\angle D A H=\angle M A O$.

Prove that line $A D$ is the symmedian from $A$ in triangle $A B C$ by showing that $\angle D A B=\angle M A C$.

Prove that line $A D$ is also the symmedian from $D$ in triangle $D B C$.

Rachel and Brian are playing a game in a grid with 1 row of 2011 squares. Initially, there is one white checker in each of the first two squares from the left, and one black checker in the third square from the left. At each stage, Rachel can choose to either run or fight. If Rachel runs, she moves the black checker moves 1 unit to the right, and Brian moves each of the white checkers one unit to the right. If Rachel chooses to fight, she pushes the checker immediately to the left of the black checker 1 unit to the left; the black checker is moved 1 unit to the right, and Brian places a new white checker in the cell immediately to the left of the black one. The game ends when the black checker reaches the last cell. How many different final configurations are possible?

On Facebook, there is a group of people that satisfies the following two properties: (i) there exists a positive integers $k$ such that any subset of $2 k-1$ people in the group contains a subset of $k$ people in the group who are all friends with each other, and (ii) every member of the group has 2011 friends or fewer. (a) [15] If $k=2$, determine, with proof, the maximum number of people the group may contain. (b) [25] If $k=776$, determine, with proof, the maximum number of people the group may contain.

Let $A B C$ be a triangle with area 1. Let points $D$ and $E$ lie on $A B$ and $A C$, respectively, such that $D E$ is parallel to $B C$ and $D E / B C=1 / 3$. If $F$ is the reflection of $A$ across $D E$, find the area of triangle $F B C$.

Let $a \star b=\sin a \cos b$ for all real numbers $a$ and $b$. If $x$ and $y$ are real numbers such that $x \star y-y \star x=1$, what is the maximum value of $x \star y+y \star x$ ?

Evaluate $2011 \times 20122012 \times 201320132013-2013 \times 20112011 \times 201220122012$.

Let $p$ be the answer to this question. If a point is chosen uniformly at random from the square bounded by $x=0, x=1, y=0$, and $y=1$, what is the probability that at least one of its coordinates is greater than $p$ ?

Rachelle picks a positive integer $a$ and writes it next to itself to obtain a new positive integer $b$. For instance, if $a=17$, then $b=1717$. To her surprise, she finds that $b$ is a multiple of $a^{2}$. Find the product of all the possible values of $\frac{b}{a^{2}}$.

Square $A B C D$ is inscribed in circle $\omega$ with radius 10. Four additional squares are drawn inside $\omega$ but outside $A B C D$ such that the lengths of their diagonals are as large as possible. A sixth square is drawn by connecting the centers of the four aforementioned small squares. Find the area of the sixth square.

For any positive real numbers $a$ and $b$, define $a \circ b=a+b+2 \sqrt{a b}$. Find all positive real numbers $x$ such that $x^{2} \circ 9 x=121$.

Find the smallest $k$ such that for any arrangement of 3000 checkers in a $2011 \times 2011$ checkerboard, with at most one checker in each square, there exist $k$ rows and $k$ columns for which every checker is contained in at least one of these rows or columns.

Segments $A A^{\prime}, B B^{\prime}$, and $C C^{\prime}$, each of length 2, all intersect at a point $O$. If $\angle A O C^{\prime}=\angle B O A^{\prime}=$ $\angle C O B^{\prime}=60^{\circ}$, find the maximum possible value of the sum of the areas of triangles $A O C^{\prime}, B O A^{\prime}$, and $C O B^{\prime}$.

In how many ways can one fill a $4 \times 4$ grid with a 0 or 1 in each square such that the sum of the entries in each row, column, and long diagonal is even?

Rosencrantz and Guildenstern play a game in which they repeatedly flip a fair coin. Let $a_{1}=4$, $a_{2}=3$, and $a_{n}=a_{n-1}+a_{n-2}$ for all $n \geq 3$. On the $n$th flip, if the coin is heads, Rosencrantz pays Guildenstern $a_{n}$ dollars, and, if the coin is tails, Guildenstern pays Rosencrantz $a_{n}$ dollars. If play continues for 2010 turns, what is the probability that Rosencrantz ends up with more money than he started with?

A sequence of integers $\left\{a_{i}\right\}$ is defined as follows: $a_{i}=i$ for all $1 \leq i \leq 5$, and $a_{i}=a_{1} a_{2} \cdots a_{i-1}-1$ for all $i>5$. Evaluate $a_{1} a_{2} \cdots a_{2011}-\sum_{i=1}^{2011} a_{i}^{2}$.

Let $a, b$, and $c$ be the side lengths of a triangle, and assume that $a \leq b$ and $a \leq c$. Let $x=\frac{b+c-a}{2}$. If $r$ and $R$ denote the inradius and circumradius, respectively, find the minimum value of $\frac{a x}{r R}$.

Danny has a set of 15 pool balls, numbered $1,2, \ldots, 15$. In how many ways can he put the balls in 8 indistinguishable bins such that the sum of the numbers of the balls in each bin is 14,15 , or 16 ?

Find all irrational numbers $x$ such that $x^{3}-17 x$ and $x^{2}+4 x$ are both rational numbers.

Let $R$ be a semicircle with diameter $X Y$. A trapezoid $A B C D$ in which $A B$ is parallel to $C D$ is circumscribed about $R$ such that $A B$ contains $X Y$. If $A D=4, C D=5$, and $B C=6$, determine $A B$.

Given positive real numbers $x, y$, and $z$ that satisfy the following system of equations:

$$\begin{aligned} x^{2}+y^{2}+x y & =1, \\ y^{2}+z^{2}+y z & =4, \\ z^{2}+x^{2}+z x & =5, \end{aligned}$$

find $x+y+z$.

In how many ways can each square of a $4 \times 2011$ grid be colored red, blue, or yellow such that no two squares that are diagonally adjacent are the same color?

Find the least positive integer $N$ with the following property: If all lattice points in $[1,3] \times[1,7] \times$ $[1, N]$ are colored either black or white, then there exists a rectangular prism, whose faces are parallel to the $x y, x z$, and $y z$ planes, and whose eight vertices are all colored in the same color.

Let $A B C D$ be a quadrilateral circumscribed about a circle with center $O$. Let $O_{1}, O_{2}, O_{3}$, and $O_{4}$ denote the circumcenters of $\triangle A O B, \triangle B O C, \triangle C O D$, and $\triangle D O A$. If $\angle A=120^{\circ}, \angle B=80^{\circ}$, and $\angle C=45^{\circ}$, what is the acute angle formed by the two lines passing through $O_{1} O_{3}$ and $O_{2} O_{4}$ ?

Let $A B C D$ be a quadrilateral inscribed in a circle with center $O$. Let $P$ denote the intersection of $A C$ and $B D$. Let $M$ and $N$ denote the midpoints of $A D$ and $B C$. If $A P=1, B P=3, D P=\sqrt{3}$, and $A C$ is perpendicular to $B D$, find the area of triangle $M O N$.

Find the number of ordered triples $(a, b, c)$ of pairwise distinct integers such that $-31 \leq a, b, c \leq 31$ and $a+b+c>0$.

Let $S$ be the set of points $(x, y, z)$ in $\mathbb{R}^{3}$ such that $x, y$, and $z$ are positive integers less than or equal to 100. Let $f$ be a bijective map between $S$ and the $\{1,2, \ldots, 1000000\}$ that satisfies the following property: if $x_{1} \leq x_{2}, y_{1} \leq y_{2}$, and $z_{1} \leq z_{2}$, then $f\left(x_{1}, y_{1}, z_{1}\right) \leq f\left(x_{2}, y_{2}, z_{2}\right)$. Define

$$\begin{aligned} A_{i} & =\sum_{j=1}^{100} \sum_{k=1}^{100} f(i, j, k), \\ B_{i} & =\sum_{j=1}^{100} \sum_{k=1}^{100} f(j, i, k), \\ \text { and } C_{i} & =\sum_{j=1}^{100} \sum_{k=1}^{100} f(j, k, i) \end{aligned}$$

Determine the minimum value of $A_{i+1}-A_{i}+B_{j+1}-B_{j}+C_{k+1}-C_{k}$.

In how many ways may thirteen beads be placed on a circular necklace if each bead is either blue or yellow and no two yellow beads may be placed in adjacent positions? (Beads of the same color are considered to be identical, and two arrangements are considered to be the same if and only if each can be obtained from the other by rotation).

Let $n$ be an integer greater than 3 . Let $R$ be the set of lattice points $(x, y)$ such that $0 \leq x, y \leq n$ and $|x-y| \leq 3$. Let $A_{n}$ be the number of paths from $(0,0)$ to $(n, n)$ that consist only of steps of the form $(x, y) \rightarrow(x, y+1)$ and $(x, y) \rightarrow(x+1, y)$ and are contained entirely within $R$. Find the smallest positive real number that is greater than $\frac{A_{n+1}}{A_{n}}$ for all $n$.

In how many ways can 13 bishops be placed on an $8 \times 8$ chessboard such that (i) a bishop is placed on the second square in the second row, (ii) at most one bishop is placed on each square, (iii) no bishop is placed on the same diagonal as another bishop, and (iv) every diagonal contains a bishop? (For the purposes of this problem, consider all diagonals of the chessboard to be diagonals, not just the main diagonals).

Find the number of polynomials $p(x)$ with integer coefficients satisfying $p(x) \geq \min \left\{2 x^{4}-6 x^{2}+1,4-5 x^{2}\right\}$ and $p(x) \leq \max \left\{2 x^{4}-6 x^{2}+1,4-5 x^{2}\right\}$ for all $x \in \mathbb{R}$.

Let $A B C$ be a triangle, and let points $P$ and $Q$ lie on $B C$ such that $P$ is closer to $B$ than $Q$ is. Suppose that the radii of the incircles of triangles $A B P, A P Q$, and $A Q C$ are all equal to 1 , and that the radii of the corresponding excircles opposite $A$ are 3,6 , and 5 , respectively. If the radius of the incircle of triangle $A B C$ is $\frac{3}{2}$, find the radius of the excircle of triangle $A B C$ opposite $A$.

Let $A B C$ be a triangle such that $A B=A C=182$ and $B C=140$. Let $X_{1}$ lie on $A C$ such that $C X_{1}=130$. Let the line through $X_{1}$ perpendicular to $B X_{1}$ at $X_{1}$ meet $A B$ at $X_{2}$. Define $X_{2}, X_{3}, \ldots$, as follows: for $n$ odd and $n \geq 1$, let $X_{n+1}$ be the intersection of $A B$ with the perpendicular to $X_{n-1} X_{n}$ through $X_{n}$; for $n$ even and $n \geq 2$, let $X_{n+1}$ be the intersection of $A C$ with the perpendicular to $X_{n-1} X_{n}$ through $X_{n}$. Find $B X_{1}+X_{1} X_{2}+X_{2} X_{3}+\ldots$

How many ways are there to color the vertices of a $2 n$-gon with three colors such that no vertex has the same color as its either of its two neighbors or the vertex directly across from it?

Let $A=\{1,2,3, \ldots, 9\}$. Find the number of bijective functions $f: A \rightarrow A$ for which there exists at least one $i \in A$ such that

$$\left|f(i)-f^{-1}(i)\right|>1$$

Let $p$ be a prime positive integer. Define a mod- $p$ recurrence of degree $n$ to be a sequence $\left\{a_{k}\right\}_{k \geq 0}$ of numbers modulo $p$ satisfying a relation of the form $a_{i+n}=c_{n-1} a_{i+n-1}+\ldots+c_{1} a_{i+1}+c_{0} a_{i}$ for all $i \geq 0$, where $c_{0}, c_{1}, \ldots, c_{n-1}$ are integers and $c_{0} \not \equiv 0(\bmod p)$. Compute the number of distinct linear recurrences of degree at most $n$ in terms of $p$ and $n$.

Find the number of sequences consisting of $100 R$ 's and $2011 S$ 's that satisfy the property that among the first $k$ letters, the number of $S$ 's is strictly more than 20 times the number of $R$ 's for all $1 \leq k \leq 2111$.

Let $w=w_{1}, w_{2}, \ldots, w_{6}$ be a permutation of the integers $\{1,2, \ldots, 6\}$. If there do not exist indices $i<j<k$ such that $w_{i}<w_{j}<w_{k}$ or indices $i<j<k<l$ such that $w_{i}>w_{j}>w_{k}>w_{l}$, then $w$ is said to be exquisite. Find the number of exquisite permutations.

An independent set of a graph $G$ is a set of vertices of $G$ such that no two vertices among these are connected by an edge. If $G$ has 2000 vertices, and each vertex has degree 10 , find the maximum possible number of independent sets that $G$ can have.

An ordering of a set of $n$ elements is a bijective map between the set and $\{1,2, \ldots, n\}$. Call an ordering $\rho$ of the 10 unordered pairs of distinct integers from the set $\{1,2,3,4,5\}$ admissible if, for any $1 \leq a<b<c \leq 5$, either $p(\{a, b\})<p(\{a, c\})<p(\{b, c\})$ or $p(\{b, c\})<p(\{a, c\})<p(\{a, b\})$. Find the total number of admissible orderings.