The diagram shows a rectangle that has been dissected into nine non-overlapping squares. Given that the width and the height of the rectangle are relatively prime positive integers, find the perimeter of the rectangle. [asy] defaultpen(linewidth(0.7)); draw((0,0)--(69,0)--(69,61)--(0,61)--(0,0));draw((36,0)--(36,36)--(0,36)); draw((36,33)--(69,33));draw((41,33)--(41,61));draw((25,36)--(25,61)); draw((34,36)--(34,45)--(25,45)); draw((36,36)--(36,38)--(34,38)); draw((36,38)--(41,38)); draw((34,45)--(41,45));[/asy]

Let $n$ and $k$ be relatively prime positive integers with $k<n$. Each number in the set $M=\{1,2,3,\ldots,n-1\}$ is colored either blue or white. For each $i$ in $M$, both $i$ and $n-i$ have the same color. For each $i\ne k$ in $M$ both $i$ and $|i-k|$ have the same color. Prove that all numbers in $M$ must have the same color.

Prove the among $16$ consecutive integers it is always possible to find one which is relatively prime to all the rest.

A [i]triangulation[/i] of a polygon is a subdivision of the polygon into triangles meeting edge to edge, with the property that the set of triangle vertices coincides with the set of vertices of the polygon. Adam randomly selects a triangulation of a regular $180$-gon. Then, Bob selects one of the $178$ triangles in this triangulation. The expected number of $1^\circ$ angles in this triangle can be expressed as $\frac{a}{b}$, where $a$ and $b$ are relatively prime positive integers. Compute $100a + b$. [i]Proposed by Lewis Chen[/i]

Let $a_{1}, a_{2}, \cdots, a_{k}$ be relatively prime positive integers. Determine the largest integer which cannot be expressed in the form \[x_{1}a_{2}a_{3}\cdots a_{k}+x_{2}a_{1}a_{3}\cdots a_{k}+\cdots+x_{k}a_{1}a_{2}\cdots a_{k-1}\] for some nonnegative integers $x_{1}, x_{2}, \cdots, x_{k}$.

Compute the number of positive integers $n < 2012$ that share exactly two positive factors with 2012. [i]Proposed by Aaron Lin[/i]

Let $p$ be the probability that, in the process of repeatedly flipping a fair coin, one will encounter a run of 5 heads before one encounters a run of 2 tails. Given that $p$ can be written in the form $m/n$ where $m$ and $n$ are relatively prime positive integers, find $m+n$.

How many positive integers $n$ are there such that there are exactly $20$ positive odd integers that are less than $n$ and relatively prime with $n$? $ \textbf{(A)}\ 5 \qquad\textbf{(B)}\ 4 \qquad\textbf{(C)}\ 3 \qquad\textbf{(D)}\ 2 \qquad\textbf{(E)}\ \text{None of above} $

Let $a$ and $b$ be relatively prime positive integers, $b$ even. For each positive integer $q$, let $p=p(q)$ be chosen so that $$ \left| \frac{p}{q} - \frac{a}{b} \right|$$ is a minimum. Prove that $$ \lim_{n \to \infty} \sum_{q=1 }^{n} \frac{ q\left| \frac{p}{q} - \frac{a}{b} \right|}{n} = \frac{1}{4}.$$

Let $a$ and $b$ be relatively prime integers with $a>b>0$ and $\tfrac{a^3-b^3}{(a-b)^3}=\tfrac{73}{3}$. What is $a-b$? $ \textbf{(A)}\ 1 \qquad\textbf{(B)}\ 2 \qquad\textbf{(C)}\ 3 \qquad\textbf{(D)}\ 4 \qquad\textbf{(E)}\ 5 $

Call a set of positive integers "conspiratorial" if no three of them are pairwise relatively prime. What is the largest number of elements in any "conspiratorial" subset of the integers $1$ to $16$?

$n$ is a natural number larger than $3$ and denote all positive coprime numbers with $n$ as $1= b_1 < b_2 < \cdots b_k$. For a positive integer $m$ which is larger than $3$ and is coprime with $n$, let $A$ be the set of tuples $(a_1,a_2, \cdots a_k)$ satisfying the condition. $$\textbf{Condition}: \text{For all integers } i, 0 \le a_i < m \text{ and } a_1b_1 + a_2b_2 + \cdots a_kb_k \text{ is a mutiple of } n$$ For elements of $A$, show that the difference of number of elements such that $a_1 = 1$ and the number of elements such that $a_2 = 2$ maximum $1$

Consider the set of all fractions $\tfrac{x}{y},$ where $x$ and $y$ are relatively prime positive integers. How many of these fractions have the property that if both numerator and denominator are increased by $1$, the value of the fraction is increased by $10\%$? $ \textbf{(A) }0\qquad\textbf{(B) }1\qquad\textbf{(C) }2\qquad\textbf{(D) }3\qquad\textbf{(E) }\text{infinitely many} $

The polynomial $P$ is a quadratic with integer coefficients. For every positive integer $n$, the integers $P(n)$ and $P(P(n))$ are relatively prime to $n$. If $P(3) = 89$, what is the value of $P(10)$?

For how many ordered pairs of positive integers $ (m,n)$, $ m \cdot n$ divides $ 2008 \cdot 2009 \cdot 2010$ ? $\textbf{(A)}\ 2\cdot3^7\cdot 5 \qquad\textbf{(B)}\ 2^5\cdot3\cdot 5 \qquad\textbf{(C)}\ 2^5\cdot3^7\cdot 5 \qquad\textbf{(D)}\ 2^3\cdot3^5\cdot 5^2 \qquad\textbf{(E)}\ \text{None}$

Let $a$ and $b$ be the two possible values of $\tan\theta$ given that \[\sin\theta + \cos\theta = \dfrac{193}{137}.\] If $a+b=m/n$, where $m$ and $n$ are relatively prime positive integers, compute $m+n$.

In January Jeff’s investment went up by three quarters. In February it went down by one quarter. In March it went up by one third. In April it went down by one fifth. In May it went up by one seventh. In June Jeff’s investment fell by $\frac{m}{n}$ where $m$ and $n$ are relatively prime positive integers. If Jeff’s investment was worth the same amount at the end of June as it had been at the beginning of January, find $m + n$.

How many positive integers $n$ are there such that there are $20$ positive integers that are less than $n$ and relatively prime with $n$? $ \textbf{(A)}\ 1 \qquad \textbf{(B)}\ 2 \qquad \textbf{(C)}\ 3 \qquad \textbf{(D)}\ 4 \qquad \textbf{(E)}\ \text{None}$

Four lighthouses are located at points $ A$, $ B$, $ C$, and $ D$. The lighthouse at $ A$ is $ 5$ kilometers from the lighthouse at $ B$, the lighthouse at $ B$ is $ 12$ kilometers from the lighthouse at $ C$, and the lighthouse at $ A$ is $ 13$ kilometers from the lighthouse at $ C$. To an observer at $ A$, the angle determined by the lights at $ B$ and $ D$ and the angle determined by the lights at $ C$ and $ D$ are equal. To an observer at $ C$, the angle determined by the lights at $ A$ and $ B$ and the angle determined by the lights at $ D$ and $ B$ are equal. The number of kilometers from $ A$ to $ D$ is given by $ \displaystyle\frac{p\sqrt{r}}{q}$, where $ p$, $ q$, and $ r$ are relatively prime positive integers, and $ r$ is not divisible by the square of any prime. Find $ p\plus{}q\plus{}r$,

Find all prime numbers $ p,q$ less than 2005 and such that $ q|p^2 \plus{} 4$, $ p|q^2 \plus{} 4$.

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$.

A paper cup has a base that is a circle with radius $r$, a top that is a circle with radius $2r$, and sides that connect the two circles with straight line segments as shown below. This cup has height $h$ and volume $V$. A second cup that is exactly the same shape as the first is held upright inside the first cup so that its base is a distance of $\tfrac{h}2$ from the base of the first cup. The volume of liquid that will t inside the first cup and outside the second cup can be written $\tfrac{m}{n}\cdot V$ where $m$ and $n$ are relatively prime positive integers. Find $m + n$. [asy] pair s = (10,1); draw(ellipse((0,0),4,1)^^ellipse((0,-6),2,.5)); fill((3,-6)--(-3,-6)--(0,-2.1)--cycle,white); draw((4,0)--(2,-6)^^(-4,0)--(-2,-6)); draw(shift(s)*ellipse((0,0),4,1)^^shift(s)*ellipse((0,-6),2,.5)); fill(shift(s)*(3,-6)--shift(s)*(-3,-6)--shift(s)*(0,-2.1)--cycle,white); draw(shift(s)*(4,0)--shift(s)*(2,-6)^^shift(s)*(-4,0)--shift(s)*(-2,-6)); pair s = (10,-2); draw(shift(s)*ellipse((0,0),4,1)^^shift(s)*ellipse((0,-6),2,.5)); fill(shift(s)*(3,-6)--shift(s)*(-3,-6)--shift(s)*(0,-4.1)--cycle,white); draw(shift(s)*(4,0)--shift(s)*(2,-6)^^shift(s)*(-4,0)--shift(s)*(-2,-6)); //darn :([/asy]

For each $n\in \mathbb{N}$, let $S(n)$ be the sum of all numbers in the set $\{ 1, 2, 3, \cdots , n \}$ which are relatively prime to $n$. $(a)$ Show that $2 \cdot S(n)$ is not a perfect square for any $n$. $(b)$ Given positive integers $m, n$, with odd $n$, show that the equation $2 \cdot S(x) = y^n$ has at least one solution $(x, y)$ among positive integers such that $m|x$.

Prove that for any positive integer $ m$ there exist an infinite number of pairs of integers $(x,y)$ such that $(\text{i})$ $x$ and $y$ are relatively prime; $(\text{ii})$ $x$ divides $y^2+m;$ $(\text{iii})$ $y$ divides $x^2+m.$

Find the sum of all integers $m$ with $1 \le m \le 300$ such that for any integer $n$ with $n \ge 2$, if $2013m$ divides $n^n-1$ then $2013m$ also divides $n-1$. [i]Proposed by Evan Chen[/i]