Found problems: 698
Let for natural numbers $a,b,c$ and any natural $n$ we have that
$(abc)^n$ divides $ ((a^n-1)(b^n-1)(c^n-1)+1)^3$. Prove that then $a=b=c$.
Find the smallest integer $k$ for which the conditions
$(1)$ $a_1, a_2, a_3, \ldots$ is a nondecreasing sequence of positive integers
$(2)$ $a_n=a_{n-1}+a_{n-2}$ for all $n>2$
$(3)$ $a_9=k$
are satisfied by more than one sequence.
A polynomial $P(x)$ is called [i]nice[/i] if $P(0) = 1$ and the nonzero coefficients of $P(x)$ alternate between $1$ and $-1$ when written in order. Suppose that $P(x)$ is nice, and let $m$ and $n$ be two relatively prime positive integers. Show that
\[Q(x) = P(x^n) \cdot \frac{(x^{mn} - 1)(x-1)}{(x^m-1)(x^n-1)}\]
is nice as well.
Circles $C_1$ and $C_2$ are externally tangent, and they are both internally tangent to circle $C_3$. The radii of $C_1$ and $C_2$ are $4$ and $10$, respectively, and the centers of the three circles are all collinear. A chord of $C_3$ is also a common external tangent of $C_1$ and $C_2$. Given that the length of the chord is $\frac{m\sqrt{n}}{p}$ where $m,n,$ and $p$ are positive integers, $m$ and $p$ are relatively prime, and $n$ is not divisible by the square of any prime, find $m+n+p$.
For how many integers $ n$ is $ \frac{n}{20\minus{}n}$ the square of an integer?
$ \textbf{(A)}\ 1 \qquad
\textbf{(B)}\ 2 \qquad
\textbf{(C)}\ 3 \qquad
\textbf{(D)}\ 4 \qquad
\textbf{(E)}\ 10$
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$.
Given are 100 different positive integers. We call a pair of numbers [i]good[/i] if the ratio of these numbers is either 2 or 3. What is the maximum number of good pairs that these 100 numbers can form? (A number can be used in several pairs.)
[i]Proposed by Alexander S. Golovanov, Russia[/i]
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} $
A sequence of numbers $x_{1},x_{2},x_{3},\ldots,x_{100}$ has the property that, for every integer $k$ between $1$ and $100,$ inclusive, the number $x_{k}$ is $k$ less than the sum of the other $99$ numbers. Given that $x_{50}=m/n,$ where $m$ and $n$ are relatively prime positive integers, find $m+n.$
Set $S = \{1, 2, 3, ..., 2005\}$. If among any $n$ pairwise coprime numbers in $S$ there exists at least a prime number, find the minimum of $n$.
suppose this equation: x <sup>2</sup> +y <sup>2</sup> +z <sup>2</sup> =w <sup>2</sup> . show that the solution of this equation ( if w,z have same parity) are in this form:
x=2d(XZ-YW), y=2d(XW+YZ),z=d(X <sup>2</sup> +Y <sup>2</sup> -Z <sup>2</sup> -W <sup>2</sup> ),w=d(X <sup>2</sup> +Y <sup>2</sup> +Z <sup>2</sup> +W <sup>2</sup> )
Kelvin and $15$ other frogs are in a meeting, for a total of $16$ frogs. During the meeting, each pair of distinct frogs becomes friends with probability $\frac{1}{2}$. Kelvin thinks the situation after the meeting is [I]cool[/I] if for each of the $16$ frogs, the number of friends they made during the meeting is a multiple of $4$. Say that the probability of the situation being cool can be expressed in the form $\frac{a}{b}$, where $a$ and $b$ are relatively prime. Find $a$.
Find all pairs $(a,b)$ of integers satisfying: there exists an integer $d \ge 2$ such that $a^n + b^n +1$ is divisible by $d$ for all positive integers $n$.
Let $m$ be an odd positive integer greater than $1$. Let $S_m$ be the set of all non-negative integers less than $m$ which are of the form $x+y$, where $xy-1$ is divisible by $m$. Let $f(m)$ be the number of elements of $S_m$.
[b](a)[/b] Prove that $f(mn)=f(m)f(n)$ if $m$, $n$ are relatively prime odd integers greater than $1$.
[b](b)[/b] Find a closed form for $f(p^k)$, where $k>0$ is an integer and $p$ is an odd prime.
In $\triangle RED, RD =1, \angle DRE = 75^\circ$ and $\angle RED = 45^\circ$. Let $M$ be the midpoint of segment $\overline{RD}$. Point $C$ lies on side $\overline{ED}$ such that $\overline{RC} \perp \overline{EM}$. Extend segment $\overline{DE}$ through $E$ to point $A$ such that $CA = AR$. Then $AE = \tfrac{a-\sqrt{b}}{c},$ where $a$ and $c$ are relatively prime positive integers, and $b$ is a positive integer. Find $a+b+c$.
Find all pairs $(a, b)$ of positive integers for which $a + b = \phi (a) + \phi (b) + gcd (a, b)$.
Here $ \phi (n)$ is the number of numbers $k$ from $\{1, 2,. . . , n\}$ with $gcd (n, k) = 1$.
Jar A contains four liters of a solution that is $45\%$ acid. Jar B contains five liters of a solution that is $48\%$ acid. Jar C contains one liter of a solution that is $k\%$ acid. From jar C, $\tfrac{m}{n}$ liters of the solution is added to jar A, and the remainder of the solution in jar C is added to jar B. At the end, both jar A and jar B contain solutions that are $50\%$ acid. Given that $m$ and $n$ are relatively prime positive integers, find $k+m+n$.
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$)
Pictured below is part of a large circle with radius $30$. There is a chain of three circles with radius $3$, each internally tangent to the large circle and each tangent to its neighbors in the chain. There are two circles with radius $2$ each tangent to two of the radius $3$ circles. The distance between the centers of the two circles with radius $2$ can be written as $\textstyle\frac{a\sqrt b-c}d$, where $a,b,c,$ and $d$ are positive integers, $c$ and $d$ are relatively prime, and $b$ is not divisible by the square of any prime. Find $a+b+c+d$.
[asy]
size(200);
defaultpen(linewidth(0.5));
real r=aCos(79/81);
pair x=dir(270+r)*27,y=dir(270-r)*27;
draw(arc(origin,30,210,330));
draw(circle(x,3)^^circle(y,3)^^circle((0,-27),3));
path arcl=arc(y,5,0,180), arcc=arc((0,-27),5,0,180), arcr=arc(x,5,0,180);
pair centl=intersectionpoint(arcl,arcc), centr=intersectionpoint(arcc,arcr);
draw(circle(centl,2)^^circle(centr,2));
dot(x^^y^^(0,-27)^^centl^^centr,linewidth(2));
[/asy]
The diagram below shows circles radius $1$ and $2$ externally tangent to each other and internally tangent to a circle radius $3$. There are relatively prime positive integers $m$ and $n$ so that a circle radius $\frac{m}{n}$ is internally tangent to the circle radius $3$ and externally tangent to the other two circles as shown. Find $m+n$.
[asy]
import graph; size(5cm);
real labelscalefactor = 0.5;
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps);
pen dotstyle = black;
draw(circle((8,2), 3));
draw(circle((8,1), 2));
draw(circle((8,4), 1));
draw((8,-1)--(8,5));
draw(circle((9.72,3.28), 0.86));
label("$ 2 $",(7.56,1.38),SE*labelscalefactor);
label("$ 1 $",(7.6,4.39),SE*labelscalefactor);
[/asy]
When the number $2^{1000}$ is divided by $13$, the remainder in the division is
$\textbf{(A) }1\qquad\textbf{(B) }2\qquad\textbf{(C) }3\qquad\textbf{(D) }7\qquad \textbf{(E) }11$
Given a fixed positive integer $a\geq 9$. Prove: There exist finitely many positive integers $n$, satisfying:
(1)$\tau (n)=a$
(2)$n|\phi (n)+\sigma (n)$
Note: For positive integer $n$, $\tau (n)$ is the number of positive divisors of $n$, $\phi (n)$ is the number of positive integers $\leq n$ and relatively prime with $n$, $\sigma (n)$ is the sum of positive divisors of $n$.
Find all pairs of positive integers $ a,b$ such that \begin{align*} b^2 + b+ 1 & \equiv 0 \pmod a \\ a^2+a+1 &\equiv 0 \pmod b . \end{align*}
Let $\Gamma_1$ and $\Gamma_2$ be circles in the plane with centers $O_1$ and $O_2$ and radii $13$ and $10$, respectively. Assume $O_1O_2=2$. Fix a circle $\Omega$ with radius $2$, internally tangent to $\Gamma_1$ at $P$ and externally tangent to $\Gamma_2$ at $Q$ . Let $\omega$ be a second variable circle internally tangent to $\Gamma_1$ at $X$ and externally tangent to $\Gamma_2$ at $Y$. Line $PQ$ meets $\Gamma_2$ again at $R$, line $XY$ meets $\Gamma_2$ again at $Z$, and lines $PZ$ and $XR$ meet at $M$.
As $\omega$ varies, the locus of point $M$ encloses a region of area $\tfrac{p}{q} \pi$, where $p$ and $q$ are relatively prime positive integers. Compute $p+q$.
[i]Proposed by Michael Kural[/i]
Let $n \ge 2$ be a positive integer, and let $\sigma(n)$ denote the sum of the positive divisors of $n$. Prove that the $n^{\text{th}}$ smallest positive integer relatively prime to $n$ is at least $\sigma(n)$, and determine for which $n$ equality holds.
[i]Proposed by Ashwin Sah[/i]