Found problems: 5802
Given positive numbers $a_1$ and $b_1$, consider the sequences defined by
\[a_{n+1}=a_n+\frac{1}{b_n},\quad b_{n+1}=b_n+\frac{1}{a_n}\quad (n \ge 1)\]
Prove that $a_{25}+b_{25} \geq 10\sqrt{2}$.
We consider the set of expressions that can be written with real numbers, $\pm$, $+$, $\times$, and parenthesis, such that if each $\pm$ is independently replaced with either $+$ or $-$, we are left with a valid arithmetic expression. For example, this includes:
\[0\pm 1, 1 \pm 2, 1+2\times (1+2\pm 3), (1 \pm 2) \times (3 \pm 4).\]
We define the [i]range[/i] of an expression of this form to be the set of all of the possible values when replacing each $\pm$ with either a $+$ or a $-$. For example,
[list]
[*] $1 \pm 2$ has range $\{-1,3\}$, since $1-2=-1$ and $1+2=3$.
[*] $(1 \pm 1) \times (1 \pm 1)$ has range $\{0,4\}$, since $(1-1)(1-1)=(1-1)(1+1)=(1+1)(1-1)=0$ and $(1+1)(1+1)=4.$
[*] $(1 \pm 2)(3\pm 4)$ has range $\{-7,-3,1,21\}$, since $(1-2)(3+4)=-7$, $(1+2)(3-4)=-3$, $(1-2)(3-4)=1$, and $(1+2)(3+4)=21$.
[/list]
We will prove that every finite nonempty set of real numbers is the range of some expression of this form. Call a nonempty set of real numbers [i]good[/i] if it is the range of some expression of this form.
(a) For each of the following sets, find an expression with a range equal to the given set. You do not need to justify the expression.
[list=i]
[*] $\{1\}$
[*] $\{1,3\}$
[*] $\{-1,0,1\}$
[/list]
(b) Prove that if $S$ and $T$ are good sets, the product set $S \cdot T = \{ xy \mid x \in S, y \in T \}$ (the set of product of elements of $S$ with elements of $T$) is good.
(c) Prove that if a set $S$ not containing $0$ is good, the set $S \cup \{ 0 \}$ (obtained upon adding $0$ to $S$) is good.
(d) Prove that every finite nonempty set of real numbers is good.
Let $ n$ be a positive integer. Consider
\[ S \equal{} \left\{ (x,y,z) \mid x,y,z \in \{ 0, 1, \ldots, n\}, x \plus{} y \plus{} z > 0 \right \}
\]
as a set of $ (n \plus{} 1)^{3} \minus{} 1$ points in the three-dimensional space. Determine the smallest possible number of planes, the union of which contains $ S$ but does not include $ (0,0,0)$.
[i]Author: Gerhard Wöginger, Netherlands [/i]
Show that $n!=a^{n-1}+b^{n-1}+c^{n-1}$ has only finitely many solutions in positive integers.
[i]Proposed by Dorlir Ahmeti, Albania[/i]
The positive integers $a_0, a_1, a_2, \ldots, a_{3030}$ satisfy $$2a_{n + 2} = a_{n + 1} + 4a_n \text{ for } n = 0, 1, 2, \ldots, 3028.$$
Prove that at least one of the numbers $a_0, a_1, a_2, \ldots, a_{3030}$ is divisible by $2^{2020}$.
Find all positive integers $n$ such that $9^{n}-1$ is divisible by $7^n$.
Prove that the ten's digit of any power of 3 is even.
\begin{quote}
Ted quite likes haikus, \\
poems with five-seven-five, \\
but Ted knows few words.
He knows $2n$ words \\
that contain $n$ syllables \\
for every int $n$.
Ted can only write \\
$N$ distinct haikus. Find $N$. \\
Take mod one hundred.
\end{quote}
Ted loves creating haikus (Japanese three-line poems with $5$, $7$, $5$ syllables each), but his vocabulary is rather limited. In particular, for integers $1 \le n \le 7$, he knows $2n$ words with $n$ syllables. Furthermore, words cannot cross between lines, but may be repeated. If Ted can make $N$ distinct haikus, compute the remainder when $N$ is divided by $100$.
[i]Proposed by Lewis Chen[/i]
Define a [b]ring[/b] in the plane to be the set of points at a distance of at least $r$ and at most $R$ from a specific point $O$, where $r<R$ are positive real numbers. Rings are determined by the three parameters $(O, R, r)$. The area of a ring is labeled $S$. A point in the plane for which both its coordinates are integers is called an integer point.
[b]a)[/b] For each positive integer $n$, show that there exists a ring not containing any integer point, for which $S>3n$ and $R<2^{2^n}$.
[b]b)[/b] Show that each ring satisfying $100\cdot R<S^2$ contains an integer point.
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$.
For any odd prime $p$ and any integer $n,$ let $d_p (n) \in \{ 0,1, \dots, p-1 \}$ denote the remainder when $n$ is divided by $p.$ We say that $(a_0, a_1, a_2, \dots)$ is a [i]p-sequence[/i], if $a_0$ is a positive integer coprime to $p,$ and $a_{n+1} =a_n + d_p (a_n)$ for $n \geqslant 0.$
(a) Do there exist infinitely many primes $p$ for which there exist $p$-sequences $(a_0, a_1, a_2, \dots)$ and $(b_0, b_1, b_2, \dots)$ such that $a_n >b_n$ for infinitely many $n,$ and $b_n > a_n$ for infinitely many $n?$
(b) Do there exist infinitely many primes $p$ for which there exist $p$-sequences $(a_0, a_1, a_2, \dots)$ and $(b_0, b_1, b_2, \dots)$ such that $a_0 <b_0,$ but $a_n >b_n$ for all $n \geqslant 1?$
[I]United Kingdom[/i]
Let $A$ be the set of $n$-digit integers whose digits are all from $\{ 1, 2, 3, 4, 5 \}$. $B$ is subset of $A$ such that it contains digit $5$, and there is no digit $3$ in front of digit $5$ (i.e. for $n = 2$, $35$ is not allowed, but $53$ is allowed). How many elements does set $B$ have?
Let $P(x)$ be a polynomial with integer coefficients such that $P(0)=1$, and let $c > 1$ be an integer. Define $x_0=0$ and $x_{i+1} = P(x_i)$ for all integers $i \ge 0$. Show that there are infinitely many positive integers $n$ such that $\gcd (x_n, n+c)=1$.
[i]Proposed by Milan Haiman and Carl Schildkraut[/i]
Janabel has a device that, when given two distinct points $U$ and $V$ in the plane, draws the perpendicular bisector of $UV$. Show that if three lines forming a triangle are drawn, Janabel can mark the orthocenter of the triangle using this device, a pencil, and no other tools.
[i]Proposed by Fedir Yudin.[/i]
Consider the sequence $\{a_n\}$ such that $a_0=4$, $a_1=22$, and $a_n-6a_{n-1}+a_{n-2}=0$ for $n\ge2$. Prove that there exist sequences $\{x_n\}$ and $\{y_n\}$ of positive integers such that
\[
a_n=\frac{y_n^2+7}{x_n-y_n}
\]
for any $n\ge0$.
On each side of an equilateral triangle of side $n \ge 1$ consider $n - 1$ points that divide the sides into $n$ equal segments. Through these points draw parallel lines to the sides of the triangles, obtaining a net of equilateral triangles of side length $1$. On each of the vertices of the small triangles put a coin head up. A move consists in flipping over three mutually adjacent coins. Find all values of $n$ for which it is possible to turn all coins tail up after a finite number of moves.
Colombia 1997
The $n$ players of a hockey team gather to select their team captain. Initially, they stand in a circle, and each person votes for the person on their left.
The players will update their votes via a series of rounds. In one round, each player $a$ updates their vote, one at a time, according to the following procedure: At the time of the update, if $a$ is voting for $b,$ and $b$ is voting for $c,$ then $a$ updates their vote to $c.$ (Note that $a, b,$ and $c$ need not be distinct; if $b=c$ then $a$'s vote does not change for this update.) Every player updates their vote exactly once in each round, in an order determined by the players (possibly different across different rounds).
They repeat this updating procedure for $n$ rounds. Prove that at this time, all $n$ players will unanimously vote for the same person.
Palindrome is a sequence of digits which doesn't change if we reverse the order of its digits. Prove that a sequence $(x_n)^{\infty}_{n=0}$ defined as
$x_n=2013+317n$
contains infinitely many numbers with their decimal expansions being palindromes.
Alphonse and Beryl play a game involving $n$ safes. Each safe can be opened by a unique key and each key opens a unique safe. Beryl randomly shuffles the $n$ keys, and after placing one key inside each safe, she locks all of the safes with her master key. Alphonse then selects $m$ of the safes (where $m < n$), and Beryl uses her master key to open just the safes that Alphonse selected. Alphonse collects all of the keys inside these $m$ safes and tries to use these keys to open up the other $n - m$ safes. If he can open a safe with one of the $m$ keys, he can then use the key in that safe to try to open any of the remaining safes, repeating the process until Alphonse successfully opens all of the safes, or cannot open any more. Let $P_m(n)$ be the probability that Alphonse can eventually open all $n$ safes starting from his initial selection of $m$ keys.
(a) Show that $P_2(3) = \frac23$.
(b) Prove that $P_1(n) = \frac1n$.
(c) For all integers $n \geq 2$, prove that $$P_2(n) = \frac2n \cdot P_1(n-1) + \frac{n-2}{n} \cdot P_2(n-1).$$
(d) Determine a formula for $P_2 (n)$.
Which of the following is equivalent to $$(2+3)(2^2+3^2)(2^4+3^4)(2^8+3^8)(2^{16}+3^{16})(2^{32}+3^{32})(2^{64}+3^{64})?$$
$\textbf{(A) }3^{127}+2^{127} \qquad \textbf{(B) }3^{127}+2^{127}+2\cdot 3^{63}+3\cdot 2^{63} \qquad \textbf{(C) }3^{128}-2^{128} \qquad \textbf{(D) }3^{128}+2^{128} \qquad \textbf{(E) }5^{127}$
For odd numbers $a_1 , ..., a_k$ and even numbers $b_1 , ..., b_k$ , we know that $\sum_ {j = 1}^k a_j^n = \sum_{j = 1}^k b_j^n$ is satisfied for n = 1,2, ..., N. Prove that $k\geq 2^N$ and that for $k = 2^N$ there exists a solution $(a_1,...,b_1,...)$ with the above properties.
For a positive integer $m$ denote by $S(m)$ and $P(m)$ the sum and product, respectively, of the digits of $m$. Show that for each positive integer $n$, there exist positive integers $a_1, a_2, \ldots, a_n$ satisfying the following conditions: \[ S(a_1) < S(a_2) < \cdots < S(a_n) \text{ and } S(a_i) = P(a_{i+1}) \quad (i=1,2,\ldots,n). \] (We let $a_{n+1} = a_1$.)
[i]Problem Committee of the Japan Mathematical Olympiad Foundation[/i]
For a positive integer $n$, denote by $\tau (n)$ the number of its positive divisors. For a positive integer $n$, if $\tau (m) < \tau (n)$ for all $m < n$, we call $n$ a good number. Prove that for any positive integer $k$, there are only finitely many good numbers not divisible by $k$.
Let $n$ be a positive integer. Initially a few positive integers are written on the blackboard. On one move Igor chooses two numbers $a, b$ of the same parity on the blackboard and writes $\frac{a+b} {2}$. After a few moves the numbers on the blackboard were exactly $1, 2, \ldots, n$. Find the smallest possible number of positive integers that were initially written on the blackboard.
For what polynomials $P(n)$ with integer coefficients can a positive integer be assigned to every lattice point in $\mathbb{R}^3$ so that for every integer $n \ge 1$, the sum of the $n^3$ integers assigned to any $n \times n \times n$ grid of lattice points is divisible by $P(n)$?
[i]Proposed by Andre Arslan[/i]