Difference between revisions of "2010 PUMaC Problems"

m (Combinatorics)
Line 51: Line 51:
 
[[2011 PuMAC Problems/Combinatorics Problem A3|Solution]]
 
[[2011 PuMAC Problems/Combinatorics Problem A3|Solution]]
  
Erick stands in the square in the 2nd row and 2nd column of a 5 by 5 chessboard.  There are $1 bills in the top left and bottom right squares, and there are $5 bills in the top right and bottom left squares, as shown below.
+
Erick stands in the square in the 2nd row and 2nd column of a 5 by 5 chessboard.  There are $1 bills in the top left and bottom right squares, and there are $5 bills in the top right and bottom left squares, as shown below.
 
<cmath>\begin{tabular}{|p{1em}|p{1em}|p{1em}|p{1em}|p{1em}|}
 
<cmath>\begin{tabular}{|p{1em}|p{1em}|p{1em}|p{1em}|p{1em}|}
 
\hline
 
\hline
&#036;1 & & & & &#036;5 \
+
$1 & & & &$5 \
 
\hline
 
\hline
 
& E & & &\
 
& E & & &\
Line 62: Line 62:
 
& & & &\
 
& & & &\
 
\hline
 
\hline
&#036;5 & & & & &#036;1 \
+
$5 & & & &$1 \
 
\hline \end{tabular}</cmath>
 
\hline \end{tabular}</cmath>
 
Every second, Erick randomly chooses a square adjacent to the one he currently stands in (that is, a square sharing an edge with the one he currently stands in) and moves to that square.  When Erick reaches a square with money on it, he takes it and quits.  The expected value of Erick's winnings in dollars is <math>m/n</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers.  Find <math>m+n</math>.
 
Every second, Erick randomly chooses a square adjacent to the one he currently stands in (that is, a square sharing an edge with the one he currently stands in) and moves to that square.  When Erick reaches a square with money on it, he takes it and quits.  The expected value of Erick's winnings in dollars is <math>m/n</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers.  Find <math>m+n</math>.

Revision as of 18:54, 10 March 2015

Template:PuMAC Problems

Division A

Algebra

Find the sum of the coefficients of the polynomial $(63x-61)^4$.

Solution

Calculate ${\sum_{n=1}^\infty\left(\lfloor\sqrt[n]{2010}\rfloor-1\right)}$ where $\lfloor x\rfloor$ is the largest integer less than or equal to $x$.

Solution

Let $S$ be the sum of all real $x$ such that $4^x = x^4$. Find the nearest integer to $S$.

Solution

Define ${f(x) = x + \sqrt{x + \sqrt{x + \sqrt{x + \sqrt{x + \ldots}}}}}$. Find the smallest integer $x$ such that $f(x)\ge50\sqrt{x}$.

Solution

Let $f(x)=3x^3-5x^2+2x-6$. If the roots of $f$ are given by $\alpha$, $\beta$, and $\gamma$, find \[\left(\frac{1}{\alpha-2}\right)^2+\left(\frac{1}{\beta-2}\right)^2+\left(\frac{1}{\gamma-2}\right)^2.\]

Solution

Assume that $f(a+b) = f(a) + f(b) + ab$, and that $f(75) - f(51) = 1230$. Find $f(100)$.

Solution

The expression $\sin2^\circ\sin4^\circ\sin6^\circ\cdots\sin90^\circ$ is equal to $p\sqrt{5}/2^{50}$, where $p$ is an integer. Find $p$.

Solution

Let $p$ be a polynomial with integer coefficients such that $p(15)=6$, $p(22)=1196$, and $p(35)=26$. Find an integer $n$ such that $p(n)=n+82$.

Solution

Combinatorics

PUMaCDonalds, a newly-opened fast food restaurant, has 5 menu items. If the first 4 customers each choose one menu item at random, the probability that the 4th customer orders a previously unordered item is $m/n$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

Solution

Let $\underline{xyz}$ represent the three-digit number with hundreds digit $x$, tens digit $y$, and units digit $z$, and similarly let $\underline{yz}$ represent the two-digit number with tens digit $y$ and units digit $z$. How many three-digit numbers $\underline{abc}$, none of whose digits are 0, are there such that $\underline{ab}>\underline{bc}>\underline{ca}$?

Solution

Sterling draws 6 circles on the plane, which divide the plane into regions (including the unbounded region). What is the maximum number of resulting regions?

Solution

Erick stands in the square in the 2nd row and 2nd column of a 5 by 5 chessboard. There are $1 bills in the top left and bottom right squares, and there are $5 bills in the top right and bottom left squares, as shown below. \[\begin{tabular}{|p{1em}|p{1em}|p{1em}|p{1em}|p{1em}|} \hline $1 & & & &$5 \\ \hline & E & & &\\ \hline & & & &\\ \hline & & & &\\ \hline $5 & & & &$1 \\ \hline \end{tabular}\] Every second, Erick randomly chooses a square adjacent to the one he currently stands in (that is, a square sharing an edge with the one he currently stands in) and moves to that square. When Erick reaches a square with money on it, he takes it and quits. The expected value of Erick's winnings in dollars is $m/n$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

Solution

We say that a rook is ``attacking" another rook on a chessboard if the two rooks are in the same row or column of the chessboard and there is no piece directly between them. Let $n$ be the maximum number of rooks that can be placed on a $6\times 6$ chessboard such that each rook is attacking at most one other. How many ways can $n$ rooks be placed on a $6\times 6$ chessboard such that each rook is attacking at most one other?

Solution

All the diagonals of a regular decagon are drawn. A regular decagon satisfies the property that if three diagonals concur, then one of the three diagonals is a diameter of the circumcircle of the decagon. How many distinct intersection points of diagonals are in the interior of the decagon?

Solution

Matt is asked to write the numbers from 1 to 10 in order, but he forgets how to count. He writes a permutation of the numbers $\{1, 2, 3\ldots , 10\}$ across his paper such that:

  • The leftmost number is 1.
  • The rightmost number is 10.
  • Exactly one number (not including 1 or 10) is less than both the number to its immediate left and the number to its immediate right.[/list]

How many such permutations are there?

Solution

Let $N$ be the sum of all binomial coefficients $\binom{a}{b}$ such that $a$ and $b$ are nonnegative integers and $a+b$ is an even integer less than 100. Find the remainder when $N$ is divided by 144. (Note: $\binom{a}{b} = 0$ if $a<b$, and $\binom{0}{0} = 1$.)

Solution

Geometry

As in the following diagram, square $ABCD$ and square $CEFG$ are placed side by side (i.e. $C$ is between $B$ and $E$ and $G$ is between $C$ and $D$). If $CE = 14$, $AB > 14$, compute the minimal area of $\triangle AEG$. [asy] size(120); defaultpen(linewidth(0.7)+fontsize(10));  pair D2(real x, real y) {  pair P = (x,y);  dot(P,linewidth(3)); return P; } int big = 30, small = 14; filldraw((0,big)--(big+small,0)--(big,small)--cycle, rgb(0.9,0.5,0.5)); draw(scale(big)*unitsquare); draw(shift(big,0)*scale(small)*unitsquare); label("$A$",D2(0,big),NW); label("$B$",D2(0,0),SW); label("$C$",D2(big,0),SW); label("$D$",D2(big,big),N); label("$E$",D2(big+small,0),SE); label("$F$",D2(big+small,small),NE); label("$G$",D2(big,small),NE); [/asy]

Solution

In a rectangular plot of land, a man walks in a very peculiar fashion. Labeling the corners $ABCD$, he starts at $A$ and walks to $C$. Then, he walks to the midpoint of side $AD$, say $A_1$. Then, he walks to the midpoint of side $CD$ say $C_1$, and then the midpoint of $A_1D$ which is $A_2$. He continues in this fashion, indefinitely. The total length of his path if $AB=5$ and $BC=12$ is of the form $a + b\sqrt{c}$. Find $\frac{abc}{4}$.

Solution

Triangle $ABC$ has $AB = 4$, $AC = 5$, and $BC = 6$. An angle bisector is drawn from angle $A$, and meets $BC$ at $M$. What is the nearest integer to $100 \frac{AM}{CM}$?

Solution

In regular hexagon $ABCDEF$, $AC$, $CE$ are two diagonals. Points $M$, $N$ are on $AC$, $CE$ respectively and satisfy $AC: AM = CE: CN = r$. Suppose $B, M, N$ are collinear, find $100r^2$. (diagram goes here) [asy] size(120); defaultpen(linewidth(0.7)+fontsize(10));  pair D2(pair P) {  dot(P,linewidth(3)); return P; } pair A=dir(0), B=dir(60), C=dir(120), D=dir(180), E=dir(240), F=dir(300), N=(4*E+C)/5,M=intersectionpoints(A--C,B--N)[0]; draw(A--B--C--D--E--F--cycle); draw(A--C--E); draw(B--N); label("$A$",D2(A),E); label("$B$",D2(B),NE); label("$C$",D2(C),NW); label("$D$",D2(D),W); label("$E$",D2(E),SW); label("$F$",D2(F),SE); label("$M$",D2(M),(0,-1.5)); label("$N$",D2(N),SE); [/asy] Solution

A cuboctahedron is a solid with 6 square faces and 8 equilateral triangle faces, with each edge adjacent to both a square and a triangle (see picture). Suppose the ratio of the volume of an octahedron to a cuboctahedron with the same side length is $r$. Find $100r^2$. (diagram goes here)

Solution

In the following diagram, a semicircle is folded along a chord $AN$ and intersects its diameter $MN$ at $B$. Given that $MB : BN = 2 : 3$ and $MN = 10$. If $AN = x$, find $x^2$. [asy] size(120); defaultpen(linewidth(0.7)+fontsize(10));  pair D2(pair P) {  dot(P,linewidth(3)); return P; } real r = sqrt(80)/5; pair M=(-1,0),  N=(1,0), A=intersectionpoints(arc((M+N)/2, 1, 0, 180),circle(N,r))[0], C=intersectionpoints(circle(A,1),circle(N,1))[0], B=intersectionpoints(circle(C,1),M--N)[0]; draw(arc((M+N)/2, 1, 0, 180)--cycle); draw(A--N); draw(arc(C,1,180,180+2*aSin(r/2))); label("$A$",D2(A),NW); label("$B$",D2(B),SW); label("$M$",D2(M),S); label("$N$",D2(N),SE); [/asy] Solution

Square $ABCD$ is divided into four rectangles by $EF$ and $GH$. $EF$ is parallel to $AB$ and $GH$ parallel to $BC$. $\angle BAF = 18^\circ$. $EF$ and $GH$ meet at point $P$. The area of rectangle $PFCH$ is twice that of rectangle $AGPE$. Given that the value of $\angle FAH$ in degrees is $x$, find the nearest integer to $x$. [asy] size(100); defaultpen(linewidth(0.7)+fontsize(10));  pair D2(pair P) {  dot(P,linewidth(3)); return P; } // NOTE: I've tampered with the angles to make the diagram not-to-scale. The correct numbers should be 72 instead of 76, and 45 instead of 55.  pair A=(0,1),  B=(0,0), C=(1,0), D=(1,1), F=intersectionpoints(A--A+2*dir(-76),B--C)[0], H=intersectionpoints(A--A+2*dir(-76+55),D--C)[0], E=F+(0,1), G=H-(1,0), P=intersectionpoints(E--F,G--H)[0]; draw(A--B--C--D--cycle); draw(F--A--H); draw(E--F); draw(G--H);  label("$A$",D2(A),NW); label("$B$",D2(B),SW); label("$C$",D2(C),SE); label("$D$",D2(D),NE); label("$E$",D2(E),plain.N); label("$F$",D2(F),S); label("$G$",D2(G),W); label("$H$",D2(H),plain.E); label("$P$",D2(P),SE);  [/asy] Solution

There is a point source of light in an empty universe. What is the minimum number of solid balls (of any size) one must place in space so that any light ray emanating from the light source intersects at least one ball?

Solution

Number Theory

Find the smallest positive integer $n$ such that $n^4 + (n+1)^4$ is composite.

Solution

Find the largest positive integer $n$ such that $\sigma(n) = 28$, where $\sigma(n)$ is the sum of the divisors of $n$, including $n$.

Solution

Find the sum of the first 5 positive integers $n$ such that $n^2 - 1$ is the product of 3 distinct primes.

Solution

Find the largest positive integer $n$ such that $n\varphi(n)$ is a perfect square. ($\varphi(n)$ is the number of integers $k$, $1 \leq k \leq n$ that are relatively prime to $n$)

Solution

Given that $x$, $y$ are positive integers with $x(x+1)|y(y+1)$, but neither $x$ nor $x+1$ divides either of $y$ or $y+1$, and $x^2 + y^2$ as small as possible, find $x^2 + y^2$.

Solution

Find the numerator of \[\frac{1010\overbrace{11 \ldots 11}^{2011 \text{ ones}}0101}{1100\underbrace{11 \ldots 11}_{2011\text{ ones}}0011}\] when reduced.

Solution

Let $n$ be the number of polynomial functions from the integers modulo $2010$ to the integers modulo $2010$. $n$ can be written as $n = p_1 p_2 \cdots p_k$, where the $p_i$s are (not necessarily distinct) primes. Find $p_1 + p_2 + \cdots + p_n$.

Solution

A consecutive pythagorean triple is a pythagorean triple of the form $a^2 + (a+1)^2 = b^2$, $a$ and $b$ positive integers. Given that $a$, $a+1$, and $b$ form the third consecutive pythagorean triple, find $a$.

Solution

Division B

Algebra

Let the operation $\bigstar$ be defined by $x\bigstar y=y^x-xy$. Calculate $(3\bigstar4)-(4\bigstar3)$.

Let $p(x) = x^2 + x + 1$. Find the fourth smallest prime $q$ such that $p(n)$ is divisble by $q$ for some integer $n$.

Write ${\frac{1}{\sqrt[5]{2} - 1} = a + b\sqrt[5]{2} + c\sqrt[5]{4} + d\sqrt[5]{8} + e\sqrt[5]{16}}$, with $a$, $b$, $c$, $d$, and $e$ integers. Find $a^2 + b^2 + c^2 + d^2 + e^2$.

Let $S$ be the sum of all real $x$ such that $4^x = x^4$. Find the nearest integer to $S$.

Let $x$ be a real root of the polynomial $p(x)=x^3-3x+3$. Find $x^9+81x^2$.

Define ${f(x) = x + \sqrt{x + \sqrt{x + \sqrt{x + \sqrt{x + \ldots}}}}}$. Find the smallest integer $x$ such that $f(x)\ge50\sqrt{x}$.

Let $f$ be a function such that $f(x)+f(x+1)=2^x$ and $f(0)=2010$. Find the last two digits of $f(2010)$.

The expression $\sin2^\circ\sin4^\circ\sin6^\circ\cdots\sin90^\circ$ is equal to $p\sqrt{5}/2^{50}$, where $p$ is an integer. Find $p$.

Combinatorics

The Princeton University Band plays a setlist of 8 distinct songs, 3 of which are tiring to play. If the Band can't play any two tiring songs in a row, how many ways can the band play its 8 songs?

PUMaCDonalds, a newly-opened fast food restaurant, has 5 menu items. If the first 4 customers each choose one menu item at random, the probability that the 4th customer orders a previously unordered item is $m/n$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$. % Yeah, I stole the PUMaCDonalds joke from another round (the team round?). We can change the problem statement to "A newly-opened fast food restaurant has 5 menu items..." if that's better. Let $\underline{xyz}$ represent the three-digit number with hundreds digit $x$, tens digit $y$, and units digit $z$, and similarly let $\underline{yz}$ represent the two-digit number with tens digit $y$ and units digit $z$. How many three-digit numbers $\underline{abc}$, none of whose digits are 0, are there such that $\underline{ab}>\underline{bc}>\underline{ca}$?

Sterling draws 6 circles on the plane, which divide the plane into regions (including the unbounded region). What is the maximum number of resulting regions?

$3n$ people take part in a chess tournament: $n$ girls and $2n$ boys. Each participant plays with each of the others exactly once. There were no ties and the number of games won by the girls is $\frac75$ the number of games won by the boys. How many people took part in the tournament?

A regular pentagon is drawn in the plane, along with all its diagonals. All its sides and diagonals are extended infinitely in both directions, dividing the plane into regions, some of which are unbounded. An ant starts in the center of the pentagon, and every second, the ant randomly chooses one of the edges of the region it's in, with an equal probability of choosing each edge, and crosses that edge into another region. If the ant enters an unbounded region, it explodes. After first leaving the central region of the pentagon, let $x$ be the expected number of times the ant re-enters the central region before it explodes. Find the closest integer to $100x$.

We say that a rook is ``attacking" another rook on a chessboard if the two rooks are in the same row or column of the chessboard and there is no piece directly between them. Let $n$ be the maximum number of rooks that can be placed on a $6\times 6$ chessboard such that each rook is attacking at most one other. How many ways can $n$ rooks be placed on a $6\times 6$ chessboard such that each rook is attacking at most one other?

Matt is asked to write the numbers from 1 to 10 in order, but he forgets how to count. He writes a permutation of the numbers $\{1, 2, 3\ldots , 10\}$ across his paper such that:

  • The leftmost number is 1.
  • The rightmost number is 10.
  • Exactly one number (not including 1 or 10) is less than both the number to its immediate left and the number to its immediate right.

How many such permutations are there?

Geometry

In a polygon, every external angle is one sixth of its corresponding internal angle. How many sides does the polygon have?

On rectangular coordinates, point $A = (1,2)$, $B = (3,4)$. $P = (a, 0)$ is on $x$-axis. Given that $P$ is chosen such that $AP + PB$ is minimized, compute $60a$.

As in the following diagram, square $ABCD$ and square $CEFG$ are placed side by side (i.e. $C$ is between $B$ and $E$ and $G$ is between $C$ and $D$). Now $CE = 14$, $AB > 14$, compute the minimal area of $\triangle AEG$. (diagram goes here)

Unit square $ABCD$ is divided into four rectangles by $EF$ and $GH$, with $BF = \frac14$. $EF$ is parallel to $AB$ and $GH$ parallel to $BC$. $EF$ and $GH$ meet at point $P$. Suppose $BF + DH = FH$, calculate the nearest integer to the degree of $\angle FAH$. (diagram goes here)

In a rectangular plot of land, a man walks in a very peculiar fashion. Labeling the corners $ABCD$, he starts at $A$ and walks to $C$. Then, he walks to the midpoint of side $AD$, say $A_1$. Then, he walks to the midpoint of side $CD$ say $C_1$, and then the midpoint of $A_1D$ which is $A_2$. He continues in this fashion, indefinitely. The total length of his path if $AB=5$ and $BC=12$ is of the form $a + b\sqrt{c}$. Find $\frac{abc}{4}$.

In regular hexagon $ABCDEF$, $AC$, $CE$ are two diagonals. Points $M$, $N$ are on $AC$, $CE$ respectively and satisfy $AC: AM = CE: CN = r$. Suppose $B, M, N$ are collinear, find $100r^2$. (diagram goes here)

A cuboctahedron is a solid with 6 square faces and 8 equilateral triangle faces, with each edge adjacent to both a square and a triangle (see picture). Suppose the ratio of the volume of an octahedron to a cuboctahedron with the same side length is $r$. Find $100r^2$. (diagram goes here)

Point $P$ is in the interior of $\triangle ABC$. The side lengths of $ABC$ are $AB = 7$, $BC = 8$, $CA = 9$. The three foots of perpendicular lines from $P$ to sides $BC$, $CA$, $AB$ are $D$, $E$, $F$ respectively. Suppose the minimal value of $\frac{BC}{PD} + \frac{CA}{PE} + \frac{AB}{PF}$ can be written as $\frac{a}{b}\sqrt{c}$, where $\gcd(a,b) = 1$ and $c$ is square free, calculate $abc$. (diagram goes here)

Number Theory

Find the positive integer less than 18 with the most positive divisors.

Let $f(n)$ be the sum of the digits of $n$. Find ${\sum_{n=1}^{99}f(n)}$.

Find the smallest positive integer $n$ such that $n^4 + (n+1)^4$ is composite.

Find the sum of the first 5 positive integers $n$ such that $n^2 - 1$ is the product of 3 distinct primes.

Given that $x$, $y$, and $z$ are positive integers such that ${\frac{x}{y} + \frac{y}{z} + \frac{z}{x} = 2}$. Find the sum of all possible $x$ values.

Given that $x$, $y$ are positive integers with $x(x+1)|y(y+1)$, but neither $x$ nor $x+1$ divides either of $y$ or $y+1$, and $x^2 + y^2$ as small as possible, find $x^2 + y^2$.

Find the numerator of \[\frac{1010\overbrace{11 \ldots 11}^{2011 \text{ ones}}0101}{1100\underbrace{11 \ldots 11}_{2011\text{ ones}}0011}\] when reduced.

Let $N$ be the number of (positive) divisors of $2010^{2010}$ ending in the digit $2$. What is the remainder when $N$ is divided by 2010?

Template:PuMAC box