Found problems: 5802
Find all function $f:\mathbb{N}^*\rightarrow \mathbb{N}^*$ that satisfy:
$(f(1))^3+(f(2))^3+...+(f(n))^3=(f(1)+f(2)+...+f(n))^2$
Let $ d_n$ be the determinant of the $ n\times n$ matrix whose entries, from left to right and then from top to bottom, are $ \cos 1,\cos 2,\dots,\cos n^2.$ (For example, $ d_3 \equal{} \begin{vmatrix}\cos 1 & \cos2 & \cos3 \\
\cos4 & \cos5 & \cos 6 \\
\cos7 & \cos8 & \cos 9\end{vmatrix}.$ The argument of $ \cos$ is always in radians, not degrees.)
Evaluate $ \lim_{n\to\infty}d_n.$
Let $f$ be a polynomial with integer coefficients. Define $$a_1 = f(0)~,~a_2 = f(a_1) = f(f(0))~,$$
and $~a_n = f(a_{n-1})$ for $n \geqslant 3$.
If there exists a natural number $k \geqslant 3$ such that $a_k = 0$, then prove that either $a_1=0$ or $a_2=0$.
Let $f : \{ 1, 2, 3, \dots \} \to \{ 2, 3, \dots \}$ be a function such that $f(m + n) | f(m) + f(n) $ for all pairs $m,n$ of positive integers. Prove that there exists a positive integer $c > 1$ which divides all values of $f$.
Given a set $S$ of integers, an allowed operation consists of the following three steps:
$\bullet$ Choose a positive integer $n$.
$\bullet$ Choose $n+1$ elements $a_0, a_1, \dots, a_n \in S$, not necessarily distinct.
$\bullet$ Add to the set $S$ all the integer roots of the polynomial $a_n x^n + a_{n-1} x^{n-1} + \dots + a_2 x^2 + a_1 x + a_0$.
Beto must choose an initial set $S$ and perform several allowed operations, so that at the end of the process $S$ contains among its elements the integers $1, 2, 3, \dots, 2023, 2024$.
Determine the smallest $k$ for which there exists an initial set $S$ with $k$ elements that allows Beto to achieve his objective.
On the $n\times n$ checker board, several cells were marked in such a way that lower left ($L$) and upper right($R$) cells are not marked and that for any knight-tour from $L$ to $R$, there is at least one marked cell. For which $n>3$, is it possible that there always exists three consective cells going through diagonal for which at least two of them are marked?
Suppose that $(a_n)_{n\geq 1}$ is a sequence of real numbers satisfying $a_{n+1} = \frac{3a_n}{2+a_n}$.
(i) Suppose $0 < a_1 <1$, then prove that the sequence $a_n$ is increasing and hence show that $\lim_{n \to \infty} a_n =1$.
(ii) Suppose $ a_1 >1$, then prove that the sequence $a_n$ is decreasing and hence show that $\lim_{n \to \infty} a_n =1$.
Let $ n$ and $ k$ be positive integers, $ n\geq k$. Prove that the greatest common divisor of the numbers $ \binom{n}{k},\binom{n\plus{}1}{k},\ldots,\binom{n\plus{}k}{k}$ is $ 1$.
In the city of Flensburg there is a single, infinitely long, street with housesnumbered $2, 3, \ldots$. The police in Flensburg is trying to catch a thief who every night moves from the house where she is currently hiding to one of its neighbouring houses.
To taunt the local law enforcement the thief reveals every morning the highest prime divisor of the number of the house she has moved to.
Every Sunday afternoon the police searches a single house, and they catch the thief if they search the house she is currently occupying. Does the police have a strategy to catch the thief in finite time?
Show that for nonnegative real numbers $a,b$ and integers $n\ge 2$,
\[\frac{a^n+b^n}{2}\ge\left(\frac{a+b}{2}\right)^n\]
When does equality hold?
For each positive integer $k$, let $d(k)$ be the number of positive divisors of $k$ and $\sigma(k)$ be the sum of positive divisors of $k$. Let $\mathbb N$ be the set of all positive integers. Find all functions $f: \mathbb{N} \to \mathbb N$ such that \begin{align*}
f(d(n+1)) &= d(f(n)+1)\quad \text{and} \\
f(\sigma(n+1)) &= \sigma(f(n)+1)
\end{align*}
for all positive integers $n$.
Let $n \ge 2018$ be an integer, and let $a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n$ be pairwise distinct positive integers not exceeding $5n$. Suppose that the sequence
\[ \frac{a_1}{b_1}, \frac{a_2}{b_2}, \dots, \frac{a_n}{b_n} \]
forms an arithmetic progression. Prove that the terms of the sequence are equal.
Let $F_0,F_1,\dots$ be the sequence of Fibonacci numbers, with $F_0=0,F_1=1$, and $F_n=F_{n-1}+F_{n-2}$ for $n \ge 2$. For $m>2$, let $R_m$ be the remainder when the product $\prod_{k=1}^{F_m-1} k^k$ is divided by $F_m$. Prove that $R_m$ is also a Fibonacci number.
Determine all integers $ n\geq 2$ having the following property: for any integers $a_1,a_2,\ldots, a_n$ whose sum is not divisible by $n$, there exists an index $1 \leq i \leq n$ such that none of the numbers $$a_i,a_i+a_{i+1},\ldots,a_i+a_{i+1}+\ldots+a_{i+n-1}$$ is divisible by $n$. Here, we let $a_i=a_{i-n}$ when $i >n$.
[i]Proposed by Warut Suksompong, Thailand[/i]
Let $a$ be a positive integer which is not a perfect square, and consider the equation \[k = \frac{x^2-a}{x^2-y^2}.\] Let $A$ be the set of positive integers $k$ for which the equation admits a solution in $\mathbb Z^2$ with $x>\sqrt{a}$, and let $B$ be the set of positive integers for which the equation admits a solution in $\mathbb Z^2$ with $0\leq x<\sqrt{a}$. Show that $A=B$.
A sequence of integers $a_1,a_2,a_3,\ldots$ is called [i]exact[/i] if $a_n^2-a_m^2=a_{n-m}a_{n+m}$ for any $n>m$. Prove that there exists an exact sequence with $a_1=1,a_2=0$ and determine $a_{2007}$.
There are 60 empty boxes $B_1,\ldots,B_{60}$ in a row on a table and an unlimited supply of pebbles. Given a positive integer $n$, Alice and Bob play the following game.
In the first round, Alice takes $n$ pebbles and distributes them into the 60 boxes as she wishes. Each subsequent round consists of two steps:
(a) Bob chooses an integer $k$ with $1\leq k\leq 59$ and splits the boxes into the two groups $B_1,\ldots,B_k$ and $B_{k+1},\ldots,B_{60}$.
(b) Alice picks one of these two groups, adds one pebble to each box in that group, and removes one pebble from each box in the other group.
Bob wins if, at the end of any round, some box contains no pebbles. Find the smallest $n$ such that Alice can prevent Bob from winning.
[i]Czech Republic[/i]
There are infinitely many people registered on the social network Mugbook. Some pairs of (different) users are registered as friends, but each person has only finitely many friends. Every user has at least one friend. (Friendship is symmetric; that is, if $A$ is a friend of $B$, then $B$ is a friend of $A$.)
Each person is required to designate one of their friends as their best friend. If $A$ designates $B$ as her best friend, then (unfortunately) it does not follow that $B$ necessarily designates $A$ as her best friend. Someone designated as a best friend is called a $1$-best friend. More generally, if $n> 1$ is a positive integer, then a user is an $n$-best friend provided that they have been designated the best friend of someone who is an $(n-1)$-best friend. Someone who is a $k$-best friend for every positive integer $k$ is called popular.
(a) Prove that every popular person is the best friend of a popular person.
(b) Show that if people can have infinitely many friends, then it is possible that a popular person is not the best friend of a popular person.
[i]Romania (Dan Schwarz)[/i]
On a blackboard a positive integer $n_0$ is written. Two players, $A$ and $B$ are playing a game, which respects the following rules:
$-$ acting alternatively per turn, each player deletes the number written on the blackboard $n_k$ and writes instead one number denoted with $n_{k+1}$ from the set $\left\{n_k-1, \dsp \left\lfloor\frac {n_k}3\right\rfloor\right\}$;
$-$ player $A$ starts first deleting $n_0$ and replacing it with $n_1\in\left\{n_0-1, \dsp \left\lfloor\frac {n_0}3\right\rfloor\right\}$;
$-$ the game ends when the number on the table is 0 - and the player who wrote it is the winner.
Find which player has a winning strategy in each of the following cases:
a) $n_0=120$;
b) $n_0=\dsp \frac {3^{2002}-1}2$;
c) $n_0=\dsp \frac{3^{2002}+1}2$.
An ordered pair $(x, y)$ of integers is a primitive point if the greatest common divisor of $x$ and $y$ is $1$. Given a finite set $S$ of primitive points, prove that there exist a positive integer $n$ and integers $a_0, a_1, \ldots , a_n$ such that, for each $(x, y)$ in $S$, we have:
$$a_0x^n + a_1x^{n-1} y + a_2x^{n-2}y^2 + \cdots + a_{n-1}xy^{n-1} + a_ny^n = 1.$$
[i]Proposed by John Berman, United States[/i]
Let $m$ and $n$ be fixed positive integers. Tsvety and Freyja play a game on an infinite grid of unit square cells. Tsvety has secretly written a real number inside of each cell so that the sum of the numbers within every rectangle of size either $m$ by $n$ or $n$ by $m$ is zero. Freyja wants to learn all of these numbers.
One by one, Freyja asks Tsvety about some cell in the grid, and Tsvety truthfully reveals what number is written in it. Freyja wins if, at any point, Freyja can simultaneously deduce the number written in every cell of the entire infinite grid (If this never occurs, Freyja has lost the game and Tsvety wins).
In terms of $m$ and $n$, find the smallest number of questions that Freyja must ask to win, or show that no finite number of questions suffice.
[i]Nikolai Beluhov[/i]
There are 51 senators in a senate. The senate needs to be divided into $n$ committees so that each senator is on one committee. Each senator hates exactly three other senators. (If senator A hates senator B, then senator B does [i]not[/i] necessarily hate senator A.) Find the smallest $n$ such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee.
Let $n$ be a fixed positive integer. The points $A_1$, $A_2$, $\ldots$, $A_{2n}$ are on a straight line. Color each point blue or red according to the following procedure: draw $n$ pairwise disjoint circumferences, each with diameter $A_iA_j$ for some $i \neq j$ and such that every point $A_k$ belongs to exactly one circumference. Points in the same circumference must be of the same color.
Determine the number of ways of coloring these $2n$ points when we vary the $n$ circumferences and the distribution of the colors.
Fix an integer $k>2$. Two players, called Ana and Banana, play the following game of numbers. Initially, some integer $n \ge k$ gets written on the blackboard. Then they take moves in turn, with Ana beginning. A player making a move erases the number $m$ just written on the blackboard and replaces it by some number $m'$ with $k \le m' < m$ that is coprime to $m$. The first player who cannot move anymore loses.
An integer $n \ge k $ is called good if Banana has a winning strategy when the initial number is $n$, and bad otherwise.
Consider two integers $n,n' \ge k$ with the property that each prime number $p \le k$ divides $n$ if and only if it divides $n'$. Prove that either both $n$ and $n'$ are good or both are bad.
Each integer in $\{1, 2, 3, . . . , 2020\}$ is coloured in such a way that, for all positive integers $a$ and $b$
such that $a + b \leq 2020$, the numbers $a$, $b$ and $a + b$ are not coloured with three different colours.
Determine the maximum number of colours that can be used.
[i]Massimiliano Foschi, Italy[/i]