Found problems: 583
Suppose $a_1, \dots, a_n$ are integers whose greatest common divisor is 1. Let $S$ be a set of integers with the following properties:
(a) For $i=1, \dots, n$, $a_i \in S$.
(b) For $i,j = 1, \dots, n$ (not necessarily distinct), $a_i - a_j \in S$.
(c) For any integers $x,y \in S$, if $x+y \in S$, then $x-y \in S$.
Prove that $S$ must be equal to the set of all integers.
Consider a sequence $(a_k)_{k \ge 1}$ of natural numbers defined as follows: $a_1=a$ and $a_2=b$ with $a,b>1$ and $\gcd(a,b)=1$ and for all $k>0$, $a_{k+2}=a_{k+1}+a_k$. Prove that for all natural numbers $n$ and $k$, $\gcd(a_n,a_{n+k}) <\frac{a_k}{2}$.
Let $ a > b > 1$ be relatively prime positive integers. Define the weight of an integer $ c$, denoted by $ w(c)$ to be the minimal possible value of $ |x| \plus{} |y|$ taken over all pairs of integers $ x$ and $ y$ such that \[ax \plus{} by \equal{} c.\] An integer $ c$ is called a [i]local champion [/i]if $ w(c) \geq w(c \pm a)$ and $ w(c) \geq w(c \pm b)$.
Find all local champions and determine their number.
[i]Proposed by Zoran Sunic, USA[/i]
Let $X_1,X_2,\ldots,X_m$ a numbering of the $m=2^n-1$ non-empty subsets of the set $\{1,2,\ldots,n\}$, $n\geq 2$. We consider the matrix $(a_{ij})_{1\leq i,j\leq m}$, where $a_{ij}=0$, if $X_i \cap X_j = \emptyset$, and $a_{ij}=1$ otherwise. Prove that the determinant $d$ of this matrix does not depend on the way the numbering was done and compute $d$.
In trapezoid $ABCD$, the sum of the lengths of the bases $AB$ and $CD$ is equal to the length of the diagonal $BD$. Let $M$ denote the midpoint of $BC$, and let $E$ denote the reflection of $C$ about the line $DM$. Prove that $\angle AEB=\angle ACD$.
Find all triples $(a,b,c)$ such that $a,b,c$ are integers in the set $\{2000,2001,\ldots,3000\}$ satisfying $a^2+b^2=c^2$ and $\text{gcd}(a,b,c)=1$.
Let $d$ be the greatest common divisor of $2^{30^{10}}-2$ and $2^{30^{45}}-2$. Find the remainder when $d$ is divided by $2013$.
Let $a_i, b_i$ be coprime positive integers for $i = 1, 2, \ldots , k$, and $m$ the least common multiple of $b_1, \ldots , b_k$. Prove that the greatest common divisor of $a_1 \frac{m}{b_1} , \ldots, a_k \frac{m}{b_k}$ equals the greatest common divisor of $a_1, \ldots , a_k.$
Let $x,y,z$ be distinct positive integers such that $(y+z)(z+x)=(x+y)^2$ . Show that \[x^2+y^2>8(x+y)+2(xy+1).\] (Paolo Leonetti)
Let $\mathbb{Z}_{>0}$ denote the set of positive integers. For any positive integer $k$, a function $f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$ is called [i]$k$-good[/i] if $\gcd(f(m) + n, f(n) + m) \le k$ for all $m \neq n$. Find all $k$ such that there exists a $k$-good function.
[i]Proposed by James Rickards, Canada[/i]
[b](a)[/b] Each of Peter and Basil thinks of three positive integers. For each pair of his numbers, Peter writes down the greatest common divisor of the two numbers. For each pair of his numbers, Basil writes down the least common multiple of the two numbers. If both Peter and Basil write down the same three numbers, prove that these three numbers are equal to each other.
[b](b)[/b] Can the analogous result be proved if each of Peter and Basil thinks of four positive integers instead?
The circle $x^2+ y^2 = r^2$ meets the coordinate axis at $A = (r,0), B = (-r,0), C = (0,r)$ and $D = (0,-r).$ Let $P = (u,v)$ and $Q = (-u,v)$ be two points on the circumference of the circle. Let $N$ be the point of intersection of $PQ$ and the $y$-axis, and $M$ be the foot of the perpendicular drawn from $P$ to the $x$-axis. If $r^2$ is odd, $u = p^m > q^n = v,$ where $p$ and $q$ are prime numbers and $m$ and $n$ are natural numbers, show that
\[ |AM| = 1, |BM| = 9, |DN| = 8, |PQ| = 8. \]
Let $a, b, c$ be distinct positive integers with sum $547$ and let $d$ be the greatest common divisor of the three numbers $ab+1, bc+1, ca+1$. Find the maximal possible value of $d$.
Find all real solutions of the following set of equations:
\[72x^3+4xy^2=11y^3\]
\[27x^5-45x^4y-10x^2y^3=\frac{-143}{32}y^5\]
A finite arithmetic progression of positive integers $a_1,a_2,\ldots,a_n$ satisfies the condition that for all $1\leq i<j\leq n$, the number of positive divisors of $\gcd\left(a_i,a_j\right)$ is equal to $j-i$. Find the maximum possible value of $n$.
$\text{(A) }2\qquad\text{(B) }3\qquad\text{(C) }4\qquad\text{(D) }5\qquad\text{(E) }6$
Prove that if a lattice triangle has no lattice points on its boundary in addition to its vertices, and one point in its interior, then this interior point is its center of gravity.
Find all triples $(a, b, c)$ of natural numbers such that the sets
$$\{ gcd (a, b), gcd(b, c), gcd(c, a), lcm (a, b), lcm (b, c), lcm (c, a)\}$$ and
$$\{2, 3, 5, 30, 60\}$$
are the same.
Remark: For example, the sets $\{1, 2013\}$ and $\{1, 1, 2013\}$ are equal.
Determine all integers $m\ge2$ for which there exists an integer $n\ge1$ with
$\gcd(m,n)=d$ and $\gcd(m,4n+1)=1$.
[i]Proposed by Gerhard Woeginger, Austria[/i]
$m, n$ are relatively prime. We have three jugs which contain $m$, $n$ and $m+n$ liters. Initially the largest jug is full of water. Show that for any $k$ in $\{1, 2, ... , m+n\}$ we can get exactly $k$ liters into one of the jugs.
For a finite set $A$ of positive integers, a partition of $A$ into two disjoint nonempty subsets $A_1$ and $A_2$ is $\textit{good}$ if the least common multiple of the elements in $A_1$ is equal to the greatest common divisor of the elements in $A_2$. Determine the minimum value of $n$ such that there exists a set of $n$ positive integers with exactly $2015$ good partitions.
Find all positive integers $x,y,z$ and $t$ such that $2^x3^y+5^z=7^t$.
Let $s_1, s_2, s_3, \dots$ be an infinite, nonconstant sequence of rational numbers, meaning it is not the case that $s_1 = s_2 = s_3 = \dots.$ Suppose that $t_1, t_2, t_3, \dots$ is also an infinite, nonconstant sequence of rational numbers with the property that $(s_i - s_j)(t_i - t_j)$ is an integer for all $i$ and $j$. Prove that there exists a rational number $r$ such that $(s_i - s_j)r$ and $(t_i - t_j)/r$ are integers for all $i$ and $j$.
Consider a regular polygon with 2007 vertices. The natural numbers $ 1,2, \ldots, 4014$ shall be distributed across the vertices and edge midpoints such that for each side the sum of its three numbers (two end points, one side center) has the same value. Show that such an assignment is possible.
Suppose that $ ABCD$ is a cyclic quadrilateral and $ CD\equal{}DA$. Points $ E$ and $ F$ belong to the segments $ AB$ and $ BC$ respectively, and $ \angle ADC\equal{}2\angle EDF$. Segments $ DK$ and $ DM$ are height and median of triangle $ DEF$, respectively. $ L$ is the point symmetric to $ K$ with respect to $ M$. Prove that the lines $ DM$ and $ BL$ are parallel.
There are many $a\times b$ rectangular cardboard pieces ($a,b\in\mathbb{N}$ such that $a<b$). It is given that by putting such pieces together without overlapping one can make $49\times 51$ rectangle, and $99\times 101$ rectangle. Can one uniquely determine $a,b$ from this?