Found problems: 5802
Let $X$ be a set of $100$ elements. Find the smallest possible $n$ satisfying the following condition: Given a sequence of $n$ subsets of $X$, $A_1,A_2,\ldots,A_n$, there exists $1 \leq i < j < k \leq n$ such that
$$A_i \subseteq A_j \subseteq A_k \text{ or } A_i \supseteq A_j \supseteq A_k.$$
The sequence $\{a_{n}\}_{n \ge 1}$ is defined by \[a_{1}=1, \; a_{2}=12, \; a_{3}=20, \; a_{n+3}= 2a_{n+2}+2a_{n+1}-a_{n}.\] Prove that $1+4a_{n}a_{n+1}$ is a square for all $n \in \mathbb{N}$.
Let $n>1$ be a positive integer and $\mathcal S$ be the set of $n^{\text{th}}$ roots of unity. Suppose $P$ is an $n$-variable polynomial with complex coefficients such that for all $a_1,\ldots,a_n\in\mathcal S$, $P(a_1,\ldots,a_n)=0$ if and only if $a_1,\ldots,a_n$ are all different. What is the smallest possible degree of $P$?
[i]Adam Ardeishar and Michael Ren[/i]
Let $a_0,b_0$ be positive integers, and define $a_{i+1}=a_i+\lfloor\sqrt{b_i}\rfloor$ and $b_{i+1}=b_i+\lfloor\sqrt{a_i}\rfloor$ for all $i\ge0$. Show that there exists a positive integer $n$ such that $a_n=b_n$.
[i]David Yang.[/i]
[b]a)[/b] Prove that there exists two infinite sequences $ \left( a_n \right)_{n\ge 1} ,\left( b_n \right)_{n\ge 1} $ of nonnegative integers such that $ a_n>b_n $ and $ (2+\sqrt 3)^n =a_n (2+\sqrt 3) -b_n , $ for any natural numbers $ n. $
[b]b)[/b] Prove that the equation $ x^2-4xy+y^2=1 $ has infinitely many solutions in $ \mathbb{N}^2. $
[i]Florian Dumitrel[/i]
[i]Version 1[/i]. Let $n$ be a positive integer, and set $N=2^{n}$. Determine the smallest real number $a_{n}$ such that, for all real $x$,
\[
\sqrt[N]{\frac{x^{2 N}+1}{2}} \leqslant a_{n}(x-1)^{2}+x .
\]
[i]Version 2[/i]. For every positive integer $N$, determine the smallest real number $b_{N}$ such that, for all real $x$,
\[
\sqrt[N]{\frac{x^{2 N}+1}{2}} \leqslant b_{N}(x-1)^{2}+x .
\]
Find all functions $f : R \to R$ satisfying the following conditions
(a) $f(1) = 1$,
(b) $f(x + y) = f(x) + f(y)$, $\forall (x,y) \in R^2$
(c) $f\left(\frac{1}{x}\right) =\frac{ f(x)}{x^2 }$, $\forall x \in R -\{0\}$
Trần Nam Dũng
There are $2020$ positive integers written on a blackboard. Every minute, Zuming erases two of the numbers and replaces them by their sum, difference, product, or quotient. For example, if Zuming erases the numbers $6$ and $3$, he may replace them with one of the numbers in the set $\{6+3, 6-3, 3-6, 6\times 3, 6\div 3, 3\div 6\}$ $= \{9, 3, 3, 18, 2, \tfrac 12\}$. After $2019$ minutes, Zuming writes the single number $-2020$ on the blackboard. Show that it was possible for Zuming to have ended up with the single number $2020$ instead, using the same rules and starting with the same $2020$ integers.
[i]Proposed by Zhuo Qun (Alex) Song[/i]
Let $\mathbb{R}_{>0}$ be the set of all positive real numbers. Find all functions $f:\mathbb{R}_{>0} \to \mathbb{R}_{>0}$ such that for all $x,y\in \mathbb{R}_{>0}$ we have
\[f(x) = f(f(f(x)) + y) + f(xf(y)) f(x+y).\]
Let $\{a_n\}_{n\geq 1}$ be a sequence of real numbers which satisfies the following relation:
\[a_{n+1}=10^n a_n^2\]
(a) Prove that if $a_1$ is small enough, then $\displaystyle\lim_{n\to\infty} a_n =0$.
(b) Find all possible values of $a_1\in \mathbb{R}$, $a_1\geq 0$, such that $\displaystyle\lim_{n\to\infty} a_n =0$.
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$.
If $ x_{k\plus{}1} \equal{} x_k \plus{} \frac12$ for $ k\equal{}1, 2, \dots, n\minus{}1$ and $ x_1\equal{}1,$ find $ x_1 \plus{} x_2 \plus{} \dots \plus{} x_n.$
$ \textbf{(A)}\ \frac{n\plus{}1}{2} \qquad
\textbf{(B)}\ \frac{n\plus{}3}{2} \qquad
\textbf{(C)}\ \frac{n^2\minus{}1}{2} \qquad
\textbf{(D)}\ \frac{n^2\plus{}n}{4} \qquad
\textbf{(E)}\ \frac{n^2\plus{}3n}{4}$
Find all functions $f:\mathbb{N} \rightarrow \mathbb{N}$ such that for every prime number $p$ and natural number $x$,
$$\{ x,f(x),\cdots f^{p-1}(x) \} $$
is a complete residue system modulo $p$. With $f^{k+1}(x)=f(f^k(x))$ for every natural number $k$ and $f^1(x)=f(x)$.
[i]Proposed by IndoMathXdZ[/i]
Let $n$ be a positive integer and let $x_1,\dotsc,x_n$ be positive real numbers satisfying $\vert x_i-x_j\vert \le 1$ for all pairs $(i,j)$ with $1 \le i<j \le n$. Prove that
\[\frac{x_1}{x_2}+\frac{x_2}{x_3}+\dots+\frac{x_{n-1}}{x_n}+\frac{x_n}{x_1} \ge \frac{x_2+1}{x_1+1}+\frac{x_3+1}{x_2+1}+\dots+\frac{x_n+1}{x_{n-1}+1}+\frac{x_1+1}{x_n+1}.\]
A sequence $a_1, a_2, \ldots $ consisting of $1$'s and $0$'s satisfies for all $k>2016$ that
\[ a_k=0 \quad \Longleftrightarrow \quad a_{k-1}+a_{k-2}+\cdots+a_{k-2016}>23. \]
Prove that there exist positive integers $N$ and $T$ such that $a_k=a_{k+T}$ for all $k>N$.
Find all functions $f: \mathbb{Q}\to\mathbb{R}$ which fulfill the following conditions:
a) $f(1)+1>0$;
b) $f(x+y) -xf(y) -yf(x) = f(x)f(y) -x-y +xy$, for all $x,y\in\mathbb{Q}$;
c) $f(x) = 2f(x+1) +x+2$, for every $x\in\mathbb{Q}$.
Find the maximum value of $ x_{0}$ for which there exists a sequence $ x_{0},x_{1}\cdots ,x_{1995}$ of positive reals with $ x_{0} \equal{} x_{1995}$, such that
\[ x_{i \minus{} 1} \plus{} \frac {2}{x_{i \minus{} 1}} \equal{} 2x_{i} \plus{} \frac {1}{x_{i}},
\]
for all $ i \equal{} 1,\cdots ,1995$.
There are two-way flights between some of the $2017$ cities in a country, such that given two cities, it is possible to reach one from the other. No matter how the flights are appointed, one can define $k$ cities as "special city", so that there is a direct flight from each city to at least one "special city". Find the minimum value of $k$.
We call a subset $B$ of natural numbers [i]loyal[/i] if there exists natural numbers $i\le j$ such that $B=\{i,i+1,\ldots,j\}$. Let $Q$ be the set of all [i]loyal[/i] sets. For every subset $A=\{a_1<a_2<\ldots<a_k\}$ of $\{1,2,\ldots,n\}$ we set
\[f(A)=\max_{1\le i \le k-1}{a_{i+1}-a_i}\qquad\text{and}\qquad g(A)=\max_{B\subseteq A, B\in Q} |B|.\] Furthermore, we define \[F(n)=\sum_{A\subseteq \{1,2,\ldots,n\}} f(A)\qquad\text{and}\qquad G(n)=\sum_{A\subseteq \{1,2,\ldots,n\}} g(A).\] Prove that there exists $m\in \mathbb N$ such that for each natural number $n>m$ we have $F(n)>G(n)$. (By $|A|$ we mean the number of elements of $A$, and if $|A|\le 1$, we define $f(A)$ to be zero).
[i]Proposed by Javad Abedi[/i]
For every integer $m\ge 1$, let $\mathbb{Z}/m\mathbb{Z}$ denote the set of integers modulo $m$. Let $p$ be a fixed prime and let $a\ge 2$ and $e\ge 1$ be fixed integers. Given a function $f\colon \mathbb{Z}/a\mathbb{Z}\to \mathbb{Z}/p^e\mathbb{Z}$ and an integer $k\ge 0$, the $k$[i]th finite difference[/i], denoted $\Delta^k f$, is the function from $\mathbb{Z}/a\mathbb{Z}$ to $\mathbb{Z}/p^e\mathbb{Z}$ defined recursively by
\begin{align*}
\Delta^0 f(n)&=f(n)\\
\Delta^k f(n)&=\Delta^{k-1}f(n+1)-\Delta^{k-1}f(n) & \text{for } k=1,2,\dots.
\end{align*}
Determine the number of functions $f$ such that there exists some $k\ge 1$ for which $\Delta^kf=f$.
[i]Holden Mui[/i]
Find all functions $f:\mathbb{R} \rightarrow \mathbb{R}$ that satisfy the conditions
\[f(1+xy)-f(x+y)=f(x)f(y) \quad \text{for all } x,y \in \mathbb{R},\]
and $f(-1) \neq 0$.
Let $n \geq 2$ be an integer. Let $P(x_1, x_2, \ldots, x_n)$ be a nonconstant $n$-variable polynomial with real coefficients. Assume that whenever $r_1, r_2, \ldots , r_n$ are real numbers, at least two of which are equal, we have $P(r_1, r_2, \ldots , r_n) = 0$. Prove that $P(x_1, x_2, \ldots, x_n)$ cannot be written as the sum of fewer than $n!$ monomials. (A monomial is a polynomial of the form $cx^{d_1}_1 x^{d_2}_2\ldots x^{d_n}_n$, where $c$ is a nonzero real number and $d_1$, $d_2$, $\ldots$, $d_n$ are nonnegative integers.)
[i]Proposed by Ankan Bhattacharya[/i]
Find all integers $n$ satisfying $n \geq 2$ and $\dfrac{\sigma(n)}{p(n)-1} = n$, in which $\sigma(n)$ denotes the sum of all positive divisors of $n$, and $p(n)$ denotes the largest prime divisor of $n$.
Let $\mathbb{Z}_{\geq 0}$ be the set of nonnegative integers. Let $f: \mathbb{Z}_{\geq0} \to \mathbb{Z}_{\geq0}$ be a function such that, for all $a,b \in \mathbb{Z}_{\geq0}$: \[f(a)^2+f(b)^2+f(a+b)^2=1+2f(a)f(b)f(a+b).\]
Furthermore, suppose there exists $n \in \mathbb{Z}_{\geq0}$ such that $f(n)=577$. Let $S$ be the sum of all possible values of $f(2017)$. Find the remainder when $S$ is divided by $2017$.
[i]Proposed by Zack Chroman[/i]
Find all positive integers $m$ such that there exist positive integers $a_1,a_2,\ldots,a_{1378}$ such that:
\[ m=\sum_{k=1}^{1378}{\frac{k}{a_k}}. \]