Found problems: 5802
In each square of a garden shaped like a $2022 \times 2022$ board, there is initially a tree of height $0$. A gardener and a lumberjack alternate turns playing the following game, with the gardener taking the first turn:
[list]
[*] The gardener chooses a square in the garden. Each tree on that square and all the surrounding squares (of which there are at most eight) then becomes one unit taller.
[*] The lumberjack then chooses four different squares on the board. Each tree of positive height on those squares then becomes one unit shorter.
[/list]
We say that a tree is [i]majestic[/i] if its height is at least $10^6$. Determine the largest $K$ such that the gardener can ensure there are eventually $K$ majestic trees on the board, no matter how the lumberjack plays.
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$).
If $m\geq 2$ show that there does not exist positive integers $x_1, x_2, ..., x_m,$ such that \[x_1< x_2<...< x_m \ \ \text{and} \ \ \frac{1}{x_1^3}+\frac{1}{x_2^3}+...+\frac{1}{x_m^3}=1.\]
Denote by S the set of all primes such the decimal representation of $\frac{1}{p}$ has the fundamental period divisible by 3. For every $p \in S$ such that $\frac{1}{p}$ has the fundamental period $3r$ one may write
\[\frac{1}{p}=0,a_{1}a_{2}\ldots a_{3r}a_{1}a_{2} \ldots a_{3r} \ldots , \]
where $r=r(p)$; for every $p \in S$ and every integer $k \geq 1$ define $f(k,p)$ by \[ f(k,p)= a_{k}+a_{k+r(p)}+a_{k+2.r(p)}\]
a) Prove that $S$ is infinite.
b) Find the highest value of $f(k,p)$ for $k \geq 1$ and $p \in S$
Given positive integers $a,b$, let the integers $q,r$, with $0 \leq r < ab$, be such that $a^2 + b^2 = abq + r$. Prove that $q + r \leq ab + 1$ and find all equality cases.
A game is played by $n$ girls ($n \geq 2$), everybody having a ball. Each of the $\binom{n}{2}$ pairs of players, is an arbitrary order, exchange the balls they have at the moment. The game is called nice [b]nice[/b] if at the end nobody has her own ball and it is called [b]tiresome[/b] if at the end everybody has her initial ball. Determine the values of $n$ for which there exists a nice game and those for which there exists a tiresome game.
For each integer $n\ge 1,$ compute the smallest possible value of \[\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor\] over all permutations $(a_1,\dots,a_n)$ of $\{1,\dots,n\}.$
[i]Proposed by Shahjalal Shohag, Bangladesh[/i]
Let $Z$ be the set of all integers. Find all the function $f: Z->Z$ such that
$f(4x+3y)=f(3x+y)+f(x+2y)$
For all integers $x,y$
Find all functions $f : R \to R$ such that $x[f(x + y) - f (x - y)] = 4y f (x)$ for any real numbers $x, y$.
There are $2024$ mathematicians sitting in a row next to the river Tisza. Each of them is working on exactly one research topic, and if two mathematicians are working on the same topic, everyone sitting between them is also working on it.
Marvin is trying to figure out for each pair of mathematicians whether they are working on the same topic. He is allowed to ask each mathematician the following question: “How many of these 2024 mathematicians are working on your topic?” He asks the questions one by one, so he knows all previous answers before he asks the next one.
Determine the smallest positive integer $k$ such that Marvin can always accomplish his goal with at most $k$ questions.
Determine the least integer $k$ for which the following story could hold true:
In a chess tournament with $24$ players, every pair of players plays at least $2$ and at most $k$ games against each other. At the end of the tournament, it turns out that every player has played a different number of games.
Define the sequence $a_1, a_2 \dots$ as follows: $a_1=1$ and for every $n\ge 2$,
\[
a_n = \begin{cases}
n-2 & \text{if } a_{n-1} =0 \\
a_{n-1} -1 & \text{if } a_{n-1} \neq 0
\end{cases}
\]
A non-negative integer $d$ is said to be {\em jet-lagged} if there are non-negative integers $r,s$ and a positive integer $n$ such that $d=r+s$ and that $a_{n+r} = a_n +s$. How many integers in $\{1,2,\dots, 2016\}$ are jet-lagged?
One hundred million cities lie on Planet MO. Initially, there are no air routes between any two cities. Now an airline company comes. It plans to establish $5050$ two-way routes, each route connects two different cities, and no two routes connect the same two cities. The "degree" of a city is defined to be the number of routes departing from that city. The "benefit" of a route is the product of the "degrees" of the two cities it connects.
Find the maximum possible value of the sum of the benefits of these $5050$ routes.
Let $A = (a_1, a_2, \ldots, a_{2001})$ be a sequence of positive integers. Let $m$ be the number of 3-element subsequences $(a_i,a_j,a_k)$ with $1 \leq i < j < k \leq 2001$, such that $a_j = a_i + 1$ and $a_k = a_j + 1$. Considering all such sequences $A$, find the greatest value of $m$.
The positive integers are colored with black and white such that:
- There exists a bijection from the black numbers to the white numbers,
- The sum of three black numbers is a black number, and
- The sum of three white numbers is a white number.
Find the number of possible colorings that satisfies the above conditions.
Let $a_1,a_2,\dots,a_{100}$ be a sequence of integers. Initially, $a_1=1$, $a_2=-1$ and the remaining numbers are $0$. After every second, we perform the following process on the sequence: for $i=1,2,\dots,99$, replace $a_i$ with $a_i+a_{i+1}$, and replace $a_{100}$ with $a_{100}+a_1$. (All of this is done simultaneously, so each new term is the sum of two terms of the sequence from before any replacements.) Show that for any integer $M$, there is some index $i$ and some time $t$ for which $|a_i|>M$ at time $t$.
Find all $f : \mathbb{N} \to \mathbb{N} $ such that $f(a) + f(b)$ divides $2(a + b - 1)$ for all $a, b \in \mathbb{N}$.
Remark: $\mathbb{N} = \{ 1, 2, 3, \ldots \} $ denotes the set of the positive integers.
For a positive integer $n$ we denote by $s(n)$ the sum of the digits of $n$. Let $P(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$ be a polynomial, where $n \geqslant 2$ and $a_i$ is a positive integer for all $0 \leqslant i \leqslant n-1$. Could it be the case that, for all positive integers $k$, $s(k)$ and $s(P(k))$ have the same parity?
Let $n \geq 5$ be a given integer. Determine the greatest integer $k$ for which there exists a polygon with $n$ vertices (convex or not, with non-selfintersecting boundary) having $k$ internal right angles.
[i]Proposed by Juozas Juvencijus Macys, Lithuania[/i]
King George has decided to connect the $1680$ islands in his kingdom by bridges. Unfortunately the rebel movement will destroy two bridges after all the bridges have been built, but not two bridges from the same island. What is the minimal number of bridges the King has to build in order to make sure that it is still possible to travel by bridges between any two of the $1680$ islands after the rebel movement has destroyed two bridges?
Let $n \geq 2$ be a natural number. For any two permutations of $(1,2,\cdots,n)$, say $\alpha = (a_1,a_2,\cdots,a_n)$ and $\beta = (b_1,b_2,\cdots,b_n),$ if there exists a natural number $k \leq n$ such that
$$b_i = \begin{cases} a_{k+1-i}, & \text{ }1 \leq i \leq k; \\ a_i, & \text{} k < i \leq n, \end{cases}$$
we call $\alpha$ a friendly permutation of $\beta$.
Prove that it is possible to enumerate all possible permutations of $(1,2,\cdots,n)$ as $P_1,P_2,\cdots,P_m$ such that for all $i = 1,2,\cdots,m$, $P_{i+1}$ is a friendly permutation of $P_i$ where $m = n!$ and $P_{m+1} = P_1$.
Let a complete oriented graph on $n$ points be given. Show that the vertices can be enumerated as $v_1 , v_2 ,\ldots, v_n$ such that $v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n.$
Consider a positive integer $a > 1$. If $a$ is not a perfect square then at the next move we add $3$ to it and if it is a perfect square we take the square root of it. Define the trajectory of a number $a$ as the set obtained by performing this operation on $a$. For example the cardinality of $3$ is $\{3, 6, 9\}$.
Find all $n$ such that the cardinality of $n$ is finite.
The following part problems may attract partial credit.
$\textbf{(a)}$Show that the cardinality of the trajectory of a number cannot be $1$ or $2$.
$\textbf{(b)}$Show that $\{3, 6, 9\}$ is the only trajectory with cardinality $3$.
$\textbf{(c)}$ Show that there for all $k \geq 3$, there exists a number such that the cardinality
of its trajectory is $k$.
$\textbf{(d)}$ Give an example of a number with cardinality of trajectory as infinity.
Let $P(x)$ be a polynomial of degree $n > 1$ with integer coefficients and let $k$ be a positive integer. Consider the polynomial $Q(x) = P(P(\ldots P(P(x)) \ldots ))$, where $P$ occurs $k$ times. Prove that there are at most $n$ integers $t$ such that $Q(t) = t$.
There are $2003$ pieces of candy on a table. Two players alternately make moves. A move consists of eating one candy or half of the candies on the table (the “lesser half” if there are an odd number of candies). At least one candy must be eaten at each move. The loser is the one who eats the last candy. Which player has a winning strategy?