Found problems: 5802
Let $n$ be a positive integer and $\{A,B,C\}$ a partition of $\{1,2,\ldots,3n\}$ such that $|A|=|B|=|C|=n$. Prove that there exist $x \in A$, $y \in B$, $z \in C$ such that one of $x,y,z$ is the sum of the other two.
On each day of their tour of the West Indies, Sourav and Srinath have either an apple or an orange for breakfast. Sourav has oranges for the first $m$ days, apples for the next $m$ days, followed by oranges for the next $m$ days, and so on. Srinath has oranges for the first $n$ days, apples for the next $n$ days, followed by oranges for the next $n$ days, and so on.
If $\gcd(m,n)=1$, and if the tour lasted for $mn$ days, on how many days did they eat the same kind of fruit?
Let $\tau(n)$ be the number of positive divisors of $n$. Let $\tau_1(n)$ be the number of positive divisors of $n$ which have remainders $1$ when divided by $3$. Find all positive integral values of the fraction $\frac{\tau(10n)}{\tau_1(10n)}$.
There is an $n \times n$ grid which has rows and columns numbered from $1$ to $n$; the cell at row $i$ and column $j$ is denoted as the cell at $(i, j)$. A subset $A$ of the cells is called [i]good[/i] if for any two cells at $(x_1, y), (x_2, y)$ in $A$, the cells $(u, v)$ satisfying $x_1 < u \leq x_2, v<y$ or $x_1 \leq u < x_2, v>y$ are not in $A$. Determine the minimal number of good sets such that they are pairwise disjoint and every cell of the board belongs to exactly one good set.
Given a positive integer number $n$, determine the minimum of
\[\max \left\{\dfrac{x_1}{1 + x_1},\, \dfrac{x_2}{1 + x_1 + x_2},\, \cdots,\, \dfrac{x_n}{1 + x_1 + x_2 + \cdots + x_n}\right\},\]
as $x_1, x_2, \ldots, x_n$ run through all non-negative real numbers which add up to $1$.
[i]Kvant Magazine[/i]
$p$ is a polynomial with integer coefficients and for every natural $n$ we have $p(n)>n$. $x_k $ is a sequence that: $x_1=1, x_{i+1}=p(x_i)$ for every $N$ one of $x_i$ is divisible by $N.$ Prove that $p(x)=x+1$
A graph has $100$ points. Given any four points, there is one joined to the other three. Show that one point must be joined to all $99$ other points. What is the smallest number possible of such points (that are joined to all the others)?
Denote by $\mathbb{V}$ the real vector space of all real polynomials in one variable, and let $\gamma :\mathbb{V}\to \mathbb{R}$ be a linear map. Suppose that for all $f,g\in \mathbb{V}$ with $\gamma(fg)=0$ we have $\gamma(f)=0$ or $\gamma(g)=0$. Prove that there exist $c,x_0\in \mathbb{R}$ such that
\[ \gamma(f)=cf(x_0)\quad \forall f\in \mathbb{V}\]
Prove that for every real number $M$ there exists an infinite arithmetic progression such that:
- each term is a positive integer and the common difference is not divisible by 10
- the sum of the digits of each term (in decimal representation) exceeds $M$.
$ k$ is a given natural number. Find all functions $ f: \mathbb{N}\rightarrow\mathbb{N}$ such that for each $ m,n\in\mathbb{N}$ the following holds: \[ f(m)\plus{}f(n)\mid (m\plus{}n)^k\]
There is a $2012\times 2012$ grid with rows numbered $1,2,\dots 2012$ and columns numbered $1,2,\dots, 2012$, and we place some rectangular napkins on it such that the sides of the napkins all lie on grid lines. Each napkin has a positive integer thickness. (in micrometers!)
(a) Show that there exist $2012^2$ unique integers $a_{i,j}$ where $i,j \in [1,2012]$ such that for all $x,y\in [1,2012]$, the sum \[ \sum _{i=1}^{x} \sum_{j=1}^{y} a_{i,j} \] is equal to the sum of the thicknesses of all the napkins that cover the grid square in row $x$ and column $y$.
(b) Show that if we use at most $500,000$ napkins, at least half of the $a_{i,j}$ will be $0$.
[i]Proposed by Ray Li[/i]
Find all positive integers $n$ and sequence of integers $a_0,a_1,\ldots, a_n$ such that the following hold:
1. $a_n\neq 0$;
2. $f(a_{i-1})=a_i$ for all $i=1,\ldots, n$, where $f(x) = a_nx^n+a_{n-1}x^{n-1}+\cdots +a_0$.
[i]
Proposed by usjl[/i]
Let $f:\mathbb{Z}^2\rightarrow\mathbb{Z}$ be a function satisfying
\[f(x+1,y)+f(x,y+1)+1=f(x,y)+f(x+1,y+1)\]
for all integers $x$ and $y$. Can it happen that $|f(x,y)|\leq 2024$ for all $x,y\in\mathbb{Z}$?
The infinite sequence \( a_1, a_2, \ldots \) is defined by \( a_1 = 1 \) and, for each \( n \geq 1 \), the number \( a_{n+1} \) is the smallest positive integer greater than \( a_n \) that has the following property: for each \( k \in \{1, 2, \ldots, n\} \), the number \( a_{n+1} + a_k \) is not a perfect square. Prove that, for all \( n \), it holds that \( a_n \leq (n - 1)^2 + 1 \).
A Dyck $n$-path is a lattice path of $n$ upsteps $(1, 1)$ and $n$ downsteps $(1, -1)$ that starts at the origin $O$ and never dips below the $x$-axis. A return is a maximal sequence of contiguous downsteps that terminates on the $x$-axis. For example, the Dyck $5$-path illustrated has two returns, of length $3$ and $1$ respectively. Show that there is a one-to-one correspondence between the Dyck $n$-paths with no return of even length and the Dyck $(n - 1)$ paths.
\[\begin{picture}(165,70)
\put(-5,0){O}
\put(0,10){\line(1,0){150}}
\put(0,10){\line(1,1){30}}
\put(30,40){\line(1,-1){15}}
\put(45,25){\line(1,1){30}}
\put(75,55){\line(1,-1){45}}
\put(120,10){\line(1,1){15}}
\put(135,25){\line(1,-1){15}}
\put(0,10){\circle{1}}\put(0,10){\circle{2}}\put(0,10){\circle{3}}\put(0,10){\circle{4}}
\put(15,25){\circle{1}}\put(15,25){\circle{2}}\put(15,25){\circle{3}}\put(15,25){\circle{4}}
\put(30,40){\circle{1}}\put(30,40){\circle{2}}\put(30,40){\circle{3}}\put(30,40){\circle{4}}
\put(45,25){\circle{1}}\put(45,25){\circle{2}}\put(45,25){\circle{3}}\put(45,25){\circle{4}}
\put(60,40){\circle{1}}\put(60,40){\circle{2}}\put(60,40){\circle{3}}\put(60,40){\circle{4}}
\put(75,55){\circle{1}}\put(75,55){\circle{2}}\put(75,55){\circle{3}}\put(75,55){\circle{4}}
\put(90,40){\circle{1}}\put(90,40){\circle{2}}\put(90,40){\circle{3}}\put(90,40){\circle{4}}
\put(105,25){\circle{1}}\put(105,25){\circle{2}}\put(105,25){\circle{3}}\put(105,25){\circle{4}}
\put(120,10){\circle{1}}\put(120,10){\circle{2}}\put(120,10){\circle{3}}\put(120,10){\circle{4}}
\put(135,25){\circle{1}}\put(135,25){\circle{2}}\put(135,25){\circle{3}}\put(135,25){\circle{4}}
\put(150,10){\circle{1}}\put(150,10){\circle{2}}\put(150,10){\circle{3}}\put(150,10){\circle{4}}
\end{picture}\]
Given two natural numbers $ n\ge 2,a, $ prove that there exists another natural number $ v\ge 2 $ such that:
$$ \frac{v+\sqrt{v^2-4}}{2} =\left( \frac{n+\sqrt{n^2-4}}{2} \right)^a $$
Find all pairs of prime numbers $p,\,q(p\le q)$ satisfying the following condition:
There exists a natural number $n$ such that $2^{n}+3^{n}+\cdots+(2pq-1)^{n}$ is a multiple of $2pq$.
Consider $n$ disks $C_{1}; C_{2}; ... ; C_{n}$ in a plane such that for each $1 \leq i < n$, the center of $C_{i}$ is on the circumference of $C_{i+1}$, and the center of $C_{n}$ is on the circumference of $C_{1}$. Define the [i]score[/i] of such an arrangement of $n$ disks to be the number of pairs $(i; j )$ for which $C_{i}$ properly contains $C_{j}$ . Determine the maximum possible score.
Prove that there exist infinitely many positive integers $n$ such that the largest prime divisor of $n^4 + n^2 + 1$ is equal to the largest prime divisor of $(n+1)^4 + (n+1)^2 +1$.
Let $n \geqslant 100$ be an integer. Ivan writes the numbers $n, n+1, \ldots, 2 n$ each on different cards. He then shuffles these $n+1$ cards, and divides them into two piles. Prove that at least one of the piles contains two cards such that the sum of their numbers is a perfect square.
There are $2022$ users on a social network called Mathbook, and some of them are Mathbook-friends. (On Mathbook, friendship is always mutual and permanent.)
Starting now, Mathbook will only allow a new friendship to be formed between two users if they have [i]at least two[/i] friends in common. What is the minimum number of friendships that must already exist so that every user could eventually become friends with every other user?
Let $n\geq 3$ be an integer. Find the number of functions $f:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$ such that
\[ f(f(k)) = f^3(k) - 6f^2(k) + 12f(k) - 6 , \ \textrm{ for all } k \geq 1 . \]
Let $P(x)$ be a polynomial of degree $n$ with real coefficients and let $a\geq 3$. Prove that
\[\max_{0\leq j \leq n+1}\left | a^j-P(j) \right |\geq 1\]
Determine all values of $a_0$ for which the sequence of real numbers with $a_{n+1}=3a_n - 4a_n^3$ for all $n\geq 0$ is periodic from the beginning.
Two positive integers $p,q \in \mathbf{Z}^{+}$ are given. There is a blackboard with $n$ positive integers written on it. A operation is to choose two same number $a,a$ written on the blackboard, and replace them with $a+p,a+q$. Determine the smallest $n$ so that such operation can go on infinitely.