HMMT November 2019

Dylan has a $100 \times 100$ square, and wants to cut it into pieces of area at least 1 . Each cut must be a straight line (not a line segment) and must intersect the interior of the square. What is the largest number of cuts he can make?

Meghana writes two (not necessarily distinct) primes $q$ and $r$ in base 10 next to each other on a blackboard, resulting in the concatenation of $q$ and $r$ (for example, if $q=13$ and $r=5$, the number on the blackboard is now 135). She notices that three more than the resulting number is the square of a prime $p$. Find all possible values of $p$.

Katie has a fair 2019-sided die with sides labeled $1,2, \ldots, 2019$. After each roll, she replaces her $n$-sided die with an $(n+1)$-sided die having the $n$ sides of her previous die and an additional side with the number she just rolled. What is the probability that Katie's $2019^{\text {th }}$ roll is a 2019 ?

In $\triangle A B C, A B=2019, B C=2020$, and $C A=2021$. Yannick draws three regular $n$-gons in the plane of $\triangle A B C$ so that each $n$-gon shares a side with a distinct side of $\triangle A B C$ and no two of the $n$-gons overlap. What is the maximum possible value of $n$ ?

Let $a, b, c$ be positive real numbers such that $a \leq b \leq c \leq 2 a$. Find the maximum possible value of

$$\frac{b}{a}+\frac{c}{b}+\frac{a}{c}$$

Find all ordered pairs $(a, b)$ of positive integers such that $2 a+1$ divides $3 b-1$ and $2 b+1$ divides $3 a-1$.

In Middle-Earth, nine cities form a 3 by 3 grid. The top left city is the capital of Gondor and the bottom right city is the capital of Mordor. How many ways can the remaining cities be divided among the two nations such that all cities in a country can be reached from its capital via the grid-lines without passing through a city of the other country?

Compute the number of ordered pairs of integers $(x, y)$ such that $x^{2}+y^{2}<2019$ and

$$x^{2}+\min (x, y)=y^{2}+\max (x, y)$$

Let $A B C D$ be an isosceles trapezoid with $A D=B C=255$ and $A B=128$. Let $M$ be the midpoint of $C D$ and let $N$ be the foot of the perpendicular from $A$ to $C D$. If $\angle M B C=90^{\circ}$, compute $\tan \angle N B M$.

An up-right path between two lattice points $P$ and $Q$ is a path from $P$ to $Q$ that takes steps of 1 unit either up or to the right. A lattice point $(x, y)$ with $0 \leq x, y \leq 5$ is chosen uniformly at random. Compute the expected number of up-right paths from $(0,0)$ to $(5,5)$ not passing through $(x, y)$.

For breakfast, Mihir always eats a bowl of Lucky Charms cereal, which consists of oat pieces and marshmallow pieces. He defines the luckiness of a bowl of cereal to be the ratio of the number of marshmallow pieces to the total number of pieces. One day, Mihir notices that his breakfast cereal has exactly 90 oat pieces and 9 marshmallow pieces, and exclaims, "This is such an unlucky bowl!" How many marshmallow pieces does Mihir need to add to his bowl to double its luckiness?

Sandy likes to eat waffles for breakfast. To make them, she centers a circle of waffle batter of radius 3 cm at the origin of the coordinate plane and her waffle iron imprints non-overlapping unit-square holes centered at each lattice point. How many of these holes are contained entirely within the area of the waffle?

For breakfast, Milan is eating a piece of toast shaped like an equilateral triangle. On the piece of toast rests a single sesame seed that is one inch away from one side, two inches away from another side, and four inches away from the third side. He places a circular piece of cheese on top of the toast that is tangent to each side of the triangle. What is the area of this piece of cheese?

To celebrate 2019, Faraz gets four sandwiches shaped in the digits 2, 0, 1, and 9 at lunch. However, the four digits get reordered (but not flipped or rotated) on his plate and he notices that they form a 4-digit multiple of 7 . What is the greatest possible number that could have been formed?

Alison is eating 2401 grains of rice for lunch. She eats the rice in a very peculiar manner: every step, if she has only one grain of rice remaining, she eats it. Otherwise, she finds the smallest positive integer $d>1$ for which she can group the rice into equal groups of size $d$ with none left over. She then groups the rice into groups of size $d$, eats one grain from each group, and puts the rice back into a single pile. How many steps does it take her to finish all her rice?

Wendy eats sushi for lunch. She wants to eat six pieces of sushi arranged in a $2 \times 3$ rectangular grid, but sushi is sticky, and Wendy can only eat a piece if it is adjacent to (not counting diagonally) at most two other pieces. In how many orders can Wendy eat the six pieces of sushi, assuming that the pieces of sushi are distinguishable?

Carl only eats food in the shape of equilateral pentagons. Unfortunately, for dinner he receives a piece of steak in the shape of an equilateral triangle. So that he can eat it, he cuts off two corners with straight cuts to form an equilateral pentagon. The set of possible perimeters of the pentagon he obtains is exactly the interval $[a, b)$, where $a$ and $b$ are positive real numbers. Compute $\frac{a}{b}$.

Omkar, $\mathrm{Krit}_{1}, \mathrm{Krit}_{2}$, and $\mathrm{Krit}_{3}$ are sharing $x>0$ pints of soup for dinner. Omkar always takes 1 pint of soup (unless the amount left is less than one pint, in which case he simply takes all the remaining soup). Krit $_{1}$ always takes $\frac{1}{6}$ of what is left, Krit ${ }_{2}$ always takes $\frac{1}{5}$ of what is left, and Krit ${ }_{3}$ always takes $\frac{1}{4}$ of what is left. They take soup in the order of Omkar, $\mathrm{Krit}_{1}, \mathrm{Krit}_{2}$, $\mathrm{Krit}_{3}$, and then cycle through this order until no soup remains. Find all $x$ for which everyone gets the same amount of soup.

For dinner, Priya is eating grilled pineapple spears. Each spear is in the shape of the quadrilateral PINE, with $P I=6 \mathrm{~cm}, I N=15 \mathrm{~cm}, N E=6 \mathrm{~cm}, E P=25 \mathrm{~cm}$, and $\angle N E P+\angle E P I=60^{\circ}$. What is the area of each spear, in $\mathrm{cm}^{2}$ ?

For dessert, Melinda eats a spherical scoop of ice cream with diameter 2 inches. She prefers to eat her ice cream in cube-like shapes, however. She has a special machine which, given a sphere placed in space, cuts it through the planes $x=n, y=n$, and $z=n$ for every integer $n$ (not necessarily positive). Melinda centers the scoop of ice cream uniformly at random inside the cube $0 \leq x, y, z \leq 1$, and then cuts it into pieces using her machine. What is the expected number of pieces she cuts the ice cream into?

Each person in Cambridge drinks a (possibly different) 12 ounce mixture of water and apple juice, where each drink has a positive amount of both liquids. Marc McGovern, the mayor of Cambridge, drinks $\frac{1}{6}$ of the total amount of water drunk and $\frac{1}{8}$ of the total amount of apple juice drunk. How many people are in Cambridge?

2019 students are voting on the distribution of $N$ items. For each item, each student submits a vote on who should receive that item, and the person with the most votes receives the item (in case of a tie, no one gets the item). Suppose that no student votes for the same person twice. Compute the maximum possible number of items one student can receive, over all possible values of $N$ and all possible ways of voting.

The coefficients of the polynomial $P(x)$ are nonnegative integers, each less than 100 . Given that $P(10)=331633$ and $P(-10)=273373$, compute $P(1)$.

Two players play a game, starting with a pile of $N$ tokens. On each player's turn, they must remove $2^{n}$ tokens from the pile for some nonnegative integer $n$. If a player cannot make a move, they lose. For how many $N$ between 1 and 2019 (inclusive) does the first player have a winning strategy?

Let $A B C D$ be an isosceles trapezoid with $A B=1, B C=D A=5, C D=7$. Let $P$ be the intersection of diagonals $A C$ and $B D$, and let $Q$ be the foot of the altitude from $D$ to $B C$. Let $P Q$ intersect $A B$ at R. Compute $\sin \angle R P D$.

Consider sequences $a$ of the form $a=\left(a_{1}, a_{2}, \ldots, a_{20}\right)$ such that each term $a_{i}$ is either 0 or 1 . For each such sequence $a$, we can produce a sequence $b=\left(b_{1}, b_{2}, \ldots, b_{20}\right)$, where

$$b_{i}= \begin{cases}a_{i}+a_{i+1} & i=1 \\ a_{i-1}+a_{i}+a_{i+1} & 1<i<20 \\ a_{i-1}+a_{i} & i=20\end{cases}$$

How many sequences $b$ are there that can be produced by more than one distinct sequence $a$ ?

In $\triangle A B C$, the external angle bisector of $\angle B A C$ intersects line $B C$ at $D$. $E$ is a point on ray $\overrightarrow{A C}$ such that $\angle B D E=2 \angle A D B$. If $A B=10, A C=12$, and $C E=33$, compute $\frac{D B}{D E}$.

Will stands at a point $P$ on the edge of a circular room with perfectly reflective walls. He shines two laser pointers into the room, forming angles of $n^{\circ}$ and $(n+1)^{\circ}$ with the tangent at $P$, where $n$ is a positive integer less than 90 . The lasers reflect off of the walls, illuminating the points they hit on the walls, until they reach $P$ again. ( $P$ is also illuminated at the end.) What is the minimum possible number of illuminated points on the walls of the room?

A convex 2019-gon $A_{1} A_{2} \ldots A_{2019}$ is cut into smaller pieces along its 2019 diagonals of the form $A_{i} A_{i+3}$ for $1 \leq i \leq 2019$, where $A_{2020}=A_{1}, A_{2021}=A_{2}$, and $A_{2022}=A_{3}$. What is the least possible number of resulting pieces?

A polynomial $P$ with integer coefficients is called tricky if it has 4 as a root.

A polynomial is called teeny if it has degree at most 1 and integer coefficients between -7 and 7 , inclusive. How many nonzero tricky teeny polynomials are there?

You are trying to cross a 6 foot wide river. You can jump at most 4 feet, but you have one stone you can throw into the river; after it is placed, you may jump to that stone and, if possible, from there to the other side of the river. However, you are not very accurate and the stone ends up landing uniformly at random in the river. What is the probability that you can get across?

For how many positive integers $a$ does the polynomial

$$x^{2}-a x+a$$

have an integer root?

In 2019, a team, including professor Andrew Sutherland of MIT, found three cubes of integers which sum to 42 :

$$42=\left(-8053873881207597 \_\right)^{3}+(80435758145817515)^{3}+(12602123297335631)^{3}$$

One of the digits, labeled by an underscore, is missing. What is that digit?

A point $P$ is chosen uniformly at random inside a square of side length 2 . If $P_{1}, P_{2}, P_{3}$, and $P_{4}$ are the reflections of $P$ over each of the four sides of the square, find the expected value of the area of quadrilateral $P_{1} P_{2} P_{3} P_{4}$.

Compute the sum of all positive integers $n<2048$ such that $n$ has an even number of 1 's in its binary representation.

Let $S$ be the set of all nondegenerate triangles formed from the vertices of a regular octagon with side length 1. Find the ratio of the largest area of any triangle in $S$ to the smallest area of any triangle in $S$.

There are 36 students at the Multiples Obfuscation Program, including a singleton, a pair of identical twins, a set of identical triplets, a set of identical quadruplets, and so on, up to a set of identical octuplets. Two students look the same if and only if they are from the same identical multiple. Nithya the teaching assistant encounters a random student in the morning and a random student in the afternoon (both chosen uniformly and independently), and the two look the same. What is the probability that they are actually the same person?

Let $p$ be a real number between 0 and 1. Jocelin has a coin that lands heads with probability $p$ and tails with probability $1-p$; she also has a number written on a blackboard. Each minute, she flips the coin, and if it lands heads, she replaces the number $x$ on the blackboard with $3 x+1$; if it lands tails she replaces it with $x / 2$. Given that there are constants $a, b$ such that the expected value of the value written on the blackboard after $t$ minutes can be written as $a t+b$ for all positive integers $t$, compute $p$.

Let $A B C D$ be a square of side length 5 , and let $E$ be the midpoint of side $A B$. Let $P$ and $Q$ be the feet of perpendiculars from $B$ and $D$ to $C E$, respectively, and let $R$ be the foot of the perpendicular from $A$ to $D Q$. The segments $C E, B P, D Q$, and $A R$ partition $A B C D$ into five regions. What is the median of the areas of these five regions?

Let $a, b, c, d$ be real numbers such that

$$\min (20 x+19,19 x+20)=(a x+b)-|c x+d|$$

for all real numbers $x$. Find $a b+c d$.

Four players stand at distinct vertices of a square. They each independently choose a vertex of the square (which might be the vertex they are standing on). Then, they each, at the same time, begin running in a straight line to their chosen vertex at 10 mph , stopping when they reach the vertex. If at any time two players, whether moving or not, occupy the same space (whether a vertex or a point inside the square), they collide and fall over. How many different ways are there for the players to choose vertices to go to so that none of them fall over?

In $\triangle A B C$, the incircle centered at $I$ touches sides $A B$ and $B C$ at $X$ and $Y$, respectively. Additionally, the area of quadrilateral $B X I Y$ is $\frac{2}{5}$ of the area of $A B C$. Let $p$ be the smallest possible perimeter of a $\triangle A B C$ that meets these conditions and has integer side lengths. Find the smallest possible area of such a triangle with perimeter $p$.

Compute the sum of all positive integers $n$ for which

$$9 \sqrt{n}+4 \sqrt{n+2}-3 \sqrt{n+16}$$

is an integer.

Let $a, b, c$ be positive integers such that

$$\frac{a}{77}+\frac{b}{91}+\frac{c}{143}=1$$

What is the smallest possible value of $a+b+c$ ?

Equilateral $\triangle A B C$ has side length 6 . Let $\omega$ be the circle through $A$ and $B$ such that $C A$ and $C B$ are both tangent to $\omega$. A point $D$ on $\omega$ satisfies $C D=4$. Let $E$ be the intersection of line $C D$ with segment $A B$. What is the length of segment $D E$ ?

Kelvin the frog lives in a pond with an infinite number of lily pads, numbered $0,1,2,3$, and so forth. Kelvin starts on lily pad 0 and jumps from pad to pad in the following manner: when on lily pad $i$, he will jump to lily pad $(i+k)$ with probability $\frac{1}{2^{k}}$ for $k>0$. What is the probability that Kelvin lands on lily pad 2019 at some point in his journey?

The polynomial $x^{3}-3 x^{2}+1$ has three real roots $r_{1}, r_{2}$, and $r_{3}$. Compute

$$\sqrt[3]{3 r_{1}-2}+\sqrt[3]{3 r_{2}-2}+\sqrt[3]{3 r_{3}-2}$$

Let $A B C$ be a triangle with $A B=5, B C=8, C A=11$. The incircle $\omega$ and $A$-excircle ${ }^{1} \Gamma$ are centered at $I_{1}$ and $I_{2}$, respectively, and are tangent to $B C$ at $D_{1}$ and $D_{2}$, respectively. Find the ratio of the area of $\triangle A I_{1} D_{1}$ to the area of $\triangle A I_{2} D_{2}$.

Consider an equilateral triangle $T$ of side length 12 . Matthew cuts $T$ into $N$ smaller equilateral triangles, each of which has side length 1,3 , or 8 . Compute the minimum possible value of $N$.

A positive integer $n$ is infallible if it is possible to select $n$ vertices of a regular 100-gon so that they form a convex, non-self-intersecting $n$-gon having all equal angles. Find the sum of all infallible integers $n$ between 3 and 100, inclusive.

Let $f(n)$ be the number of distinct digits of $n$ when written in base 10 . Compute the sum of $f(n)$ as $n$ ranges over all positive 2019-digit integers.

For a positive integer $n$, let, $\tau(n)$ be the number of positive integer divisors of $n$. How many integers $1 \leq n \leq 50$ are there such that $\tau(\tau(n))$ is odd?

Let $P$ be a point inside regular pentagon $A B C D E$ such that $\angle P A B=48^{\circ}$ and $\angle P D C=42^{\circ}$. Find $\angle B P C$, in degrees.

In acute $\triangle A B C$ with centroid $G, A B=22$ and $A C=19$. Let $E$ and $F$ be the feet of the altitudes from $B$ and $C$ to $A C$ and $A B$ respectively. Let $G^{\prime}$ be the reflection of $G$ over $B C$. If $E, F, G$, and $G^{\prime}$ lie on a circle, compute $B C$.

Dan is walking down the left side of a street in New York City and must cross to the right side at one of 10 crosswalks he will pass. Each time he arrives at a crosswalk, however, he must wait $t$ seconds, where $t$ is selected uniformly at random from the real interval $[0,60]$ ( $t$ can be different at different crosswalks). Because the wait time is conveniently displayed on the signal across the street, Dan employs the following strategy: if the wait time when he arrives at the crosswalk is no more than $k$ seconds, he crosses. Otherwise, he immediately moves on to the next crosswalk. If he arrives at the last crosswalk and has not crossed yet, then he crosses regardless of the wait time. Find the value of $k$ which minimizes his expected wait time.

For a given positive integer $n$, we define $\varphi(n)$ to be the number of positive integers less than or equal to $n$ which share no common prime factors with $n$. Find all positive integers $n$ for which

$$\varphi(2019 n)=\varphi\left(n^{2}\right)$$

A palindrome is a string that does not change when its characters are written in reverse order. Let $S$ be a 40 -digit string consisting only of 0 's and 1 's, chosen uniformly at random out of all such strings. Let $E$ be the expected number of nonempty contiguous substrings of $S$ which are palindromes. Compute the value of $\lfloor E\rfloor$.

In isosceles $\triangle A B C, A B=A C$ and $P$ is a point on side $B C$. If $\angle B A P=2 \angle C A P, B P=\sqrt{3}$, and $C P=1$, compute $A P$.

A function $f: \mathbb{Z} \rightarrow \mathbb{Z}$ satisfies: $f(0)=0$ and

$$\left|f\left((n+1) 2^{k}\right)-f\left(n 2^{k}\right)\right| \leq 1$$

for all integers $k \geq 0$ and $n$. What is the maximum possible value of $f(2019)$ ?

James is standing at the point $(0,1)$ on the coordinate plane and wants to eat a hamburger. For each integer $n \geq 0$, the point $(n, 0)$ has a hamburger with $n$ patties. There is also a wall at $y=2.1$ which James cannot cross. In each move, James can go either up, right, or down 1 unit as long as he does not cross the wall or visit a point he has already visited. Every second, James chooses a valid move uniformly at random, until he reaches a point with a hamburger. Then he eats the hamburger and stops moving. Find the expected number of patties that James eats on his burger.

A sequence of real numbers $a_{0}, a_{1}, \ldots, a_{9}$ with $a_{0}=0, a_{1}=1$, and $a_{2}>0$ satisfies

$$a_{n+2} a_{n} a_{n-1}=a_{n+2}+a_{n}+a_{n-1}$$

for all $1 \leq n \leq 7$, but cannot be extended to $a_{10}$. In other words, no values of $a_{10} \in \mathbb{R}$ satisfy

$$a_{10} a_{8} a_{7}=a_{10}+a_{8}+a_{7}$$

Compute the smallest possible value of $a_{2}$.

A circle $\Gamma$ with center $O$ has radius 1. Consider pairs $(A, B)$ of points so that $A$ is inside the circle and $B$ is on its boundary. The circumcircle $\Omega$ of $O A B$ intersects $\Gamma$ again at $C \neq B$, and line $A C$ intersects $\Gamma$ again at $X \neq C$. The pair $(A, B)$ is called techy if line $O X$ is tangent to $\Omega$. Find the area of the region of points $A$ so that there exists a $B$ for which $(A, B)$ is techy.

A polynomial $P$ with integer coefficients is called tricky if it has 4 as a root.

A polynomial is called $k$-tiny if it has degree at most 7 and integer coefficients between $-k$ and $k$, inclusive. A polynomial is called nearly tricky if it is the sum of a tricky polynomial and a 1-tiny polynomial. Let $N$ be the number of nearly tricky 7 -tiny polynomials. Estimate $N$. An estimate of $E$ will earn $\left\lfloor 20 \min \left(\frac{N}{E}, \frac{E}{N}\right)^{4}\right\rfloor$ points.

You are trying to cross a 400 foot wide river. You can jump at most 4 feet, but you have many stones you can throw into the river. You will stop throwing stones and cross the river once you have placed enough stones to be able to do so. You can throw straight, but you can't judge distance very well, so each stone ends up being placed uniformly at random along the width of the river. Estimate the expected number $N$ of stones you must throw before you can get across the river. An estimate of $E$ will earn $\left\lfloor 20 \min \left(\frac{N}{E}, \frac{E}{N}\right)^{3}\right\rfloor$ points.

Let $N$ be the number of sequences of positive integers $\left(a_{1}, a_{2}, a_{3}, \ldots, a_{15}\right)$ for which the polynomials

$$x^{2}-a_{i} x+a_{i+1}$$

each have an integer root for every $1 \leq i \leq 15$, setting $a_{16}=a_{1}$. Estimate $N$. An estimate of $E$ will earn $\left\lfloor 20 \min \left(\frac{N}{E}, \frac{E}{N}\right)^{2}\right\rfloor$ points.