Found problems: 5923
Suppose $W(k,2)$ is the smallest number such that if $n\ge W(k,2)$, for each coloring of the set $\{1,2,...,n\}$ with two colors there exists a monochromatic arithmetic progression of length $k$. Prove that
$W(k,2)=\Omega (2^{\frac{k}{2}})$.
Let $ A_0 \equal{} (a_1,\dots,a_n)$ be a finite sequence of real numbers. For each $ k\geq 0$, from the sequence $ A_k \equal{} (x_1,\dots,x_k)$ we construct a new sequence $ A_{k \plus{} 1}$ in the following way.
1. We choose a partition $ \{1,\dots,n\} \equal{} I\cup J$, where $ I$ and $ J$ are two disjoint sets, such that the expression
\[ \left|\sum_{i\in I}x_i \minus{} \sum_{j\in J}x_j\right|
\]
attains the smallest value. (We allow $ I$ or $ J$ to be empty; in this case the corresponding sum is 0.) If there are several such partitions, one is chosen arbitrarily.
2. We set $ A_{k \plus{} 1} \equal{} (y_1,\dots,y_n)$ where $ y_i \equal{} x_i \plus{} 1$ if $ i\in I$, and $ y_i \equal{} x_i \minus{} 1$ if $ i\in J$.
Prove that for some $ k$, the sequence $ A_k$ contains an element $ x$ such that $ |x|\geq\frac n2$.
[i]Author: Omid Hatami, Iran[/i]
The given sequences are $ (x_1, x_2, \ldots, x_n) $, $ (y_1, y_2, \ldots, y_n) $ with positive terms. Prove that there exists a permutation $ p $ of the set $ \{1, 2, \ldots, n\} $ such that for every real $ t $ the sequence
$$ (x_{p(1)}+ty_{p(1)}, x_{p(2)}+ty_{p(2)}, \ldots, x_{p(n)}+ty_{p(n) })$$ has the following property: there is a number $ k $ such that $ 1 \leq k \leq n $ and all non-zero terms of the sequence with indices less than $ k $ are of the same sign and all non-zero terms of the sequence with indices not less than $ k $ are the same sign.
The general term of a sequence of numbers is defined as $a_n =\frac{1}{n^2 - n}$, for every integer $n \ge 3$.
That is, $a_3 =\frac16$, $a_4 =\frac{1}{12}$, $a_5 =\frac{1}{20}$, and so on.
Find a general expression for the sum $S_n$, which is the sum of all terms from $a_3$ until $a_n$.
In an increasing sequence of four positive integers, the first three terms form an arithmetic progression, the last three terms form a geometric progression, and the first and fourth terms differ by 30. Find the sum of the four terms.
A $\textit{divisibility chain}$ is a sequence of positive integers $(a_1, a_2, \ldots, a_n)$ such that $a_k$ divides $a_{k+1}$ for all $1 \le k < n $. Compute the number of divisibility chains of the form $(a, b, a^2, c, a^3, 360^9)$.
[i]Proposed by Michael Tang[/i]
Suppose we have some proteins that each protein is a sequence of 7 "AMINO-ACIDS" $A,\ B,\ C,\ H,\ F,\ N$. For example $AFHNNNHAFFC$ is a protein. There are some steps that in each step an amino-acid will change to another one. For example with the step $NA\rightarrow N$ the protein $BANANA$ will cahnge to $BANNA$("in Persian means workman"). We have a set of allowed steps that each protein can change with these steps. For example with the
set of steps:
$\\ 1)\ AA\longrightarrow A\\ 2)\ AB\longrightarrow BA\\ 3)\ A\longrightarrow \mbox{null}$
Protein $ABBAABA$ will change like this:
$\\ ABB\underline{AA}BA\\ \underline{AB}BABA\\ B\underline{AB}ABA\\ BB\underline{AA}BA\\ BB\underline{AB}A\\ BBB\underline{AA}\\ BBB\underline{A}\\ BBB$
You see after finite steps this protein will finish it steps.
Set of allowed steps that for them there exist a protein that may have infinitely many steps is dangerous. Which of the following allowed sets are dangerous?
a) $NO\longrightarrow OONN$
b) $\left\{\begin{array}{c}HHCC\longrightarrow HCCH\\ CC\longrightarrow CH\end{array}\right.$
c) Design a set of allowed steps that change $\underbrace{AA\dots A}_{n}\longrightarrow\underbrace{BB\dots B}_{2^{n}}$
d) Design a set of allowed steps that change $\underbrace{A\dots A}_{n}\underbrace{B\dots B}_{m}\longrightarrow\underbrace{CC\dots C}_{mn}$
You see from $c$ and $d$ that we acn calculate the functions $F(n)=2^{n}$ and $G(M,N)=mn$ with these steps. Find some other calculatable functions with these steps. (It has some extra mark.)
Let $\{a_n\}_{n\geq 1}$ be a sequence with $a_1=1$, $a_2=4$ and for all $n>1$, \[ a_{n} = \sqrt{ a_{n-1}a_{n+1} + 1 } . \]
a) Prove that all the terms of the sequence are positive integers.
b) Prove that $2a_na_{n+1}+1$ is a perfect square for all positive integers $n$.
[i]Valentin Vornicu[/i]
Flights are arranged between 13 countries. For $ k\ge 2$, the sequence $ A_{1} ,A_{2} ,\ldots A_{k}$ is said to a cycle if there exist a flight from $ A_{1}$ to $ A_{2}$, from $ A_{2}$ to $ A_{3}$, $ \ldots$, from $ A_{k \minus{} 1}$ to $ A_{k}$, and from $ A_{k}$ to $ A_{1}$. What is the smallest possible number of flights such that how the flights are arranged, there exist a cycle?
$\textbf{(A)}\ 14 \qquad\textbf{(B)}\ 53 \qquad\textbf{(C)}\ 66 \qquad\textbf{(D)}\ 79 \qquad\textbf{(E)}\ 156$
Let $(a_n), n = 0, 1, . . .,$ be a sequence of real numbers such that $a_0 = 0$ and
\[a^3_{n+1} = \frac{1}{2} a^2_n -1, n= 0, 1,\cdots\]
Prove that there exists a positive number $q, q < 1$, such that for all $n = 1, 2, \ldots ,$
\[|a_{n+1} - a_n| \leq q|a_n - a_{n-1}|,\]
and give one such $q$ explicitly.
Let $ a_1,a_2,\dots$ be sequence of real numbers such that $ a_1\equal{}1$, $ a_2\equal{}\dfrac{4}{3}$, and \[ a_{n\plus{}1}\equal{}\sqrt{1\plus{}a_na_{n\minus{}1}}, \quad \forall n \ge 2.\] Prove that for all $ n \ge 2$, \[ a_n^2>a_{n\minus{}1}^2\plus{}\dfrac{1}{2}\] and \[ 1\plus{}\dfrac{1}{a_1}\plus{}\dfrac{1}{a_2}\plus{}\dots\plus{}\dfrac{1}{a_n}>2a_n.\]
[i]Fajar Yuliawan, Bandung[/i]
Let $n$ be a positive integer. Find the number of sequences $a_0,a_1,a_2,\dots,a_{2n}$ of integers in the range $[0,n]$ such that for all integers $0\leq k\leq n$ and all nonnegative integers $m$, there exists an integer $k\leq i\leq 2k$ such that $\lfloor k/2^m\rfloor=a_i.$
[i]Andrew Carratu[/i]
Let $n$ be a positive integer. A [i]Japanese triangle[/i] consists of $1 + 2 + \dots + n$ circles arranged in an equilateral triangular shape such that for each $i = 1$, $2$, $\dots$, $n$, the $i^{th}$ row contains exactly $i$ circles, exactly one of which is coloured red. A [i]ninja path[/i] in a Japanese triangle is a sequence of $n$ circles obtained by starting in the top row, then repeatedly going from a circle to one of the two circles immediately below it and finishing in the bottom row. Here is an example of a Japanese triangle with $n = 6$, along with a ninja path in that triangle containing two red circles.
[asy]
// credit to vEnhance for the diagram (which was better than my original asy):
size(4cm);
pair X = dir(240); pair Y = dir(0);
path c = scale(0.5)*unitcircle;
int[] t = {0,0,2,2,3,0};
for (int i=0; i<=5; ++i) {
for (int j=0; j<=i; ++j) {
filldraw(shift(i*X+j*Y)*c, (t[i]==j) ? lightred : white);
draw(shift(i*X+j*Y)*c);
}
}
draw((0,0)--(X+Y)--(2*X+Y)--(3*X+2*Y)--(4*X+2*Y)--(5*X+2*Y),linewidth(1.5));
path q = (3,-3sqrt(3))--(-3,-3sqrt(3));
draw(q,Arrows(TeXHead, 1));
label("$n = 6$", q, S);
label("$n = 6$", q, S);
[/asy]
In terms of $n$, find the greatest $k$ such that in each Japanese triangle there is a ninja path containing at least $k$ red circles.
Let $n$ be a positive integer. We start with $n$ piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. Find (in terms of $n$) the smallest number of nonempty piles that one can obtain by performing a finite sequence of moves of this form.
Show that among the square roots of the first $ 2015 $ natural numbers, we cannot choose an arithmetic sequence composed of $ 45 $ elements.
A doubly-indexed sequence $a_{m,n}$, for $m$ and $n$ nonnegative integers, is defined as follows:
[list]
[*]$a_{m,0}=0$ for all $m>0$ and $a_{0,0}=1$.
[*]$a_{m,1}=0$ for all $m>1$, $a_{1,1}=1$, and $a_{0,1}=0$.
[*]$a_{0,n}=a_{0,n-1}+a_{0,n-2}$ for all $n\geq 2$.
[*]$a_{m,n}=a_{m,n-1}+a_{m,n-2}+a_{m-1,n-1}-a_{m-1,n-2}$ for all $m>0$, $n\geq 2$.
[/list]
Then there exists a unique value of $x$ so $\sum_{m=0}^{\infty}\sum_{n=0}^{\infty}\frac{a_{m,n}x^m}{3^{n-m}}=1$. Find $\lfloor 1000x^2 \rfloor$.
Sequence $\{ a_n \}$ satisfies: $a_1=3$, $a_2=7$, $a_n^2+5=a_{n-1}a_{n+1}$, $n \geq 2$. If $a_n+(-1)^n$ is prime, prove that there exists a nonnegative integer $m$ such that $n=3^m$.
Define a sequence of positive rational numbers $x_0, x_1, x_2, x_3, \cdots$ by $x_0 = 2, x_1 = 3,$ and
for all $n \geq 2,$
$$x_n = \frac{x_{n-1}^2 + 5}{x_{n-2}}$$
(a) Prove that $x_n$ is an integer for all $n \geq 0.$
(b) Prove that if $x_n$ is prime, then either $n = 0$ or $n = 2^k$ for some integer $k \geq 0.$
Let $a_1$, $a_2$, ... be a sequence of integers defined recursively by $a_1=2013$ and for $n \ge 1$, $a_{n+1}$ is the sum of the $2013$-th powers of the digits of $a_n$. Do there exist distinct positive integers $i$, $j$ such that $a_i=a_j$?
Given sequence $ \{ c_n \}$ satisfying the conditions that $ c_0\equal{}1$, $ c_1\equal{}0$, $ c_2\equal{}2005$, and $ c_{n\plus{}2}\equal{}\minus{}3c_n \minus{} 4c_{n\minus{}1} \plus{}2008$, ($ n\equal{}1,2,3, \cdots$). Let $ \{ a_n \}$ be another sequence such that $ a_n\equal{}5(c_{n\plus{}1} \minus{} c_n) \cdot (502 \minus{} c_{n\minus{}1} \minus{} c_{n\minus{}2}) \plus{} 4^n \times 2004 \times 501$, ($ n\equal{}2,3, \cdots$).
Is $ a_n$ a perfect square for every $ n > 2$?
Kara rolls a six-sided die six times, and notices that the results satisfy the following conditions:
[list]
[*] She rolled a $6$ exactly three times;
[*] The product of her first three rolls is the same as the product of her last three rolls.
[/list]
How many distinct sequences of six rolls could Kara have rolled?
[i]Proposed by Andrew Wu[/i]
For all $n\ge2$ positive integer, let $f(n)$ denote the product of all distinct prime divisors of $n$. For example, $f(5)=5$, $f(8)=2$, and $f(12)=6$. Given a sequence ${a_n}$, where $a_1\ge2$, defined as follows:
$$a_{n+1}=a_n+f(a_n)$$
Show that for any prime $p$, there exists a term $a_k$ in the sequence such that $p|a_k$.
A square $ABCD$ is divided into $(n - 1)^2$ congruent squares, with sides parallel to the sides of the given square. Consider the grid of all $n^2$ corners obtained in this manner. Determine all integers $n$ for which it is possible to construct a non-degenerate parabola with its axis parallel to one side of the square and that passes through exactly $n$ points of the grid.
Find all homogeneous linear recursive sequences such that there is a $ T$ such that $ a_n\equal{}a_{n\plus{}T}$ for each $ n$.
Let $a_1, a_2, \dots$ be an arithmetic sequence and $b_1, b_2, \dots$ be a geometric sequence. Suppose that $a_1 b_1 = 20$, $a_2 b_2 = 19$, and $a_3 b_3 = 14$. Find the greatest possible value of $a_4 b_4$.