Found problems: 5802
For each non-negative integer $n$, let $u_n = \left( 2+\sqrt{5} \right)^n + \left( 2-\sqrt{5} \right)^n$.
a) Prove that $u_n$ is a positive integer for all $n \geq 0$. When $n$ changes, what is the largest possible remainder when $u_n$ is divided by $24$?
b) Find all pairs of positive integers $(a, b)$ such that $a, b < 500$ and for all odd positive integers $n$, $u_n \equiv a^n - b^n \pmod {1111}$.
Sequences $(a_n)_{n=0}^{\infty}$ and $(b_n)_{n=0}^{\infty}$ are defined with recurrent relations :
$$a_0=0 , \;\;\; a_1=1, \;\;\;\; a_{n+1}=\frac{2018}{n} a_n+ a_{n-1}\;\;\; \text {for }\;\;\; n\geq 1$$ and
$$b_0=0 , \;\;\; b_1=1, \;\;\;\; b_{n+1}=\frac{2020}{n} b_n+ b_{n-1}\;\;\; \text {for }\;\;\; n\geq 1$$
Prove that :$$\frac{a_{1010}}{1010}=\frac{b_{1009}}{1009}$$
The problem is about real polynomial functions, denoted by $f$, of degree $\deg f$.
a) Prove that a polynomial function $f$ can`t be wrriten as sum of at most $\deg f$ periodic functions.
b) Show that if a polynomial function of degree $1$ is written as sum of two periodic functions, then they are unbounded on every interval (thus, they are "wild").
c) Show that every polynomial function of degree $1$ can be written as sum of two periodic functions.
d) Show that every polynomial function $f$ can be written as sum of $\deg f+1$ periodic functions.
e) Give an example of a function that can`t be written as a finite sum of periodic functions.
[i]Dan Schwarz[/i]
Consider the sequence defined by \(a_1 = 2\), \(a_2 = 3\), and
\[
a_{2k+1} = 2 + 2a_k, \quad a_{2k+2} = 2 + a_k + a_{k+1},
\]
for all integers \(k \geq 1\). Determine all positive integers \(n\) such that
\[
\frac{a_n}{n}
\]
is an integer.
Proposed by Niranjan Balachandran, SS Krishnan, and Prithwijit De.
A rabbit initially stands at the position $0$, and repeatedly jumps on the real line. In each jump, the rabbit can jump to any position corresponds to an integer but it cannot stand still. Let $N(a)$ be the number of ways to jump with a total distance of $2019$ and stop at the position $a$. Determine all integers $a$ such that $N(a)$ is odd.
Find the largest integer $ n$ satisfying the following conditions:
(i) $ n^2$ can be expressed as the difference of two consecutive cubes;
(ii) $ 2n\plus{}79$ is a perfect square.
Show that there exists a unique sequence of decimal digits $p_0=5,p_1,p_2,\ldots$ such that, for any $k$, the square of any positive integer ending with $\overline{p_kp_{k-1}\cdots p_0}$ ends with the same digits.
Prove that for every integer power of 2, there exists a multiple of it with all digits (in decimal expression) not zero.
Determine all functions $f$ from the set of non-negative integers to itself such that $f(a + b) = f(a) + f(b) + f(c) + f(d)$, whenever $a, b, c, d$, are non-negative integers satisfying $2ab = c^2 + d^2$.
A round robin tournament is held with $2016$ participants. Each player plays each other player once and no games result in ties. We say a pair of players $A$ and $B$ is a [i]dominant pair[/i] if all other players either defeat $A$ and $B$ or are defeated by both $A$ and $B$. Find the maximum number dominant pairs.
[i]Proposed by Nathan Ramesh
Let $n\geq 4$ and $y_1,\dots, y_n$ real with
$$\sum_{k=1}^n y_k=\sum_{k=1}^n k y_k=\sum_{k=1}^n k^2y_k=0$$
and
$$y_{k+3}-3y_{k+2}+3y_{k+1}-y_k=0$$
for $1\leq k\leq n-3$. Prove that
$$\sum_{k=1}^n k^3y_k=0$$
Given natural numbers $a,b$ and function $f: \mathbb{N} \to \mathbb{N} $ such that for any natural number $n, f\left( n+a \right)$ is divided by $f\left( {\left[ {\sqrt n } \right] + b} \right)$. Prove that for any natural $n$ exist $n$ pairwise distinct and pairwise relatively prime natural numbers ${{a}_{1}}$, ${{a}_{2}}$, $\ldots$, ${{a}_{n}}$ such that the number $f\left( {{a}_{i+1}} \right)$ is divided by $f\left( {{a}_{i}} \right)$ for each $i=1,2, \dots ,n-1$ .
(Here $[x]$ is the integer part of number $x$, that is, the largest integer not exceeding $x$.)
Let $ n$ be a positive integer and let $ a_1,a_2,a_3,\ldots,a_k$ $ ( k\ge 2)$ be distinct integers in the set $ { 1,2,\ldots,n}$ such that $ n$ divides $ a_i(a_{i + 1} - 1)$ for $ i = 1,2,\ldots,k - 1$. Prove that $ n$ does not divide $ a_k(a_1 - 1).$
[i]Proposed by Ross Atkins, Australia [/i]
A $\textit{lattice point}$ of the coordinate plane is a point $(x,y)$ in which both $x$ and $y$ are integers. Let $k\geq2$ be a positive integer. Find the smallest positive integer $c_k$ (which may depend on $k$) such that every lattice point can be colored with one of $c_k$ colors, subject to the following two conditions:
[list=1]
[*] If $(x,y)$ and $(a,b)$ are two distinct neighboring points; that is, $|x-a|\leq1$ and $|y-b|\leq1$, then $(x,y)$ and $(a,b)$ must be different colors. [/*]
[*] If $(x,y)$ and $(a,b)$ are two lattice points such that $x\equiv a\pmod{k}$ and $y\equiv b\pmod{k}$, then $(x,y)$ and $(a,b)$ must be the same color. [/*]
[/list]
Let $g:\mathbb{N}\to \mathbb{N}$ be a bijective function and suppose that $f:\mathbb{N}\to \mathbb{N}$ is a function such that:
[list]
[*] For all naturals $x$, $$\underbrace{f(\cdots (f}_{x^{2023}\;f\text{'s}}(x)))=x. $$
[*] For all naturals $x,y$ such that $x|y$, we have $f(x)|g(y)$.
[/list]
Prove that $f(x)=x$.
[i]Proposed by Pulkit Sinha[/i]
A cake has the form of an $ n$ x $ n$ square composed of $ n^{2}$ unit squares. Strawberries lie on some of the unit squares so that each row or column contains exactly one strawberry; call this arrangement $\mathcal{A}$.
Let $\mathcal{B}$ be another such arrangement. Suppose that every grid rectangle with one vertex at the top left corner of the cake contains no fewer strawberries of arrangement $\mathcal{B}$ than of arrangement $\mathcal{A}$. Prove that arrangement $\mathcal{B}$ can be obtained from $ \mathcal{A}$ by performing a number of switches, defined as follows:
A switch consists in selecting a grid rectangle with only two strawberries, situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle.
Let $ n$ be an integer, $ n\geq 2$, and the integers $ a_1,a_2,\ldots,a_n$, such that $ 0 < a_k\leq k$, for all $ k \equal{} 1,2,\ldots,n$. Knowing that the number $ a_1 \plus{} a_2 \plus{} \cdots \plus{} a_n$ is even, prove that there exists a choosing of the signs $ \plus{}$, respectively $ \minus{}$, such that
\[ a_1 \pm a_2 \pm \cdots \pm a_n\equal{} 0.
\]
Let $f: \mathbb N \to \mathbb N$ be a function such that $f(1)=1$ and
\[f(n)=n - f(f(n-1)), \quad \forall n \geq 2.\]
Prove that $f(n+f(n))=n $ for each positive integer $n.$
The sequence $(x_n)$ is defined as follows:
$$x_1=2,\, x_{n+1}=\sqrt{x_n+8}-\sqrt{x_n+3}$$
for all $n\geq 1$.
a. Prove that $(x_n)$ has a finite limit and find that limit.
b. For every $n\geq 1$, prove that
$$n\leq x_1+x_2+\dots +x_n\leq n+1.$$
Let $b$ and $c$ be any two positive integers. Define an integer sequence $a_n$, for $n\geq 1$, by $a_1=1$, $a_2=1$, $a_3=b$ and $a_{n+3}=ba_{n+2}a_{n+1}+ca_n$.
Find all positive integers $r$ for which there exists a positive integer $n$ such that the number $a_n$ is divisible by $r$.
A holey triangle is an upward equilateral triangle of side length $n$ with $n$ upward unit triangular holes cut out. A diamond is a $60^\circ-120^\circ$ unit rhombus.
Prove that a holey triangle $T$ can be tiled with diamonds if and only if the following condition holds: Every upward equilateral triangle of side length $k$ in $T$ contains at most $k$ holes, for $1\leq k\leq n$.
[i]Proposed by Federico Ardila, Colombia [/i]
$N$ teams take part in a league. Every team plays every other team exactly once during the league, and receives 2 points for each win, 1 point for each draw, and 0 points for each loss. At the end of the league, the sequence of total points in descending order $\mathcal{A} = (a_1 \ge a_2 \ge \cdots \ge a_N )$ is known, as well as which team obtained which score. Find the number of sequences $\mathcal{A}$ such that the outcome of all matches is uniquely determined by this information.
[I]Proposed by Dominic Yeo, United Kingdom.[/i]
Let $g$ and $h$ be two distinct elements of a group $G$, and let $n$ be a positive integer. Consider a sequence $w=(w_1,w_2,\dots)$ which is not eventually periodic and where each $w_i$ is either $g$ or $h$. Denote by $H$ the subgroup of $G$ generated by all elements of the form $w_kw_{k+1}\dotsc w_{k+n-1}$ with $k \ge 1$. Prove that $H$ does not depend on the choice of the sequence $w$ (but may depend on $n$).
Let $n\geq 2$ be an integer and let $a_1,a_2,\ldots,a_n$ be real numbers. Prove that for any non-empty subset $S\subset \{1,2,3,\ldots, n\}$ we have
\[ \left( \sum_{i \in S} a_i \right)^2 \leq \sum_{1\leq i \leq j \leq n } (a_i + \cdots + a_j ) ^2 . \]
[i]Gabriel Dospinescu[/i]
Find all functions $f\colon\mathbb R\to\mathbb R$ such that for all real numbers $x$ and $y$,
\[f(xf(y))+f(y)=f(x+y)+f(xy).\]
[i]Milan Haiman[/i]