Found problems: 5923
Define the sequence $a_0,a_1,a_2,\hdots$ by $a_n=2^n+2^{\lfloor n/2\rfloor}$. Prove that there are infinitely many terms of the sequence which can be expressed as a sum of (two or more) distinct terms of the sequence, as well as infinitely many of those which cannot be expressed in such a way.
Let $\left\{ a_n \right\}$ and $\left\{ b_n \right\}$ be sequences defined recursively by $a_0 =2$; $b_0 = 2$, and $a_{n+1} = a_n \sqrt{1+a_n^2+b_n^2}-b_n$; $b_{n+1} = b_n\sqrt{1+a_n^2+b_n^2} + a_n$. Find the ternary (base 3) representation of $a_4$ and $b_4$.
Positive integers $ a$, $ b$, and $ 2009$, with $ a<b<2009$, form a geometric sequence with an integer ratio. What is $ a$?
$ \textbf{(A)}\ 7 \qquad
\textbf{(B)}\ 41 \qquad
\textbf{(C)}\ 49 \qquad
\textbf{(D)}\ 289 \qquad
\textbf{(E)}\ 2009$
Let $p \equiv 2 \pmod 3$ be a prime, $k$ a positive integer and $P(x) = 3x^{\frac{2p-1}{3}}+3x^{\frac{p+1}{3}}+x+1$. For any integer $n$, let $R(n)$ denote the remainder when $n$ is divided by $p$ and let $S = \{0,1,\cdots,p-1\}$. At each step, you can either (a) replaced every element $i$ of $S$ with $R(P(i))$ or (b) replaced every element $i$ of $S$ with $R(i^k)$. Determine all $k$ such that there exists a finite sequence of steps that reduces $S$ to $\{0\}$.
[i]Proposed by fattypiggy123[/i]
Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be the function as
\[ f(x) = \begin{cases} \frac{1}{x-1}& (x > 1)\\ 1& (x=1)\\ \frac{x}{1-x} & (x<1) \end{cases} \]
Let $x_1$ be a positive irrational number which is a zero of a quadratic polynomial with integer coefficients. For every positive integer $n$, let $x_{n+1} = f(x_n)$. Prove that there exists different positive integers $k$ and $\ell$ such that $x_k = x_\ell$.
Suppose that a sequence $a_1,a_2,\ldots$ of positive real numbers satisfies \[a_{k+1}\geq\frac{ka_k}{a_k^2+(k-1)}\] for every positive integer $k$. Prove that $a_1+a_2+\ldots+a_n\geq n$ for every $n\geq2$.
What is the largest possible length of an arithmetic progression of positive integers $ a_{1}, a_{2},\cdots , a_{n}$ with difference $ 2$, such that $ {a_{k}}^{2}\plus{}1$ is prime for $ k \equal{} 1, 2, . . . , n$?
Theseus starts at the point $(0, 0)$ in the plane. If Theseus is standing at the point $(x, y)$ in the plane, he can step one unit to the north to point $(x, y+1)$, one unit to the west to point $(x-1, y)$, one unit to the south to point $(x, y-1)$, or one unit to the east to point $(x+1, y)$. After a sequence of more than two such moves, starting with a step one unit to the south (to point $(0, -1)$), Theseus finds himself back at the point $(0, 0)$. He never visited any point other than $(0, 0)$ more than once, and never visited the point $(0, 0)$ except at the start and end of this sequence of moves.
Let $X$ be the number of times that Theseus took a step one unit to the north, and then a step one unit to the west immediately afterward. Let $Y$ be the number of times that Theseus took a step one unit to the west, and then a step one unit to the north immediately afterward. Prove that $|X - Y| = 1$.
[i]Mitchell Lee[/i]
A social network has $2019$ users, some pairs of whom are friends. Whenever user $A$ is friends with user $B$, user $B$ is also friends with user $A$. Events of the following kind may happen repeatedly, one at a time:
[list]
[*] Three users $A$, $B$, and $C$ such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends, change their friendship statuses such that $B$ and $C$ are now friends, but $A$ is no longer friends with $B$, and no longer friends with $C$. All other friendship statuses are unchanged.
[/list]
Initially, $1010$ users have $1009$ friends each, and $1009$ users have $1010$ friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.
[i]Proposed by Adrian Beker, Croatia[/i]
Antonio plays a game where he continually flips a fair coin to see the sequence of heads ($H$) and tails ($T$) that he flips. Antonio wins the game if he sees on four consecutive flips the sequence $TTHT$ before he sees the sequence $HTTH$. The probability that Antonio wins the game is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$.
Let $ a_1$, $ a_2$, $ \ldots$, $ a_n$ be distinct positive integers, $ n\ge 3$. Prove that there exist distinct indices $ i$ and $ j$ such that $ a_i \plus{} a_j$ does not divide any of the numbers $ 3a_1$, $ 3a_2$, $ \ldots$, $ 3a_n$.
[i]Proposed by Mohsen Jamaali, Iran[/i]
In $\triangle ABC$, $A,B,C$ are arithmetic sequence, and $c-a$ is equal to height on side $BC$, then $\sin\frac{C-A}{2}=$________.
A sequence of three real numbers forms an arithmetic progression with a first term of $ 9$. If $ 2$ is added to the second term and $ 20$ is added to the third term, the three resulting numbers form a geometric progression. What is the smallest possible value for the third term in the geometric progression?
$ \textbf{(A)}\ 1 \qquad \textbf{(B)}\ 4 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 49 \qquad \textbf{(E)}\ 81$
Let $u_n$ be the $n^\text{th}$ term of the sequence \[1,\,\,\,\,\,\,2,\,\,\,\,\,\,5,\,\,\,\,\,\,6,\,\,\,\,\,\,9,\,\,\,\,\,\,12,\,\,\,\,\,\,13,\,\,\,\,\,\,16,\,\,\,\,\,\,19,\,\,\,\,\,\,22,\,\,\,\,\,\,23,\ldots,\] where the first term is the smallest positive integer that is $1$ more than a multiple of $3$, the next two terms are the next two smallest positive integers that are each two more than a multiple of $3$, the next three terms are the next three smallest positive integers that are each three more than a multiple of $3$, the next four terms are the next four smallest positive integers that are each four more than a multiple of $3$, and so on: \[\underbrace{1}_{1\text{ term}},\,\,\,\,\,\,\underbrace{2,\,\,\,\,\,\,5}_{2\text{ terms}} ,\,\,\,\,\,\,\underbrace{6,\,\,\,\,\,\,9,\,\,\,\,\,\,12}_{3\text{ terms}},\,\,\,\,\,\,\underbrace{13,\,\,\,\,\,\,16,\,\,\,\,\,\,19,\,\,\,\,\,\,22}_{4\text{ terms}},\,\,\,\,\,\,\underbrace{23,\ldots}_{5\text{ terms}},\,\,\,\,\,\,\ldots.\] Determine $u_{2008}$.
A $\pm 1$-[i]sequence[/i] is a sequence of $2022$ numbers $a_1, \ldots, a_{2022},$ each equal to either $+1$ or $-1$. Determine the largest $C$ so that, for any $\pm 1$-sequence, there exists an integer $k$ and indices $1 \le t_1 < \ldots < t_k \le 2022$ so that $t_{i+1} - t_i \le 2$ for all $i$, and $$\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge C.$$
Given are two coprime positive integers $a, b$ with $b$ odd and $a>2$. The sequence $(x_n)$ is defined by $x_0=2, x_1=a$ and $x_{n+2}=ax_{n+1}+bx_n$ for $n \geq 1$. Prove that:
$a)$ If $a$ is even then there do not exist positive integers $m, n, p$ such that $\frac{x_m} {x_nx_p}$ is a positive integer.
$b)$ If $a$ is odd then there do not exist positive integers $m, n, p$ such that $mnp$ is even and $\frac{x_m} {x_nx_p}$ is a perfect square.
There are $36$ cards in a deck arranged in the sequence spades, clubs, hearts, diamonds, spades, clubs, hearts, diamonds, etc. Somebody took part of this deck off the top, turned it upside down, and cut this part into the remaining part of the deck (i.e. inserted it between two consecutive cards). Then four cards were taken off the top, then another four, etc. Prove that in any of these sets of four cards, all the cards are of different suits.
(A Merkov, Moscow)
Consider the arithmetic progression $a, a+d, a+2d,\ldots$ where $a$ and $d$ are positive integers. For any positive integer $k$, prove that the progression has either no $k$-th powers or infinitely many.
For $n = 1,2,3,...$. $a_n$ is defined by:
$$a_n =\frac{1 \cdot 4 \cdot 7 \cdot ... (3n-2)}{2 \cdot 5 \cdot 8 \cdot ... (3n-1)}$$
Prove that for every $n$ holds that
$$\frac{1}{\sqrt{3n+1}}\le a_n \le \frac{1}{\sqrt[3]{3n+1}}$$
Let $1,7,19,\ldots$ be the sequence of numbers such that for all integers $n\ge 1$, the average of the first $n$ terms is equal to the $n$th perfect square. Compute the last three digits of the $2021$st term in the sequence.
[i]Proposed by Nathan Xiong[/i]
Let $1,2,3,4,5,6,7,8,9,11,12,\cdots$ be the sequence of all positive integers which do not contain the digit zero. Write $\{a_n\}$ for this sequence. By comparing with a geometric series, show that $\sum_{k=1}^n \frac{1}{a_k} < 90$.
The angles $\alpha, \beta, \gamma$ of a triangle are in arithmetic progression. If $\sin 20\alpha$, $\sin 20\beta$, and $\sin 20\gamma$ are in arithmetic progression, how many different values can $\alpha$ take?
$
\textbf{(A)}\ 1
\qquad\textbf{(B)}\ 2
\qquad\textbf{(C)}\ 3
\qquad\textbf{(D)}\ 4
\qquad\textbf{(E)}\ \text{None of the above}
$
Abimbola plays a game with a coin. He tosses the coin a number of times, and records whether each toss was a "heads" or "tails". He stops tossing the coin as soon as he tosses an odd number of heads in a row, followed by a tails. (Note that he stops if the number of heads since the previous time that he tosses tails is odd, and he then tosses another tails. If he has not tossed tails previously, then he stops if the total number of heads is odd, and he then tosses tails.) How many different sequences of coin tosses are there such that he stops after the $n^\text{th}$ coin toss?
A road company is trying to build a system of highways in a country with $21$ cities. Each highway runs between two cities. A trip is a sequence of distinct cities $C_1,\dots, C_n$, for which there is a highway between $C_i$ and $C_{i+1}$. The company wants to fulfill the following two constraints:
(1) for any ordered pair of distinct cities $(C_i, C_j)$, there is exactly one trip starting at $C_i$ and ending at $C_j$.
(2) if $N$ is the number of trips including exactly 5 cities, then $N$ is maximized.
What is this maximum value of $N$?
Xavier takes a permutation of the numbers $1$ through $2011$ at random, where each permutation has an equal probability of being selected. He then cuts the permutation into increasing contiguous subsequences, such that each subsequence is as long as possible. Compute the expected number of such subsequences.
[i]Author: Alex Zhu[/i]
[hide="Clarification"]An increasing contiguous subsequence is an increasing subsequence all of whose terms are adjacent in the original sequence. For example, 1,3,4,5,2 has two maximal increasing contiguous subsequences: (1,3,4,5) and (2). [/hide]