Found problems: 5802
The sequence $(Q_{n}(x))$ of polynomials is defined by
$$Q_{1}(x)=1+x ,\; Q_{2}(x)=1+2x,$$
and for $m \geq 1 $ by
$$Q_{2m+1}(x)= Q_{2m}(x) +(m+1)x Q_{2m-1}(x),$$
$$Q_{2m+2}(x)= Q_{2m+1}(x) +(m+1)x Q_{2m}(x).$$
Let $x_n$ be the largest real root of $Q_{n}(x).$ Prove that $(x_n )$ is an increasing sequence and that $\lim_{n\to \infty} x_n =0.$
$n$ red and $n$ blue points on a plane are given so that no three of the $2n$ points are collinear. Prove that it is always possible to split up the points into $n$ pairs, with one red and one blue point in each pair, so that no two of the $n$ line segments which connect the two members of a pair intersect.
Let $ABCD$ be a square with side $20$ and $T_1, T_2, ..., T_{2000}$ are points in $ABCD$ such that no $3$ points in the set $S = \{A, B, C, D, T_1, T_2, ..., T_{2000}\}$ are collinear. Prove that there exists a triangle with vertices in $S$, such that the area is less than $1/10$.
The sequence $\{a_n\}$ is defined by $a_0 = 1, a_1 = 2,$ and for $n \geq 2,$
$$a_n = a_{n-1}^2 + (a_0a_1 \dots a_{n-2})^2.$$
Let $k$ be a positive integer, and let $p$ be a prime factor of $a_k.$ Show that $p > 4(k-1).$
Let $n$ be a positive integer, and let $S_n$ be the set of all permutations of $1,2,...,n$. let $k$ be a non-negative integer, let $a_{n,k}$ be the number of even permutations $\sigma$ in $S_n$ such that $\sum_{i=1}^{n}|\sigma(i)-i|=2k$ and $b_{n,k}$ be the number of odd permutations $\sigma$ in $S_n$ such that $\sum_{i=1}^{n}|\sigma(i)-i|=2k$. Evaluate $a_{n,k}-b_{n,k}$.
[i]* * *[/i]
Let $n > 1$ be an integer and let $f(x) = x^n + 5 \cdot x^{n-1} + 3.$ Prove that there do not exist polynomials $g(x),h(x),$ each having integer coefficients and degree at least one, such that $f(x) = g(x) \cdot h(x).$
We have $n$ points in the plane, no three on a line.
We call $k$ of them good if they form a convex polygon and there is no other point in the convex polygon.
Suppose that for a fixed $k$ the number of $k$ good points is $c_k$.
Show that the following sum is independent of the structure of points and only depends on $n$ :
\[ \sum_{i=3}^n (-1)^i c_i \]
Let \(m\) be a positive integer. Find, in terms of \(m\), all polynomials \(P(x)\) with integer coefficients such that for every integer \(n\), there exists an integer \(k\) such that \(P(k)=n^m\).
[i]Proposed by Raymond Feng[/i]
Let $S$ be a set, such that for every positive integer $n$, we have $|S\cap T|=1$, where $T=\{n,2n,3n\}$. Prove that if $2\in S$, then $13824\notin S$.
For any positive integer $m \geq 2$, let $p(m)$ be the smallest prime dividing $m$ and $P(m)$ be the largest prime dividing $m$. Let $C$ be a positive integer. Define sequences $\{a_n\}$ and $\{b_n\}$ by $a_0 = b_0 = C$ and, for each positive integer $k$ such that $a_{k-1}\geq 2$,
$$a_k=a_{k-1}-\frac{a_{k-1}}{p(a_{k-1})};$$
and, for each positive integer $k$ such that $b_{k-1}\geq 2$,
$$b_k=b_{k-1}-\frac{b_{k-1}}{P(b_{k-1})}$$
It is easy to see that both $\{a_n\}$ and $\{b_n\}$ are finite sequences which terminate when they reach the number $1$.
Prove that the numbers of terms in the two sequences are always equal.
Let $n > 1$ be a given integer. An $n \times n \times n$ cube is composed of $n^3$ unit cubes. Each unit cube is painted with one colour. For each $n \times n \times 1$ box consisting of $n^2$ unit cubes (in any of the three possible orientations), we consider the set of colours present in that box (each colour is listed only once). This way, we get $3n$ sets of colours, split into three groups according to the orientation.
It happens that for every set in any group, the same set appears in both of the other groups. Determine, in terms of $n$, the maximal possible number of colours that are present.
A Retired Linguist (R.L.) writes in the first move a word consisting of $n$ letters, which are all different. In each move, he determines the maximum $i$, such that the word obtained by reversing the first $i$ letters of the last word hasn't been written before, and writes this new word. Prove that R.L. can make $n!$ moves.
The $ 5\times 5$ grid shown contains a collection of squares with sizes from $ 1\times 1$ to $ 5\times 5$. How many of these squares contain the black center square?
[asy]unitsize(6mm);
defaultpen(linewidth(.8pt));
for(int i=0; i<=5; ++i)
{
draw((0,i)--(5,i));
draw((i,0)--(i,5));
}
fill((2,2)--(2,3)--(3,3)--(3,2)--cycle);[/asy]$ \textbf{(A)}\ 12\qquad
\textbf{(B)}\ 15\qquad
\textbf{(C)}\ 17\qquad
\textbf{(D)}\ 19\qquad
\textbf{(E)}\ 20$
Yatta and Yogi play a game in which they begin with a pile of $n$ stones. The players take turns removing $1$, $2$, $3$, $5$, $6$, $7$, or $8$ stones from the pile. That is, when it is a player's turn to remove stones, that player may remove from $1$ to $8$ stones, but [i]cannot[/i] remove exactly $4$ stones. The player who removes the last stone [i]loses[/i]. Yogi goes first and finds that he has a winning position, meaning that so long as he plays perfectly, Yatta cannot defeat him. For how many positive integers $n$ from $100$ to $2008$ inclusive is this the case?
Let $F_r=x^r\sin{rA}+y^r\sin{rB}+z^r\sin{rC}$, where $x,y,z,A,B,C$ are real and $A+B+C$ is an integral multiple of $\pi$. Prove that if $F_1=F_2=0$, then $F_r=0$ for all positive integral $r$.
Let the sequence $\{a_n\}_{n \geq 1}$ be defined by
\[
a_1 = 1, \quad a_{n+1} = a_n + \frac{1}{\sqrt[2024]{a_n}} \quad \text{for } n \geq 1, \, n \in \mathbb{N}
\]
Prove that
\[
a_n^{2025} >n^{2024}
\]
for all positive integers $n \geq 2$.
$\textbf{Proposed by Prajit Adhikari, Nepal.}$
Let $n$ be a positive integer. Prove that there exists a poisitve integer $m$ such that
$$7^n \mid 3^m+5^m-1$$
Let $N=6+66+666+....+666..66$, where there are hundred $6's$ in the last term in the sum. How many times does the digit $7$ occur in the number $N$
Let $P$ be a polynomial with integer coefficients such that $P(0)=0$ and
\[\gcd(P(0), P(1), P(2), \ldots ) = 1.\]
Show there are infinitely many $n$ such that
\[\gcd(P(n)- P(0), P(n+1)-P(1), P(n+2)-P(2), \ldots) = n.\]
Let $n > 1$ be an integer. In a circular arrangement of $n$ lamps $L_0, \ldots, L_{n-1},$ each of of which can either ON or OFF, we start with the situation where all lamps are ON, and then carry out a sequence of steps, $Step_0, Step_1, \ldots .$ If $L_{j-1}$ ($j$ is taken mod $n$) is ON then $Step_j$ changes the state of $L_j$ (it goes from ON to OFF or from OFF to ON) but does not change the state of any of the other lamps. If $L_{j-1}$ is OFF then $Step_j$ does not change anything at all. Show that:
(i) There is a positive integer $M(n)$ such that after $M(n)$ steps all lamps are ON again,
(ii) If $n$ has the form $2^k$ then all the lamps are ON after $n^2-1$ steps,
(iii) If $n$ has the form $2^k + 1$ then all lamps are ON after $n^2 - n + 1$ steps.
[b]p1.[/b] Sujay sees a shooting star go across the night sky, and took a picture of it. The shooting star consists of a star body, which is bounded by four quarter-circle arcs, and a triangular tail. Suppose $AB = 2$, $AC = 4$. Let the area of the shooting star be $X$. If $6X = a-b\pi$ for positive integers $a, b$, find $a + b$.
[img]https://cdn.artofproblemsolving.com/attachments/0/f/f9c9ff23416565760df225c133330e795b9076.png[/img]
[b]p2.[/b] Assuming that each distinct arrangement of the letters in $DISCUSSIONS$ is equally likely to occur, what is the probability that a random arrangement of the letters in $DISCUSSIONS$ has all the $S$’s together?
[b]p3.[/b] Evaluate
$$\frac{(1 + 2022)(1 + 2022^2)(1 + 2022^4) ... (1 + 2022^{2^{2022}})}{1 + 2022 + 2022^2 + ... + 2022^{2^{2023}-1}} .$$
[b]p4.[/b] Dr. Kraines has $27$ unit cubes, each of which has one side painted red while the other five are white. If he assembles his cubes into one $3 \times 3 \times 3$ cube by placing each unit cube in a random orientation, what is the probability that the entire surface of the cube will be white, with no red faces visible? If the answer is $2^a3^b5^c$ for integers $a$, $b$, $c$, find $|a + b + c|$.
[b]p5.[/b] Let S be a subset of $\{1, 2, 3, ... , 1000, 1001\}$ such that no two elements of $S$ have a difference of $4$ or $7$. What is the largest number of elements $S$ can have?
[b]p6.[/b] George writes the number $1$. At each iteration, he removes the number $x$ written and instead writes either $4x+1$ or $8x+1$. He does this until $x > 1000$, after which the game ends. What is the minimum possible value of the last number George writes?
[b]p7.[/b] List all positive integer ordered pairs $(a, b)$ satisfying $a^4 + 4b^4 = 281 \cdot 61$.
[b]p8.[/b] Karthik the farmer is trying to protect his crops from a wildfire. Karthik’s land is a $5 \times 6$ rectangle divided into $30$ smaller square plots. The $5$ plots on the left edge contain fire, the $5$ plots on the right edge contain blueberry trees, and the other $5 \times 4$ plots of land contain banana bushes. Fire will repeatedly spread to all squares with bushes or trees that share a side with a square with fire. How many ways can Karthik replace $5$ of his $20$ plots of banana bushes with firebreaks so that fire will not consume any of his prized blueberry trees?
[b]p9.[/b] Find $a_0 \in R$ such that the sequence $\{a_n\}^{\infty}_{n=0}$ defined by $a_{n+1} = -3a_n + 2^n$ is strictly increasing.
[b]p10.[/b] Jonathan is playing with his life savings. He lines up a penny, nickel, dime, quarter, and half-dollar from left to right. At each step, Jonathan takes the leftmost coin at position $1$ and uniformly chooses a position $2 \le k \le 5$. He then moves the coin to position $k$, shifting all coins at positions $2$ through $k$ leftward. What is the expected number of steps it takes for the half-dollar to leave and subsequently return to position $5$?
PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].
We write in order of increasing number of 1 and all positive integers,which the sum of digits is divisible by $5$. Obtain a sequence of $1, 5, 14, 19. . .$
Prove that the n-th term of the sequence is less than $5n$.
Let $m, n$ be positive integers with $m > 1$. Anastasia partitions the integers $1, 2, \dots , 2m$ into $m$ pairs. Boris then chooses one integer from each pair and finds the sum of these chosen integers.
Prove that Anastasia can select the pairs so that Boris cannot make his sum equal to $n$.
Let $n\geqslant 2$ be a positive integer and $a_1,a_2, \ldots ,a_n$ be real numbers such that \[a_1+a_2+\dots+a_n=0.\]
Define the set $A$ by
\[A=\left\{(i, j)\,|\,1 \leqslant i<j \leqslant n,\left|a_{i}-a_{j}\right| \geqslant 1\right\}\]
Prove that, if $A$ is not empty, then
\[\sum_{(i, j) \in A} a_{i} a_{j}<0.\]
Let $a$ and $b$ be distinct positive integers. The following infinite process takes place on an initially empty board.
[list=i]
[*] If there is at least a pair of equal numbers on the board, we choose such a pair and increase one of its components by $a$ and the other by $b$.
[*] If no such pair exists, we write two times the number $0$.
[/list]
Prove that, no matter how we make the choices in $(i)$, operation $(ii)$ will be performed only finitely many times.
Proposed by [I]Serbia[/I].