HMMT November 2009

Evaluate the sum:

$$11^{2}-1^{2}+12^{2}-2^{2}+13^{2}-3^{2}+\ldots+20^{2}-10^{2}$$

Given that $a+b+c=5$ and that $1 \leq a, b, c \leq 2$, what is the minimum possible value of $\frac{1}{a+b}+\frac{1}{b+c}$ ?

What is the period of the function $f(x)=\cos (\cos (x))$ ?

How many subsets $A$ of $\{1,2,3,4,5,6,7,8,9,10\}$ have the property that no two elements of $A$ sum to 11 ?

A polyhedron has faces that are all either triangles or squares. No two square faces share an edge, and no two triangular faces share an edge. What is the ratio of the number of triangular faces to the number of square faces?

Find the maximum value of $x+y$, given that $x^{2}+y^{2}-3 y-1=0$.

There are 15 stones placed in a line. In how many ways can you mark 5 of these stones so that there are an odd number of stones between any two of the stones you marked?

Let $\triangle A B C$ be an equilateral triangle with height 13 , and let $O$ be its center. Point $X$ is chosen at random from all points inside $\triangle A B C$. Given that the circle of radius 1 centered at $X$ lies entirely inside $\triangle A B C$, what is the probability that this circle contains $O$ ?

A set of points is convex if the points are the vertices of a convex polygon (that is, a non-selfintersecting polygon with all angles less than or equal to $180^{\circ}$ ). Let $S$ be the set of points $(x, y)$ such that $x$ and $y$ are integers and $1 \leq x, y \leq 26$. Find the number of ways to choose a convex subset of $S$ that contains exactly 98 points.

Compute

$$\prod_{n=0}^{\infty}\left(1-\left(\frac{1}{2}\right)^{3^{n}}+\left(\frac{1}{4}\right)^{3^{n}}\right)$$

Paul starts with the number 19. In one step, he can add 1 to his number, divide his number by 2 , or divide his number by 3 . What is the minimum number of steps Paul needs to get to 1 ?

You start with a number. Every second, you can add or subtract any number of the form $n$ ! to your current number to get a new number. In how many ways can you get from 0 to 100 in 4 seconds? ( $n!$ is defined as $n \times(n-1) \times(n-2) \times \cdots \times 2 \times 1$, so $1!=1,2!=2,3!=6,4!=24$, etc.)

Let $C$ be the circle of radius 12 centered at $(0,0)$. What is the length of the shortest path in the plane between $(8 \sqrt{3}, 0)$ and $(0,12 \sqrt{2})$ that does not pass through the interior of $C$ ?

You are given a $5 \times 6$ checkerboard with squares alternately shaded black and white. The bottomleft square is white. Each square has side length 1 unit. You can normally travel on this board at a speed of 2 units per second, but while you travel through the interior (not the boundary) of a black square, you are slowed down to 1 unit per second. What is the shortest time it takes to travel from the bottom-left corner to the top-right corner of the board?

The following grid represents a mountain range; the number in each cell represents the height of the mountain located there. Moving from a mountain of height $a$ to a mountain of height $b$ takes $(b-a)^{2}$ time. Suppose that you start on the mountain of height 1 and that you can move up, down, left, or right to get from one mountain to the next. What is the minimum amount of time you need to get to the mountain of height 49 ?

1	3	6	10	15	21	28
2	5	9	14	20	27	34
4	8	13	19	26	33	39
7	12	18	25	32	38	43
11	17	24	31	37	42	46
16	23	30	36	41	45	48
22	29	35	40	44	47	49

There are five guys named Alan, Bob, Casey, Dan, and Eric. Each one either always tells the truth or always lies. You overhear the following discussion between them:

Alan: "All of us are truth-tellers."
Bob: "No, only Alan and I are truth-tellers."
Casey: "You are both liars."
Dan: "If Casey is a truth-teller, then Eric is too."
Eric: "An odd number of us are liars."

Who are the liars?

Five guys are eating hamburgers. Each one puts a top half and a bottom half of a hamburger bun on the grill. When the buns are toasted, each guy randomly takes two pieces of bread off of the grill. What is the probability that each guy gets a top half and a bottom half?

A single burger is not enough to satisfy a guy's hunger. The five guys go to Five Guys' Restaurant, which has 20 different meals on the menu. Each meal costs a different integer dollar amount between $\$ 1$ and $\$ 20$. The five guys have $\$ 20$ to split between them, and they want to use all the money to order five different meals. How many sets of five meals can the guys choose?

Five guys each have a positive integer (the integers are not necessarily distinct). The greatest common divisor of any two guys' numbers is always more than 1 , but the greatest common divisor of all the numbers is 1 . What is the minimum possible value of the product of the numbers?

Five guys join five girls for a night of bridge. Bridge games are always played by a team of two guys against a team of two girls. The guys and girls want to make sure that every guy and girl play against each other an equal number of times. Given that at least one game is played, what is the least number of games necessary to accomplish this?

Find the height at which the ball first contacts the right side.

How many times does the ball bounce before it returns to a vertex? (The final contact with a vertex does not count as a bounce.)

Find the distance from the ball's point of first contact with a wall to the nearest vertex.

How many times does the ball bounce before it returns to a vertex? (The final contact with a vertex does not count as a bounce.)

In how many ways can the ball be launched so that it will return again to a vertex for the first time after 2009 bounces?

Suppose that in every room, Mario randomly picks a door to walk through. What is the expected number of doors (not including Mario's initial entrance to the first room) through which Mario will pass before he reaches Bowser's level?

Suppose that instead there are 6 rooms with 4 doors. In each room, 1 door leads to the next room in the sequence (or, for the last room, Bowser's level), while the other 3 doors lead to the first room. Now what is the expected number of doors through which Mario will pass before he reaches Bowser's level?

In general, if there are $d$ doors in every room (but still only 1 correct door) and $r$ rooms, the last of which leads into Bowser's level, what is the expected number of doors through which Mario will pass before he reaches Bowser's level?

If $f(x)=x /(x+1)$, what is $f(f(f(f(2009))))$ ?

A knight begins on the lower-left square of a standard chessboard. How many squares could the knight end up at after exactly 2009 legal knight's moves? (A knight's move is 2 squares either horizontally or vertically, followed by 1 square in a direction perpendicular to the first.)

Consider a square, inside which is inscribed a circle, inside which is inscribed a square, inside which is inscribed a circle, and so on, with the outermost square having side length 1. Find the difference between the sum of the areas of the squares and the sum of the areas of the circles.

A cube has side length 1. Find the product of the lengths of the diagonals of this cube (a diagonal is a line between two vertices that is not an edge).

Tanks has a pile of 5 blue cards and 5 red cards. Every morning, he takes a card and throws it down a well. What is the probability that the first card he throws down and the last card he throws down are the same color?

Find the last two digits of $1032^{1032}$. Express your answer as a two-digit number.

A computer program is a function that takes in 4 bits, where each bit is either a 0 or a 1 , and outputs TRUE or FALSE. How many computer programs are there?

The angles of a convex $n$-sided polygon form an arithmetic progression whose common difference (in degrees) is a non-zero integer. Find the largest possible value of $n$ for which this is possible. (A polygon is convex if its interior angles are all less than $180^{\circ}$.)

Daniel wrote all the positive integers from 1 to $n$ inclusive on a piece of paper. After careful observation, he realized that the sum of all the digits that he wrote was exactly 10,000 . Find $n$.

Admiral Ackbar needs to send a 5-character message through hyperspace to the Rebels. Each character is a lowercase letter, and the same letter may appear more than once in a message. When the message is beamed through hyperspace, the characters come out in a random order. Ackbar chooses his message so that the Rebels have at least a $\frac{1}{2}$ chance of getting the same message he sent. How many distinct messages could he send?

Lily and Sarah are playing a game. They each choose a real number at random between -1 and 1 . They then add the squares of their numbers together. If the result is greater than or equal to 1 , Lily wins, and if the result is less than 1, Sarah wins. What is the probability that Sarah wins?

Let $\omega$ be a circle of radius 1 centered at $O$. Let $B$ be a point on $\omega$, and let $l$ be the line tangent to $\omega$ at $B$. Let $A$ be on $l$ such that $\angle A O B=60^{\circ}$. Let $C$ be the foot of the perpendicular from $B$ to $O A$. Find the length of line segment $O C$.

8 students are practicing for a math contest, and they divide into pairs to take a practice test. In how many ways can they be split up?

Let $f(x)=x^{4}+a x^{3}+b x^{2}+c x+d$ be a polynomial whose roots are all negative integers. If $a+b+c+d=2009$, find $d$.

The curves $x^{2}+y^{2}=36$ and $y=x^{2}-7$ intersect at four points. Find the sum of the squares of the $x$-coordinates of these points.

Pick a random digit in the decimal expansion of $\frac{1}{99999}$. What is the probability that it is 0 ?

A circle passes through the points $(2,0)$ and $(4,0)$ and is tangent to the line $y=x$. Find the sum of all possible values for the $y$-coordinate of the center of the circle.

Let $f$ be a function that takes in a triple of integers and outputs a real number. Suppose that $f$ satisfies the equations

$$\begin{aligned} f(a, b, c) & =\frac{f(a+1, b, c)+f(a-1, b, c)}{2} \\ f(a, b, c) & =\frac{f(a, b+1, c)+f(a, b-1, c)}{2} \\ f(a, b, c) & =\frac{f(a, b, c+1)+f(a, b, c-1)}{2} \end{aligned}$$

for all integers $a, b, c$. What is the minimum number of triples at which we need to evaluate $f$ in order to know its value everywhere?

You are trapped in ancient Japan, and a giant enemy crab is approaching! You must defeat it by cutting off its two claws and six legs and attacking its weak point for massive damage. You cannot cut off any of its claws until you cut off at least three of its legs, and you cannot attack its weak point until you have cut off all of its claws and legs. In how many ways can you defeat the giant enemy crab? (Note that the legs are distinguishable, as are the claws.)

Consider an equilateral triangle and a square both inscribed in a unit circle such that one side of the square is parallel to one side of the triangle. Compute the area of the convex heptagon formed by the vertices of both the triangle and the square.

Let $f(x)=x^{2}+2 x+1$. Let $g(x)=f(f(\cdots f(x)))$, where there are $2009 f \mathrm{~s}$ in the expression for $g(x)$. Then $g(x)$ can be written as

$$g(x)=x^{2^{2009}}+a_{2^{2009}-1} x^{2^{2009}-1}+\cdots+a_{1} x+a_{0}$$

where the $a_{i}$ are constants. Compute $a_{2^{2009}-1}$.

Five cards labeled A, B, C, D, and E are placed consecutively in a row. How many ways can they be re-arranged so that no card is moved more than one position away from where it started? (Not moving the cards at all counts as a valid re-arrangement.)

Let $a_{0}, a_{1}, \ldots$ be a sequence such that $a_{0}=3, a_{1}=2$, and $a_{n+2}=a_{n+1}+a_{n}$ for all $n \geq 0$. Find

$$\sum_{n=0}^{8} \frac{a_{n}}{a_{n+1} a_{n+2}}$$

Penta chooses 5 of the vertices of a unit cube. What is the maximum possible volume of the figure whose vertices are the 5 chosen points?

Find all solutions to $x^{4}+2 x^{3}+2 x^{2}+2 x+1=0$ (including non-real solutions).

In how many ways can the positive integers from 1 to 100 be arranged in a circle such that the sum of every two integers placed opposite each other is the same? (Arrangements that are rotations of each other count as the same.) Express your answer in the form $a!\cdot b^{c}$.

$A B C D$ is a regular tetrahedron of volume 1. Maria glues regular tetrahedra $A^{\prime} B C D, A B^{\prime} C D$, $A B C^{\prime} D$, and $A B C D^{\prime}$ to the faces of $A B C D$. What is the volume of the tetrahedron $A^{\prime} B^{\prime} C^{\prime} D^{\prime}$ ?

Six men and their wives are sitting at a round table with 12 seats. These men and women are very jealous - no man will allow his wife to sit next to any man except for himself, and no woman will allow her husband to sit next to any woman except for herself. In how many distinct ways can these 12 people be seated such that these conditions are satisfied? (Rotations of a valid seating are considered distinct.)

For how many integer values of $b$ does there exist a polynomial function with integer coefficients such that $f(2)=2010$ and $f(b)=8$ ?

Regular hexagon $A B C D E F$ has side length 2. A laser beam is fired inside the hexagon from point $A$ and hits $\overline{B C}$ at point $G$. The laser then reflects off $\overline{B C}$ and hits the midpoint of $\overline{D E}$. Find $B G$.

There are two buildings facing each other, each 5 stories high. How many ways can Kevin string ziplines between the buildings so that: (a) each zipline starts and ends in the middle of a floor. (b) ziplines can go up, stay flat, or go down, but can't touch each other (this includes touching at their endpoints).

Note that you can't string a zipline between two floors of the same building.

A circle $\omega_{1}$ of radius 15 intersects a circle $\omega_{2}$ of radius 13 at points $P$ and $Q$. Point $A$ is on line $P Q$ such that $P$ is between $A$ and $Q . R$ and $S$ are the points of tangency from $A$ to $\omega_{1}$ and $\omega_{2}$, respectively, such that the line $A S$ does not intersect $\omega_{1}$ and the line $A R$ does not intersect $\omega_{2}$. If $P Q=24$ and $\angle R A S$ has a measure of $90^{\circ}$, compute the length of $A R$.

Compute

$$\sum_{n=2009}^{\infty} \frac{1}{\binom{n}{2009}}$$

Note that $\binom{n}{k}$ is defined as $\frac{n!}{k!(n-k)!}$.

How many hits does "3.1415" get on Google? Quotes are for clarity only, and not part of the search phrase. Also note that Google does not search substrings, so a webpage with 3.14159 on it will not match 3.1415 . If $A$ is your answer, and $S$ is the correct answer, then you will get $\max (25-\mid \ln (A)-$ $\ln (S) \mid, 0)$ points, rounded to the nearest integer.

Call an integer $n>1$ radical if $2^{n}-1$ is prime. What is the 20 th smallest radical number? If $A$ is your answer, and $S$ is the correct answer, you will get $\max \left(25\left(1-\frac{|A-S|}{S}\right), 0\right)$ points, rounded to the nearest integer.