Found problems: 276
Determine all functions $f: \mathbb{Q} \rightarrow \mathbb{Z} $ satisfying
\[ f \left( \frac{f(x)+a} {b}\right) = f \left( \frac{x+a}{b} \right) \]
for all $x \in \mathbb{Q}$, $a \in \mathbb{Z}$, and $b \in \mathbb{Z}_{>0}$. (Here, $\mathbb{Z}_{>0}$ denotes the set of positive integers.)
Natural number $n>1$ is given. Let $I$ be a set of integers that are relatively prime to $n$. Define the function $f:I=>N$. We call a function $k-periodic$ if for any $a,b$ , $f(a)=f(b)$ whenever $ k|a-b $. We know that $f$ is $n-periodic$. Prove that minimal period of $f$ divides all other periods.
Example: if $n=6$ and $f(1)=f(5)$ then minimal period is 1, if $f(1)$ is not equal to $f(5)$ then minimal period is 3.
Let $n$ be an arbitrary positive integer.
(a) For every positive integers $a$ and $b$, show that $gcd(n^a + 1, n^b + 1) \le n^{gcd(a,b)} + 1$.
(b) Show that there exist infinitely many composite pairs ($a, b)$, such that each of them is not a multiply of the other number and equality holds in (a).
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 $n$ and $m$ be positive integers in the range $[1, 10^{10}]$. Let $R$ be the rectangle with corners at $(0, 0), (n, 0), (n, m), (0, m)$ in the coordinate plane. A simple non-self-intersecting quadrilateral with vertices at integer coordinates is called [i]far-reaching[/i] if each of its vertices lie on or inside $R$, but each side of $R$ contains at least one vertex of the quadrilateral. Show that there is a far-reaching quadrilateral with area at most $10^6$.
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 $O=(0,0)$ be the origin of the $xy$-plane. We say a lattice triangle $ABC$ is [i]marine[/i] if it has centroid $O$ and area $\tfrac{3}{2}$.
Let $P$ be any point in the plane which is not a lattice point. Prove that $P$ lies in the interior of some marine triangle if and only if the line segment $\overline{OP}$ does not pass through any lattice points besides $O$.
(A [i]lattice point[/i] is a point whose $x$-coordinate and $y$-coordinate are both integers. A [i]lattice triangle[/i] is a triangle whose vertices are lattice points.)
Functions $f,g:\mathbb{Z}\to\mathbb{Z}$ satisfy $$f(g(x)+y)=g(f(y)+x)$$ for any integers $x,y$. If $f$ is bounded, prove that $g$ is periodic.
Let $S$ be a set of integers (not necessarily positive) such that
(a) there exist $a,b \in S$ with $\gcd(a,b)=\gcd(a-2,b-2)=1$;
(b) if $x$ and $y$ are elements of $S$ (possibly equal), then $x^2-y$ also belongs to $S$.
Prove that $S$ is the set of all integers.
Say a positive integer $n>1$ is $d$-coverable if for each non-empty subset $S\subseteq \{0, 1, \ldots, n-1\}$, there exists a polynomial $P$ with integer coefficients and degree at most $d$ such that $S$ is exactly the set of residues modulo $n$ that $P$ attains as it ranges over the integers. For each $n$, find the smallest $d$ such that $n$ is $d$-coverable, or prove no such $d$ exists.
[i]Proposed by Carl Schildkraut[/i]
Assume that $k$ and $n$ are two positive integers. Prove that there exist positive integers $m_1 , \dots , m_k$ such that \[1+\frac{2^k-1}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_k}\right).\]
[i]Proposed by Japan[/i]
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 $n$ be a positive integer. Let $s: \mathbb N \to \{1, \ldots, n\}$ be a function such that $n$ divides $m-s(m)$ for all positive integers $m$. Let $a_0, a_1, a_2, \ldots$ be a sequence such that $a_0=0$ and \[a_{k}=a_{k-1}+s(k) \text{ for all }k\ge 1.\]
Find all $n$ for which this sequence contains all the residues modulo $(n+1)^2$.
[i]Proposed by N.V. Tejaswi[/i]
Let $a,b,c$ be given positive integers. Prove that there exists some positive integer $N$ such that
\[ a\mid Nbc+b+c,\ b\mid Nca+c+a,\ c\mid Nab+a+b \]
if and only if, denoting $d=\gcd(a,b,c)$ and $a=dx$, $b=dy$, $c=dz$, the positive integers $x,y,z$ are pairwise coprime, and also $\gcd(d,xyz) \mid x+y+z$.
(Dan Schwarz)
There exist $4$ positive integers $a,b,c,d$ such that $abcd \neq 1$ and each pair of them have a GCD of $1$. Two functions $f,g : \mathbb{N} \rightarrow \{0,1\}$ are multiplicative functions such that for each positive integer $n$ we have :
$$f(an+b)=g(cn+d)$$
Prove that at least one of the followings hold.
$i)$ for each positive integer $n$ we have $f(an+b)=g(cn+d)=0$
$ii)$ There exists a positive integer $k$ such that for all $n$ where $(n,k)=1$ we have $g(n)=f(n)=1$
(Function $f$ is multiplicative if for any natural numbers $a,b$ we have $f(ab)=f(a)f(b)$)
Proposed by [i]Navid Safaii[/i]
Let $P$ be a polynomial. Suppose that there exists a rational $q$ such that $P(m)=q^n$ for infinitely many integers $(m,n)$. Prove that $P(x)=c\cdot Q(x)^k$ for some integer constants $c$ and $k$ and irreducible polynomial $Q$ with rational coefficients.
(Here, a polynomial is $\textit{irreducible}$ if it can't be factored into the product of non-constant polynomials with rational coefficients.)
[i]Jason Lee[/i]
$m$ and $n$ are two nonnegative integers. In the Philosopher's Chess, The chessboard is an infinite grid of identical regular hexagons and a new piece named the Donkey moves on it as follows:
Starting from one of the hexagons, the Donkey moves $m$ cells in one of the $6$ directions, then it turns $60$ degrees clockwise and after that moves $n$ cells in this new direction until it reaches it's final cell.
At most how many cells are in the Philosopher's chessboard such that one cannot go from anyone of them to the other with a finite number of movements of the Donkey?
[i]Proposed by Shayan Dashmiz[/i]
Given a function $f$ for which
\[f(x)=f(398-x)=f(2158-x)=f(3214-x) \]holds for all real $x,$ what is the largest number of different values that can appear in the list $f(0),f(1),f(2),\ldots,f(999)?$
Do there exists many infinitely points like $(x_1,y_1),(x_2,y_2),...$ such that for any sequences like {$b_1,b_2,...$} of real numbers there exists a polynomial $P(x,y)\in R[x,y]$ such that we have for all $i$ :
$P(x_{i},y_{i})=b_{i}$
We have a number $n$ for which we can find 5 consecutive numbers, none of which is divisible by $n$, but their product is.
Show that we can find 4 consecutive numbers, none of which is divisible by $n$, but their product is.
Let $P(x)$ be a nonconstant complex coefficient polynomial and let $Q(x,y)=P(x)-P(y).$ Suppose that polynomial $Q(x,y)$ has exactly $k$ linear factors unproportional two by tow (without counting repetitons). Let $R(x,y)$ be factor of $Q(x,y)$ of degree strictly smaller than $k$. Prove that $R(x,y)$ is a product of linear polynomials.
[b]Note: [/b] The [i]degree[/i] of nontrivial polynomial $\sum_{m}\sum_{n}c_{m,n}x^{m}y^{n}$ is the maximum of $m+n$ along all nonzero coefficients $c_{m,n}.$ Two polynomials are [i]proportional[/i] if one of them is the other times a complex constant.
[i]Proposed by Navid Safaie[/i]
Suppose $m$ and $n$ are relatively prime positive integers. A regular $m$-gon and a regular
$n$-gon are inscribed in a circle. Let $d$ be the minimum distance in degrees (of the arc along
the circle) between a vertex of the $m$-gon and a vertex of the $n$-gon. What is the maximum
possible value of $d$?
$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$
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 $n$ be an integer with $n \ge 2$. Show that $n$ does not divide $2^{n}-1$.