Found problems: 276
Let $ n$ be a natural number such that $ n \equal{} a^2 \plus{} b^2 \plus{}c^2$ for some natural numbers $ a,b,c$. Prove that
\[ 9n \equal{} (p_1a\plus{}q_1b\plus{}r_1c)^2 \plus{} (p_2a\plus{}q_2b\plus{}r_2c)^2 \plus{} (p_3a\plus{}q_3b\plus{}r_3c)^2\]
where $ p_j$'s , $ q_j$'s , $ r_j$'s are all [b]nonzero[/b] integers. Further, if $ 3$ does [b]not[/b] divide at least one of $ a,b,c,$ prove that $ 9n$ can be expressed in the form $ x^2\plus{}y^2\plus{}z^2$, where $ x,y,z$ are natural numbers [b]none[/b] of which is divisible by $ 3$.
Consider a directed graph $G$ with $n$ vertices, where $1$-cycles and $2$-cycles are permitted. For any set $S$ of vertices, let $N^{+}(S)$ denote the out-neighborhood of $S$ (i.e. set of successors of $S$), and define $(N^{+})^k(S)=N^{+}((N^{+})^{k-1}(S))$ for $k\ge2$.
For fixed $n$, let $f(n)$ denote the maximum possible number of distinct sets of vertices in $\{(N^{+})^k(X)\}_{k=1}^{\infty}$, where $X$ is some subset of $V(G)$. Show that there exists $n>2012$ such that $f(n)<1.0001^n$.
[i]Linus Hamilton.[/i]
Can every positive rational number $q$ be written as
$$\frac{a^{2021} + b^{2023}}{c^{2022} + d^{2024}},$$
where $a, b, c, d$ are all positive integers?
[i]Proposed by Dominic Yeo, UK[/i]
Find all polynomials $ p$ of one variable with integer coefficients such that if $ a$ and $ b$ are natural numbers such that $ a \plus{} b$ is a perfect square, then $ p\left(a\right) \plus{} p\left(b\right)$ is also a perfect square.
Let $ \theta$ be an angle in the interval $ (0,\pi/2)$. Given that $ \cos \theta$ is irrational, and that $ \cos k \theta$ and $ \cos[(k \plus{} 1)\theta ]$ are both rational for some positive integer $ k$, show that $ \theta \equal{} \pi/6$.
In the coordinate plane consider the set $ S$ of all points with integer coordinates. For a positive integer $ k$, two distinct points $A$, $ B\in S$ will be called $ k$-[i]friends[/i] if there is a point $ C\in S$ such that the area of the triangle $ ABC$ is equal to $ k$. A set $ T\subset S$ will be called $ k$-[i]clique[/i] if every two points in $ T$ are $ k$-friends. Find the least positive integer $ k$ for which there exits a $ k$-clique with more than 200 elements.
[i]Proposed by Jorge Tipe, Peru[/i]
Let \( A \) and \( B \) be positive integers, and let \( S \) be a set of positive integers with the following properties:
(1) For every non-negative integer $k$, $\text{ } A^k \in S$;
(2) If a positive integer $ n \in S$, then every positive divisor of $ n$ is in $S$;
(3) If $m ,n \in S$ and $m,n$ are coprime, then $mn \in S$;
(4) If $n \in S$, then $An + B \in S$.
Prove that all positive integers coprime to \( B \) are in \( S \).
Find all surjective functions $ f: \mathbb{N} \to \mathbb{N}$ such that for every $ m,n \in \mathbb{N}$ and every prime $ p,$ the number $ f(m + n)$ is divisible by $ p$ if and only if $ f(m) + f(n)$ is divisible by $ p$.
[i]Author: Mohsen Jamaali and Nima Ahmadi Pour Anari, Iran[/i]
Let $k,n\ge 1$ be relatively prime integers. All positive integers not greater than $k+n$ are written in some order on the blackboard. We can swap two numbers that differ by $k$ or $n$ as many times as we want. Prove that it is possible to obtain the order $1,2,\dots,k+n-1, k+n$.
The ratio of prime numbers $p$ and $q$ does not exceed 2 ($p\ne q$).
Prove that there are two consecutive positive integers such that
the largest prime divisor of one of them is $p$ and that of the other is $q$.
Let $P(x)$ and $Q(x)$ be arbitrary polynomials with real coefficients, and let $d$ be the degree of $P(x)$. Assume that $P(x)$ is not the zero polynomial. Prove that there exist polynomials $A(x)$ and $B(x)$ such that:
(i) both $A$ and $B$ have degree at most $d/2$
(ii) at most one of $A$ and $B$ is the zero polynomial.
(iii) $\frac{A(x)+Q(x)B(x)}{P(x)}$ is a polynomial with real coefficients. That is, there is some polynomial $C(x)$ with real coefficients such that $A(x)+Q(x)B(x)=P(x)C(x)$.
For $ a_i \in \mathbb{Z}^ \plus{}$, $ i \equal{} 1, \ldots, k$, and $ n \equal{} \sum^k_{i \equal{} 1} a_i$, let $ d \equal{} \gcd(a_1, \ldots, a_k)$ denote the greatest common divisor of $ a_1, \ldots, a_k$.
Prove that $ \frac {d} {n} \cdot \frac {n!}{\prod\limits^k_{i \equal{} 1} (a_i!)}$ is an integer.
[i]Dan Schwarz, Romania[/i]
Let $ a, b, c$ be integers satisfying $ 0 < a < c \minus{} 1$ and $ 1 < b < c$. For each $ k$, $ 0\leq k \leq a$, Let $ r_k,0 \leq r_k < c$
be the remainder of $ kb$ when divided by $ c$. Prove that the two sets $ \{r_0, r_1, r_2, \cdots , r_a\}$ and $ \{0, 1, 2, \cdots , a\}$ are different.
Prove that for every square-free integer $n>1$, there exists a prime number $p$ and an integer $m$ satisfying
\[ p \mid n \quad \text{and} \quad n \mid p^2+p\cdot m^p. \]
For each positive integer $ n$, let $ c(n)$ be the largest real number such that
\[ c(n) \le \left| \frac {f(a) \minus{} f(b)}{a \minus{} b}\right|\]
for all triples $ (f, a, b)$ such that
--$ f$ is a polynomial of degree $ n$ taking integers to integers, and
--$ a, b$ are integers with $ f(a) \neq f(b)$.
Find $ c(n)$.
[i]Shaunak Kishore.[/i]
Let $p$ be an odd prime number and $\mathbb{Z}_{>0}$ be the set of positive integers. Suppose that a function $f:\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}\to\{0,1\}$ satisfies the following properties:
[list]
[*] $f(1,1)=0$.
[*] $f(a,b)+f(b,a)=1$ for any pair of relatively prime positive integers $(a,b)$ not both equal to 1;
[*] $f(a+b,b)=f(a,b)$ for any pair of relatively prime positive integers $(a,b)$.
[/list]
Prove that
$$\sum_{n=1}^{p-1}f(n^2,p) \geqslant \sqrt{2p}-2.$$
Call admissible a set $A$ of integers that has the following property:
If $x,y \in A$ (possibly $x=y$) then $x^2+kxy+y^2 \in A$ for every integer $k$.
Determine all pairs $m,n$ of nonzero integers such that the only admissible set containing both $m$ and $n$ is the set of all integers.
[i]Proposed by Warut Suksompong, Thailand[/i]
Find the product of all values of $d$ such that $x^{3} +2x^{2} +3x +4 = 0$ and $x^{2} +dx +3 = 0$ have a common root.
Prove that for any positive integers $x, y, z$ with $xy-z^2 = 1$ one can find non-negative integers $a, b, c, d$ such that $x = a^2 + b^2, y = c^2 + d^2, z = ac + bd$.
Set $z = (2q)!$ to deduce that for any prime number $p = 4q + 1$, $p$ can be represented as the sum of squares of two integers.
Given complex numbers $a,b,c$, we have that $|az^2 + bz +c| \leq 1$ holds true for any complex number $z, |z| \leq 1$. Find the maximum value of $|bc|$.
$n$ being a given integer, find all functions $f\colon \mathbb{Z} \to \mathbb{Z}$, such that for all integers $x,y$ we have $f\left( {x + y + f(y)} \right) = f(x) + ny$.
Suppose that $n\ge2$ and $a_1,a_2,...,a_n$ are natural numbers that $ (a_1,a_2,...,a_n)=1$. Find all strictly increasing function $f: \mathbb{Z} \to \mathbb{R} $ that:
$$ \forall x_1,x_2,...,x_n \in \mathbb{Z} : f(\sum_{i=1}^{n} {x_ia_i}) = \sum_{i=1}^{n} {f(x_ia_i})$$
[i]Proposed by Navid Safaei and Ali Mirzaei [/i]
A [i]word[/i] is a finite sequence of letters from some alphabet. A word is [i]repetitive[/i] if it is a concatenation of at least two identical subwords (for example, $ababab$ and $abcabc$ are repetitive, but $ababa$ and $aabb$ are not). Prove that if a word has the property that swapping any two adjacent letters makes the word repetitive, then all its letters are identical. (Note that one may swap two adjacent identical letters, leaving a word unchanged.)
[i]Romania (Dan Schwarz)[/i]
Determine which integers $n > 1$ have the property that there exists an infinite sequence $a_1, a_2, a_3, \ldots$ of nonzero integers such that the equality \[a_k+2a_{2k}+\ldots+na_{nk}=0\]holds for every positive integer $k$.
Let $p$ be a prime number. Let $\mathbb F_p$ denote the integers modulo $p$, and let $\mathbb F_p[x]$ be the set of polynomials with coefficients in $\mathbb F_p$. Define $\Psi : \mathbb F_p[x] \to \mathbb F_p[x]$ by \[ \Psi\left( \sum_{i=0}^n a_i x^i \right) = \sum_{i=0}^n a_i x^{p^i}. \] Prove that for nonzero polynomials $F,G \in \mathbb F_p[x]$, \[ \Psi(\gcd(F,G)) = \gcd(\Psi(F), \Psi(G)). \] Here, a polynomial $Q$ divides $P$ if there exists $R \in \mathbb F_p[x]$ such that $P(x) - Q(x) R(x)$ is the polynomial with all coefficients $0$ (with all addition and multiplication in the coefficients taken modulo $p$), and the gcd of two polynomials is the highest degree polynomial with leading coefficient $1$ which divides both of them. A non-zero polynomial is a polynomial with not all coefficients $0$. As an example of multiplication, $(x+1)(x+2)(x+3) = x^3+x^2+x+1$ in $\mathbb F_5[x]$.
[i]Proposed by Mark Sellke[/i]