Found problems: 276
Let $\mathbb{N}=\{1, 2, 3, \dots\}$ be the set of all positive integers. Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that for any positive integers $a$ and $b$, the following two conditions hold:
(1) $f(ab) = f(a)f(b)$, and
(2) at least two of the numbers $f(a)$, $f(b)$, and $f(a+b)$ are equal.
Prove that for any polynomial $P$ with real coefficients, and for any positive integer $n$, there exists a polynomial $Q$ with real coefficients such that $P(x)^2 +Q(x)^2$ is divisible by $(1+x^2)^n$.
Let $a,b$ be integers with $0<a<b$. A set $\{x,y,z\}$ of non-negative integers is [i]olympic[/i] if $x<y<z$ and if $\{z-y,y-x\}=\{a,b\}$. Show that the set of all non-negative integers is the union of pairwise disjoint olympic sets.
Let $a(n)$ be the sequence defined by $a(1)=2$ and $a(n+1)=(a(n))^{n+1}-1$ for each integer $n\geq 1$. Suppose that $p>2$ is a prime and $k$ is a positive integer. Prove that some term of the sequence $a(n)$ is divisible by $p^k$.
[i]Proposed by John Berman[/i]
The prime number $p$ and a positive integer $k$ are given. Assume that $P(x)\in \mathbb Z[X]$ is a polynomial with coefficients in the set $\{0,1,\cdots,p-1\}$ with least degree which satisfies the following property: There exists a permutaion of numbers $1,2,\cdots,p-1$ around a circle such that for any $k$ consecutive numbers $a_1,a_2,\cdots,a_k$ one has
$$
p | P(a_1)+P(a_2)+\cdots+ P(a_k).
$$
Prove that $P(x)$ is of the form $ax^d+b$.
Proposed by [i]Yahya Motevassel[/i]
Let $p{}$ and $q{}$ be two coprime positive integers. A frog hops along the integer line so that on every hop it moves either $p{}$ units to the right or $q{}$ units to the left. Eventually, the frog returns to the initial point. Prove that for every positive integer $d{}$ with $d < p + q$ there are two numbers visited by the frog which differ just by $d{}$.
[i]Nikolay Belukhov[/i]
Let $ f: \mathbb{R}\to\mathbb{N}$ be a function which satisfies $ f\left(x \plus{} \dfrac{1}{f(y)}\right) \equal{} f\left(y \plus{} \dfrac{1}{f(x)}\right)$ for all $ x$, $ y\in\mathbb{R}$. Prove that there is a positive integer which is not a value of $ f$.
[i]Proposed by Žymantas Darbėnas (Zymantas Darbenas), Lithuania[/i]
Let $m,n$ be naturals satisfying $n \geq m \geq 2$ and let $S$ be a set consisting of $n$ naturals. Prove that $S$ has at least $2^{n-m+1}$ distinct subsets, each whose sum is divisible by $m$. (The zero set counts as a subset).
For some positive integer $n,$ Elmo writes down the equation
\[x_1+x_2+\dots+x_n=x_1+x_2+\dots+x_n.\]
Elmo inserts at least one $f$ to the left side of the equation and adds parentheses to create a valid functional equation. For example, if $n=3,$ Elmo could have created the equation
\[f(x_1+f(f(x_2)+x_3))=x_1+x_2+x_3.\]
Cookie Monster comes up with a function $f: \mathbb{Q}\to\mathbb{Q}$ which is a solution to Elmo's functional equation. (In other words, Elmo's equation is satisfied for all choices of $x_1,\dots,x_n\in\mathbb{Q})$. Is it possible that there is no integer $k$ (possibly depending on $f$) such that $f^k(x)=x$ for all $x$?
[i]Srinivas Arun[/i]
In triangle \( ABC \), let \( I \) be the \( A \)-excenter. Points \( X \) and \( Y \) are placed on line \( BC \) such that \( B \) is between \( X \) and \( C \), and \( C \) is between \( Y \) and \( B \). Moreover, \( B \) and \( C \) are the contact points of \( BC \) with the \( A \)-excircle of triangles \( BAY \) and \( AXC \), respectively. Let \( J \) be the \( A \)-excenter of triangle \( AXY \), and let \( H' \) be the reflection of the orthocenter of triangle \( ABC \) with respect to its circumcenter. Prove that \( I \), \( J \), and \( H' \) are collinear.
Proposed by Ali Nazarboland
The denominators of two irreducible fractions are 600 and 700. Find the minimum value of the denominator of their sum (written as an irreducible fraction).
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 us consider a simle graph with vertex set $ V$. All ordered pair $ (a,b)$ of integers with $ gcd(a,b) \equal{} 1$, are elements of V.
$ (a,b)$ is connected to $ (a,b \plus{} kab)$ by an edge and to $ (a \plus{} kab,b)$ by another edge for all integer k.
Prove that for all $ (a,b)\in V$, there exists a path fromm $ (1,1)$ to $ (a,b)$.
Let $P(x)$ be a polynomial with rational coefficients such that $P(n)$ is integer for all
integers $n$. Moreover: $gcd(P(1), \ldots , P(k), \ldots) = 1$. Prove that every integer $k$ can be represented
in infinitely many ways of the form
$\pm P(1) \pm P(2) \pm \ldots \pm P(m)$,
for some positive integer $m$ and certain choices of $\pm$.
Let $\tfrac{a}{b}$ be a fraction such that $a$ and $b$ are positive integers and the first three digits of its decimal expansion are $527$. What is the smallest possible value of $a+b?$
A set $A\subset \mathbb{Z}$ is "padre" if whenever $x,y \in A$ with $x\leq y$ then also $2y -x \in A$. Prove that if $A$ is "padre", $0,a,b \in A$ with $0< a < b$ and $d = g.c.d(a,b)$ then \[a+b-3d, a+b-2d \in A.\]
Let $n > 3$ be a positive integer. Find all integers $k$ such that $1 \le k \le n$ and for
which the following property holds:
If $x_1, . . . , x_n$ are $n$ real numbers such that $x_i + x_{i + 1} + ... + x_{i + k - 1} = 0$ for all integers $i > 1$ (indexes are taken modulo $n$), then $x_1 = . . . = x_n = 0$.
Proposed by [i]Vincent Jugé and Théo Lenoir, France[/i]
Let $p$ be a prime number, $n$ a natural number which is not divisible by $p$, and $\mathbb{K}$ is a finite field, with $char(K) = p, |K| = p^n, 1_{\mathbb{K}}$ unity element and $\widehat{0} = 0_{\mathbb{K}}.$ For every $m \in \mathbb{N}^{*}$ we note
$ \widehat{m} = \underbrace{1_{\mathbb{K}} + 1_{\mathbb{K}} + \ldots + 1_{\mathbb{K}}}_{m \text{ times}} $ and define the polynomial
\[
f_m = \sum_{k = 0}^{m} (-1)^{m - k} \widehat{\binom{m}{k}} X^{p^k} \in \mathbb{K}[X].
\]
a) Show that roots of $f_1$ are $ \left\{ \widehat{k} | k \in \{0,1,2, \ldots , p - 1 \} \right\}$.
b) Let $m \in \mathbb{N}^{*}.$ Determine the set of roots from $\mathbb{K}$ of polynomial $f_{m}.$
Let $T$ the set of the infinite sequences of integers. For two given elements in $T$:
$(a_{1},a_{2},a_{3},...)$ and $(b_{1},b_{2},b_{3},...)$, define the sum
$(a_{1},a_{2},a_{3},...)+(b_{1},b_{2},b_{3},...)=(a_{1}+b_{1},a_{2}+b_{2},a_{3}+b_{3},...)$.
Let $f: T\rightarrow$ $\mathbb{Z}$ a function such that:
i) If $x\in T$ has exactly one of your terms equal $1$ and all the others equal $0$, then $f(x)=0$.
ii)$f(x+y)=f(x)+f(y)$, for all $x,y\in T$.
Prove that $f(x)=0$ for all $x\in T$
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.
Let $f\in\mathbb{Z}[X]$ be an irreducible polynomial over the ring of integer polynomials, such that $|f(0)|$ is not a perfect square. Prove that if the leading coefficient of $f$ is 1 (the coefficient of the term having the highest degree in $f$) then $f(X^2)$ is also irreducible in the ring of integer polynomials.
[i]Mihai Piticari[/i]
Given a natural $n>1$ and its prime fatorization $n=p_1^{\alpha 1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$, its [i]false derived[/i] is defined by $$f(n)=\alpha_1p_1^{\alpha_1-1}\alpha_2p_2^{\alpha_2-1}...\alpha_kp_k^{\alpha_k-1}.$$ Prove that there exist infinitely many naturals $n$ such that $f(n)=f(n-1)+1$.
Find all functions $f:\mathbb{Z}\rightarrow \mathbb{Z}$ such that for all integers $x$, $y$, $$f(x-f(y))=f(f(y))+f(x-2y)$$
[i]Proposed by Ivan Chan Kai Chin[/i]
Let $ \mathcal G$ be the set of all finite groups with at least two elements.
a) Prove that if $ G\in \mathcal G$, then the number of morphisms $ f: G\to G$ is at most $ \sqrt [p]{n^n}$, where $ p$ is the largest prime divisor of $ n$, and $ n$ is the number of elements in $ G$.
b) Find all the groups in $ \mathcal G$ for which the inequality at point a) is an equality.
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]