Found problems: 5802
Find all functions $f:\mathbb{Z} \rightarrow \mathbb{Z}$ such that $f(1) \neq f(-1)$ and $$f(m+n)^2 \mid f(m)-f(n)$$ for all integers $m, n$.
[i]Proposed by Liam Baker, South Africa[/i]
Two rational numbers \(\tfrac{m}{n}\) and \(\tfrac{n}{m}\) are written on a blackboard, where \(m\) and \(n\) are relatively prime positive integers. At any point, Evan may pick two of the numbers \(x\) and \(y\) written on the board and write either their arithmetic mean \(\tfrac{x+y}{2}\) or their harmonic mean \(\tfrac{2xy}{x+y}\) on the board as well. Find all pairs \((m,n)\) such that Evan can write 1 on the board in finitely many steps.
[i]Proposed by Yannick Yao[/i]
Let $f_0, f_1,...$ be the Fibonacci sequence: $f_0 = f_1 = 1, f_n = f_{n-1} + f_{n-2}$ if $n \geq 2$.
Determine all possible positive integers $n$ so that there is a positive integer $a$ such that
$f_n \leq a \leq f_{n+1}$ and that $a( \frac{1}{f_1}+\frac{1}{f_1f_2}+\cdots+\frac{1}{f_1f_2...f_n} )$
is an integer.
Prove that
$$\sum\limits_{n = 1}^{\infty}\frac{1}{\sqrt{n}\left(n+1\right)} < 2.$$
Proposed by Ivan Krijan, University of Zagreb
The infinite sequence $a_0,a _1, a_2, \dots$ of (not necessarily distinct) integers has the following properties: $0\le a_i \le i$ for all integers $i\ge 0$, and \[\binom{k}{a_0} + \binom{k}{a_1} + \dots + \binom{k}{a_k} = 2^k\] for all integers $k\ge 0$. Prove that all integers $N\ge 0$ occur in the sequence (that is, for all $N\ge 0$, there exists $i\ge 0$ with $a_i=N$).
Determine all positive integers $M$ such that the sequence $a_0, a_1, a_2, \cdots$ defined by \[ a_0 = M + \frac{1}{2} \qquad \textrm{and} \qquad a_{k+1} = a_k\lfloor a_k \rfloor \quad \textrm{for} \, k = 0, 1, 2, \cdots \] contains at least one integer term.
Let $f: \mathbb{Q}\rightarrow \mathbb{R}$ be a function such that \[|f(x)-f(y)|\leq (x-y)^{2}\] for all $x,y \in\mathbb{Q}$. Prove that $f$ is constant.
It is given sequence wih length of $2017$ which consists of first $2017$ positive integers in arbitrary order (every number occus exactly once). Let us consider a first term from sequence, let it be $k$. From given sequence we form a new sequence of length 2017, such that first $k$ elements of new sequence are same as first $k$ elements of original sequence, but in reverse order while other elements stay unchanged. Prove that if we continue transforming a sequence, eventually we will have sequence with first element $1$.
Prove that the numbers $A,B$ and $C$ are equal, where:
- $A=$ number of ways that we can cover a $2 \times n$ rectangle with $2 \times 1$ retangles.
- $B=$ number of sequences of ones and twos that add up to $n$
- $C= \sum^m_{k=0} \binom{m + k}{2 \cdot k}$ if $n = 2 \cdot m,$ and
- $C= \sum^m_{k=0} \binom{m + k + 1}{2 \cdot k + 1}$ if $n = 2 \cdot m + 1.$
Let $d > 0$ be an arbitrary real number. Consider the set $S_{n}(d)=\{s=\frac{1}{x_{1}}+\frac{1}{x_{2}}+...+\frac{1}{x_{n}}|x_{i}\in\mathbb{N},s<d\}$. Prove that $S_{n}(d)$ has a maximum element.
Let Q+ and Z denote the set of positive rationals and the set of inte-
gers, respectively. Find all functions f : Q+ → Z satisfying the following
conditions:
(i) f(1999) = 1;
(ii) f(ab) = f(a) + f(b) for all a, b ∈ Q+;
(iii) f(a + b) ≥ min{f(a), f(b)} for all a, b ∈ Q+.
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.
Let $m$ and $n$ be positive integers and $S$ be a subset with $(2^m-1)n+1$ elements of the set $\{1,2,3,\ldots, 2^mn\}$. Prove that $S$ contains $m+1$ distinct numbers $a_0,a_1,\ldots, a_m$ such that $a_{k-1} \mid a_{k}$ for all $k=1,2,\ldots, m$.
Let $n$ be a positive integer and let $\alpha_n $ be the number of $1$'s within binary representation of $n$.
Show that for all positive integers $r$,
\[2^{2n-\alpha_n}\phantom{-1} \bigg|^{\phantom{0}}_{\phantom{-1}} \sum_{k=-n}^{n} \binom{2n}{n+k} k^{2r}.\]
What is the value of the product$$\left(1+\frac{1}{1}\right)\cdot\left(1+\frac{1}{2}\right)\cdot\left(1+\frac{1}{3}\right)\cdot\left(1+\frac{1}{4}\right)\cdot\left(1+\frac{1}{5}\right)\cdot\left(1+\frac{1}{6}\right)?$$
$\textbf{(A) }\frac{7}{6}\qquad\textbf{(B) }\frac{4}{3}\qquad\textbf{(C) }\frac{7}{2}\qquad\textbf{(D) }7\qquad\textbf{(E) }8$
Let $a, b$, and $n$ be integers such that $a + b$ is divisible by $n$ and $a^2 + b^2$ is divisible by $n^2$. Prove that $a^m + b^m$ is divisible by $n^m$ for all positive integers $m$.
The Fibonacci sequence $F_n$ is defined by $F_0=0,F_1=1$ and the recurrence relation $F_n=F_{n-1}+F_{n-2}$ for all integers $n\geq2$. Let $p\geq3$ be a prime number.
[list=a]
[*] Prove that $F_{p-1}+F_{p+1}-1$ is divisible by $p$.
[*] Prove that $F_{p^{k+1}-1}+F_{p^{k+1}+1}-\left(F_{p^k-1}+F_{p^k+1}\right)$ is divisible by $p^{k+1}$ for any positive integer $k$.
[/list]
Find all functions $f:\mathbb{N} \to \mathbb{N}$ such that\[f\left(\Big \lceil \frac{f(m)}{n} \Big \rceil\right)=\Big \lceil \frac{m}{f(n)} \Big \rceil\]for all $m,n \in \mathbb{N}$.
[i]Proposed by Md. Ashraful Islam Fahim[/i]
Let $T$ be a tree on $n$ vertices with exactly $k$ leaves. Suppose that there exists a subset of at least $\frac{n+k-1}{2}$ vertices of $T$, no two of which are adjacent. Show that the longest path in $T$ contains an even number of edges. [hide=*]A tree is a connected graph with no cycles. A leaf is a vertex of degree 1[/hide]
[i]Vincent Huang[/i]
In some city there are $2000000$ citizens. In every group of $2000$ citizens there are $3$ pairwise friends. Prove, that there are $4$ pairwise friends in city.
A student wrote down the following sequence of numbers : the first number is 1, the second number is 2, and after that, each number is obtained by adding together all the previous numbers. Determine the 12th number in the sequence.
Let $a_1$ , $\ldots$ , $a_n$ be positive integers and $a$ a positive integer that is greater than $1$ and is divisible by the product $a_1a_2\ldots a_n$. Prove that $a^{n+1}+a-1$ is not divisible by the product $(a+a_1-1)(a+a_2-1)\ldots(a+a_n-1)$.
Determine the maximal length $L$ of a sequence $a_1,\dots,a_L$ of positive integers satisfying both the following properties:
[list=disc]
[*]every term in the sequence is less than or equal to $2^{2023}$, and
[*]there does not exist a consecutive subsequence $a_i,a_{i+1},\dots,a_j$ (where $1\le i\le j\le L$) with a choice of signs $s_i,s_{i+1},\dots,s_j\in\{1,-1\}$ for which \[s_ia_i+s_{i+1}a_{i+1}+\dots+s_ja_j=0.\]
[/list]
There are $n$ students standing in a circle, one behind the other. The students have heights $h_1<h_2<\dots <h_n$. If a student with height $h_k$ is standing directly behind a student with height $h_{k-2}$ or less, the two students are permitted to switch places. Prove that it is not possible to make more than $\binom{n}{3}$ such switches before reaching a position in which no further switches are possible.
Let $a, b$, and $c$ be integers such that $a+b+c$ divides $a^2 +b^2 +c^2$. Prove that there are infinitely many positive integers $n$ such that $a+b+c$ divides $a^n +b^n +c^n$.