2009 PUMaC Problems

Algebra A Find the root that the following three polynomials have in common: $\begin{align*} & x^3+41x^2-49x-2009 \\ & x^3 + 5x^2-49x-245 \\ & x^3 + 39x^2 - 117x - 1435\end{align*}$

Given that $P(x)$ is the least degree polynomial with rational coefficients such that $P(\sqrt{2} + \sqrt{3}) = \sqrt{2},$ find $P(10)$ .

Let $x_1,x_2,\ldots, x_{10}$ be non-negative real numbers such that $\frac{x_1}{1}+ \frac{x_2}{2}+\ldots+\frac{x_{10}}{10}\leq9$ . Find the maximum possible value of $\frac{{x_1}^2}{1}+ \frac{{x_2}^2}{2}+\ldots+\frac{{x_{10}}^2}{10}$ .

Find the smallest positive $\alpha$ (in degrees) for which all the numbers $\cos{\alpha},\cos{2\alpha},\ldots,\cos{2^n\alpha},\ldots$ are negative.

Find the maximal positive integer $n$ , so that for any real number $x$ we have $\sin^{n}{x}+\cos^{n}{x} \geq \frac{1}{n}$ .

Find the number of functions $f:\mathbb{Z}\mapsto\mathbb{Z}$ for which $f(h+k)+f(hk)=f(h)f(k)+1$ , for all integers $h$ and $k$ .

Let $x_1,x_2,\dots,x_n$ be a sequence of integers, such that $-1\leq x_i\leq 2$ , for $i=1,2,\dots,n$ , $x_1+x_2+\dots+x_n = 7$ and $x_1^8+x_2^8+\dots x_n^8 =2009$ . Let $m$ and $M$ be the minimal and maximal possible value of $x_1^9+x_2^9+\dots x_n^9$ , respectively. Find the $\frac{M}{m}$ . Round your answer to nearest integer, if necessary.

The real numbers $x$ , $y$ , $z$ , and $t$ satisfy the following equation: $2x^2 + 4xy + 3y^2 - 2xz -2 yz + z^2 + 1 = t + \sqrt{y + z - t}$ Find 100 times the maximum possible value for $t$ .

Combinatorics A Find the number of subsets of $\{1,2,\ldots,7\}$ that do not contain two consecutive integers.

It is known that a certain mechanical balance can measure any object of integer mass anywhere between 1 and 2009 (both included). This balance has $k$ weights of integral values. What is the minimum $k$ for which there exist weights that satisfy this condition?

How many strings of ones and zeroes of length 10 are there such that there is an even number of ones, and no zero follows another zero?

We divide up the plane into disjoint regions using a circle, a rectangle and a triangle. What is the greatest number of regions that we can get?

There are $n$ players in a round-robin ping-pong tournament (i.e. every two persons will play exactly one game). After some matches have been played, it is known that the total number of matches that have been played among any $n-2$ people is equal to $3^k$ (where $k$ is a fixed integer). Find the sum of all possible values of $n$ .

We have a $6 \times 6$ square, partitioned into 36 unit squares. We select some of these unit squares and draw some of their diagonals, subject to the condition that no two diagonals we draw have any common points. What is the maximal number of diagonals that we can draw?

We randomly choose 5 distinct positive integers less than or equal to 90. What is the floor of 10 times the expected value of the fourth largest number?

Taotao wants to buy a bracelet. The bracelets have 7 different beads on them, arranged in a circle. Two bracelets are the same if one can be rotated or flipped to get the other. If she can choose the colors and placement of the beads, and the beads come in orange, white, and black, how many possible bracelets can she buy?

Geometry A A rectangular piece of paper $ABCD$ has sides of lengths $AB = 1$ , $BC = 2$ . The rectangle is folded in half such that $AD$ coincides with $BC$ and $EF$ is the folding line. Then fold the paper along a line $BM$ such that the corner $A$ falls on line $EF$ . How large, in degrees, is $\angle ABM$ ? $[asy] size(180); pathpen = linewidth(0.7); pointpen = black+linewidth(3); pointfontpen = fontsize(10); pen dd = linewidth(0.7) + linetype("4 4"), dr = rgb(0.8,0,0), dg = rgb(0,0.6,0), db = rgb(0,0,0.6)+linewidth(1); pair A=(0,1), B=(0,0), C=(2,0), D=(2,1), E=A/2, F=(2,.5), M=(0.5,1), N=reflect(B,M)*A; D(B--M--D("N",N,NE)--B--D("C",C,SE)--D("D",D,NE)--M); D(D("M",M,plain.N)--D("A",A,NW)--D("B",B,SW),dd); D(D("E",E,W)--D("F",F,plain.E),dd); [/asy]$

Tetrahedron $ABCD$ havs sides of lengths, in increasing order, $7, 13, 18, 27, 36, 41.$ If $AB=41$ , then what is the length of $CD$ ?

A polygon is called concave if it has at least one angle strictly greater than $180^{\circ}$ . What is the maximum number of symmetries that an 11-sided concave polygon can have?

In the following diagram (not to scale), $A$ , $B$ , $C$ , $D$ are four consecutive vertices of an 18-sided regular polygon with center $O$ . Let $P$ be the midpoint of $AC$ and $Q$ be the midpoint of $DO$ . Find $\angle OPQ$ in degrees. $[asy] pathpen = linewidth(0.7); pointpen = black+linewidth(3); pointfontpen = fontsize(10); pen dd = linewidth(0.7) + linetype("4 4"); real n = 10, start = 360/n*6-15; pair O=(0,0), A=dir(start), B=dir(start+360/n), C=dir(start+2*360/n), D=dir(start+3*360/n), P=(A+C)/2, Q=(O+D)/2; D(D("O",O,NE)--D("A",A,W)--D("B",B,SW)--D("C",C,S)--D("D",D,SE)--O--D("P",P,1.6*dir(95))--D("Q",Q,NE)); D(A--C); D(A--(A+dir(start-360/n))/2, dd); D(D--(D+dir(start+4*360/n))/2, dd); [/asy]$

Lines $l$ and $m$ are perpendicular. Line $l$ partitions a convex polygon into two parts of equal area, and partitions the projection of the polygon onto $m$ into two line segments of length $a$ and $b$ respectively. Determine the maximum value of $\left\lfloor \frac{1000a}{b} \right\rfloor$ . (The floor notation $\lfloor x \rfloor$ denotes largest integer not exceeding $x$ )

Consider the solid with 4 triangles and 4 regular hexagons as faces, where each triangle borders 3 hexagons, and all the sides are of length 1. Compute the [i]square[/i] of the volume of the solid. Express your result in reduced fraction and concatenate the numerator with the denominator (e.g., if you think that the square is $\frac{1734}{274}$ , then you would submit 1734274).

You are given a convex pentagon $ABCDE$ with $AB=BC$ , $CD=DE$ , $\angle{ABC}=150^\circ$ , $\angle{BCD} = 165^\circ$ , $\angle{CDE}=30^\circ$ , $BD=6$ . Find the area of this pentagon. Round your answer to the nearest integer if necessary. $[asy] pathpen = linewidth(0.7); pointpen = black+linewidth(3); pointfontpen = fontsize(10); pair A = (0,0), B = (0.8,-1.8), C = B+rotate(-150)*(A-B), D = IP(CR(B,6), C--C+rotate(-165)*6*(B-C)), E = D+rotate(-30)*(C-D); D(D("B",B,W)--D("C",C,SW)--D("D",D,plain.E)--D("E",E,NE)--D("A",A,NW)--B--D); [/asy]$

Consider $\triangle ABC$ and a point $M$ in its interior so that $\angle MAB = 10^\circ$ , $\angle MBA = 20^\circ$ , $\angle MCA = 30^\circ$ and $\angle MAC = 40^\circ$ . What is $\angle MBC$ ?

Number Theory A You are given that $17! = 355687ab8096000$ for some digits $a$ and $b$ . Find the two-digit number $\overline{ab}$ that is missing above.

Find the number of ordered pairs $(a, b)$ of positive integers that are solutions of the following equation: $a^2 + b^2 = ab(a+b)$

Find the sum of all prime numbers $p$ which satisfy $p = a^4 + b^4 + c^4 - 3$ for some primes (not necessarily distinct) $a$ , $b$ and $c$ .

Find the sum of all integers $x$ for which there is an integer $y$ , such that $x^3-y^3=xy+61$ .

Suppose that for some positive integer $n$ , the first two digits of $5^n$ and $2^n$ are identical. Suppose the first two digits are $a$ and $b$ in this order. Find the two-digit number $\overline{ab}$ .

Let $s(m)$ denote the sum of the digits of the positive integer $m$ . Find the largest positive integer that has no digits equal to zero and satisfies the equation $2^{s(n)} = s(n^2).$

Let $S=\{p/q| q\leq 2009, p/q <1257/2009, p,q \in \mathbb{N} \}$ . If the maximum element of $S$ is $p_0/q_0$ in reduced form, find $p_0+q_0$ .

Find the largest positive integer $k$ such that $\phi ( \sigma ( 2^k)) = 2^k$ . ( $\phi(n)$ denotes the number of positive integers that are smaller than $n$ and relatively prime to $n$ , and $\sigma(n)$ denotes the sum of divisors of $n$ ). As a hint, you are given that $641|2^{32}+1$ .

Individual Finals A The sequence of positive real numbers $(x_n)$ is defined recursively as follows: $x_1 = 1$ , and for $n \geq 2$ ,

\[x_{n} = 
\begin{cases}
nx_{n-1} & \quad \text{when }nx_{n-1}\leq 1, \\
\frac{x_{n-1}}{n} &\quad \text{otherwise}.
\end{cases}
\right.\] (Error compiling LaTeX. Unknown error_msg)

Show that there is an integer $N > 1$ such that $|x_N - 1| < 0.00001$ . Thus the elements of the sequence can get very close to 1 for large $N$ ; however, it is easy to see that they can never be 1 unless $N = 1$ .

Let $(x_n)$ be a sequence of positive integers defined as follows: $x_1$ is a fixed six-digit number and for any $n \geq 1$ , $x_{n+1}$ is a prime divisor of $x_n + 1$ . Find $x_{19} + x_{20}$ .

Using one straight cut we partition a rectangular piece of paper into two pieces. We call this one "operation". Next, we cut one of the two pieces so obtained once again, to partition [i]this piece[/i] into two smaller pieces (i.e. we perform the operation on any [i]one[/i] of the pieces obtained). We continue this process, and so, after each operation we increase the number of pieces of paper by $1$ . What is the minimum number of operations needed to get $47$ pieces of $46$ -sided polygons? [obviously there will be other pieces too, but we will have at least $47$ (not necessarily [i]regular[/i]) $46$ -gons.]

Algebra B If $\phi$ is the Golden Ratio, we know that $\frac1\phi = \phi - 1$ . Define a new positive real number, called $\phi_d$ , where $\frac1{\phi_d} = \phi_d - d$ (so $\phi = \phi_1$ ). Given that $\phi_{2009} = \frac{a + \sqrt{b}}{c}$ , $a, b, c$ positive integers, and the greatest common divisor of $a$ and $c$ is 1, find $a + b + c$ .

Let $p(x)$ be the polynomial with leading coefficent 1 and rational coefficents, such that $p\left(\sqrt{3 + \sqrt{3 + \sqrt{3 + \ldots}}}\right) = 0,$ and with the least degree among all such polynomials. Find $p(5)$ .

Find the root that the following three polynomials have in common: $\begin{align*} & x^3+41x^2-49x-2009 \\ & x^3 + 5x^2-49x-245 \\ & x^3 + 39x^2 - 117x - 1435\end{align*}$

Given that $P(x)$ is the least degree polynomial with rational coefficients such that $P(\sqrt{2} + \sqrt{3}) = \sqrt{2},$ find $P(10)$ .

Let $x_1,x_2,\ldots, x_{10}$ be non-negative real numbers such that $\frac{x_1}{1}+\frac{x_2}{2}+\ldots+\frac{x_{10}}{10}\leq9$ . Find the maximum possible value of $\frac{{x_1}^2}{1}+\frac{{x_2}^2}{2}+\ldots+\frac{{x_{10}}^2}{10}$ .

Find the smallest positive $\alpha$ (in degrees) for which all the numbers $\cos{\alpha},\cos{2\alpha},\ldots,\cos{2^n\alpha},\ldots$ are negative.

Find the maximal positive integer $n$ , so that for any real number $x$ we have $\sin^{n}{x}+\cos^{n}{x} \geq \frac{1}{n}$ .

Find the number of functions $f:\mathbb{Z}\mapsto\mathbb{Z}$ for which $f(h+k)+f(hk)=f(h)f(k)+1$ , for all integers $h$ and $k$ .

Combinatorics B Three people, John, Macky, and Rik, play a game of passing a basketball from one to another. Find the number of ways of passing the ball starting with Macky and reaching Macky again at the end of the seventh pass.

Find the number of subsets of $\{1,2,\ldots,7\}$ that do not contain two consecutive integers.

It is known that a certain mechanical balance can measure any object of integer mass anywhere between 1 and 2009 (both included). This balance has $k$ weights of integral values. What is the minimum $k$ for which there exist weights that satisfy this condition?

How many strings of ones and zeroes of length 10 are there such that there is an even number of ones, and no zero follows another zero?

We divide up the plane into disjoint regions using a circle, a rectangle and a triangle. What is the greatest number of regions that we can get?

There are $n$ players in a round-robin ping-pong tournament (i.e. every two persons will play exactly one game). After some matches have been played, it is known that the total number of matches that have been played among any $n-2$ people is equal to $3^k$ (where $k$ is a fixed integer). Find the sum of all possible values of $n$ .

We have a $6 \times 6$ square, partitioned into 36 unit squares. We select some of these unit squares and draw some of their diagonals, subject to the condition that no two diagonals we draw have any common points. What is the maximal number of diagonals that we can draw?

We randomly choose 5 distinct positive integers less than or equal to 90. What is the floor of 10 times the expected value of the fourth largest number?

Geometry B Find 100 times the area of a regular dodecagon inscribed in a unit circle. Round your answer to the nearest integer if necessary. $[asy] defaultpen(linewidth(0.7)); real theta = 17; pen dr = rgb(0.8,0,0), dg = rgb(0,0.6,0), db = rgb(0,0,0.6)+linewidth(1); draw(unitcircle,dg); for(int i = 0; i < 12; ++i) { draw(dir(30*i+theta)--dir(30*(i+1)+theta), db); dot(dir(30*i+theta),Fill(rgb(0.8,0,0))); } dot(dir(theta),Fill(dr)); dot((0,0),Fill(dr)); [/asy]$

A triangle has sides of lengths 5, 6, 7. What is 60 times the square of the radius of the inscribed circle?

A rectangular piece of paper $ABCD$ has sides of lengths $AB = 1$ , $BC = 2$ . The rectangle is folded in half such that $AD$ coincides with $BC$ and $EF$ is the folding line. Then fold the paper along a line $BM$ such that the corner $A$ falls on line $EF$ . How large, in degrees, is $\angle ABM$ ? $[asy] size(180); pathpen = linewidth(0.7); pointpen = black+linewidth(3); pointfontpen = fontsize(10); pen dd = linewidth(0.7) + linetype("4 4"), dr = rgb(0.8,0,0), dg = rgb(0,0.6,0), db = rgb(0,0,0.6)+linewidth(1); pair A=(0,1), B=(0,0), C=(2,0), D=(2,1), E=A/2, F=(2,.5), M=(0.5,1), N=reflect(B,M)*A; D(B--M--D("N",N,NE)--B--D("C",C,SE)--D("D",D,NE)--M); D(D("M",M,plain.N)--D("A",A,NW)--D("B",B,SW),dd); D(D("E",E,W)--D("F",F,plain.E),dd); [/asy]$

Tetrahedron $ABCD$ has sides of lengths, in increasing order, 7, 13, 18, 27, 36, 41. If $AB=41$ , then what is the length of $CD$ ?

A polygon is called concave if it has at least one angle strictly greater than $180^{\circ}$ . What is the maximum number of symmetries that an 11-sided concave polygon can have? (A [i]symmetry[/i] of a polygon is a way to rotate or reflect the plane that leaves the polygon unchanged.)

In the following diagram (not to scale), $A$ , $B$ , $C$ , $D$ are four consecutive vertices of an 18-sided regular polygon with center $O$ . Let $P$ be the midpoint of $AC$ and $Q$ be the midpoint of $DO$ . Find $\angle OPQ$ in degrees. $[asy] pathpen = linewidth(0.7); pointpen = black+linewidth(3); pointfontpen = fontsize(10); pen dd = linewidth(0.7) + linetype("4 4"); real n = 10, start = 360/n*6-15; pair O=(0,0), A=dir(start), B=dir(start+360/n), C=dir(start+2*360/n), D=dir(start+3*360/n), P=(A+C)/2, Q=(O+D)/2; D(D("O",O,NE)--D("A",A,W)--D("B",B,SW)--D("C",C,S)--D("D",D,SE)--O--D("P",P,1.6*dir(95))--D("Q",Q,NE)); D(A--C); D(A--(A+dir(start-360/n))/2, dd); D(D--(D+dir(start+4*360/n))/2, dd); [/asy]$

Lines $l$ and $m$ are perpendicular. Line $l$ partitions a convex polygon into two parts of equal area, and partitions the projection of the polygon onto $m$ into two line segments of length $a$ and $b$ respectively. Determine the maximum value of $\left\lfloor \frac{1000a}{b} \right\rfloor$ . (The floor notation $\lfloor x \rfloor$ denotes largest integer not exceeding $x$ )

Consider the solid with 4 triangles and 4 regular hexagons as faces, where each triangle borders 3 hexagons, and all the sides are of length 1. Compute the [i]square[/i] of the volume of the solid. Express your result in reduced fraction and concatenate the numerator with the denominator (e.g., if you think that the square is $\frac{1734}{274}$ , then you would submit 1734274).

Number Theory B

Find the number of pairs of integers $x$ and $y$ such that $x^2 + xy + y^2 = 28$ .

Suppose you are given that for some positive integer $n$ , $1! + 2! + \ldots + n!$ is a perfect square. Find the sum of all possible values of $n$ .

You are given that $17! = 355687ab8096000$ for some digits $a$ and $b$ . Find the two-digit number $\overline{ab}$ that is missing above.

Find the number of ordered pairs $(a, b)$ of positive integers that are solutions of the following equation: $a^2 + b^2 = ab(a+b).$

Find the sum of all prime numbers $p$ which satisfy $p = a^4 + b^4 + c^4 - 3$ for some primes (not necessarily distinct) $a$ , $b$ and $c$ .

Find the sum of all integers $x$ for which there is an integer $y$ , such that $x^3-y^3=xy+61$ .

Suppose that for some positive integer $n$ , the first two digits of $5^n$ and $2^n$ are identical. Suppose the first two digits are $a$ and $b$ in this order. Find the two-digit number $\overline{ab}$ .

Let $s(m)$ denote the sum of the digits of the positive integer $m$ . Find the largest positive integer that has no digits equal to zero and satisfies the equation $2^{s(n)} = s(n^2).$

Individual Finals B You have an unlimited supply of monominos, dominos, and L-trominos. How many ways, in terms of $n$ , can you cover a $2 \times n$ grid with these shapes? Please note that you do [i]NOT[/i] have to use all the shapes. Also, you are allowed to [i]rotate[/i] any of the pieces, so they do not have to be aligned exactly as they are in the diagram below. $[asy] pen db = rgb(0,0,0.5); real r = 0.08; pair s1 = (3,0), s2 = 2*s1; fill(unitsquare, db); fill(shift(s1)*unitsquare, db); fill(shift(s1-(0,1+r))*unitsquare, db); fill(shift(s2)*unitsquare, db); fill(shift(s2-(0,1+r))*unitsquare, db); fill(shift(s2+(1+r,-1-r))*unitsquare, db);[/asy]$

For what positive integer $k$ is $\binom{100}{k} \binom{200}{k}$ maximal?

Let $(x_n)$ be a sequence of positive integers defined as follows: $x_1$ is a fixed six-digit number and for any $n \geq 1$ , $x_{n+1}$ is a prime divisor of $x_n + 1$ . Find $x_{19} + x_{20}$ .

[hide="Thread links"] Algebra A:

Combinatorics A:

Geometry A:

Number Theory A:

Individual Finals A:

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=151&t=427753

Algebra B:

Combinatorics B:

Geometry B:

Number Theory B:

Individual Finals B:

Team Round

All problems here: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=414&t=427597 (questions may depend on each other.)

Page

Toolbox

Search

2009 PUMaC Problems