Found problems: 5802
Let $ a_0$, $ a_1$, $ a_2$, $ \ldots$ be a sequence of positive integers such that the greatest common divisor of any two consecutive terms is greater than the preceding term; in symbols, $ \gcd (a_i, a_{i \plus{} 1}) > a_{i \minus{} 1}$. Prove that $ a_n\ge 2^n$ for all $ n\ge 0$.
[i]Proposed by Morteza Saghafian, Iran[/i]
A deck of $n > 1$ cards is given. A positive integer is written on each card. The deck has the property that the arithmetic mean of the numbers on each pair of cards is also the geometric mean of the numbers on some collection of one or more cards.
For which $n$ does it follow that the numbers on the cards are all equal?
[i]Proposed by Oleg Košik, Estonia[/i]
Given a positive integer $k$ show that there exists a prime $p$ such that one can choose distinct integers $a_1,a_2\cdots, a_{k+3} \in \{1, 2, \cdots ,p-1\}$ such that p divides $a_ia_{i+1}a_{i+2}a_{i+3}-i$ for all $i= 1, 2, \cdots, k$.
[i]South Africa [/i]
Let $N$ be the set of positive integers.
Find all the functions $f: N\to N$ with $f (1) = 2$ and such that $max \{f(m)+f(n), m+n\}$ divides $min\{2m+2n,f (m+ n)+1\}$ for all $m, n$ positive integers
Let $n \geq 2$ be a positive integer. Call a sequence $a_1, a_2, \cdots , a_k$ of integers an $n$[i]-chain[/i] if $1 = a_2 < a_ 2 < \cdots < a_k =n$, $a_i$ divides $a_{i+1}$ for all $i$, $1 \leq i \leq k-1$. Let $f(n)$ be the number of $n$[i]-chains[/i] where $n \geq 2$. For example, $f(4) = 2$ corresponds to the $4$-chains $\{1,4\}$ and $\{1,2,4\}$.
Prove that $f(2^m \cdot 3) = 2^{m-1} (m+2)$ for every positive integer $m$.
Two ants are moving along the edges of a convex polyhedron. The route of every ant ends in its starting point, so that one ant does not pass through the same point twice along its way. On every face $F$ of the polyhedron are written the number of edges of $F$ belonging to the route of the first ant and the number of edges of $F$ belonging to the route of the second ant. Is there a polyhedron and a pair of routes described as above, such that only one face contains a pair of distinct numbers?
[i]Proposed by Nikolai Beluhov[/i]
Positive integer $k(\ge 8)$ is given. Prove that if there exists a pair of positive integers $(x,y)$ that satisfies the conditions below, then there exists infinitely many pairs $(x,y)$.
(1) $ $ $x\mid y^2-3, y\mid x^2-2$
(2) $ $ $gcd\left(3x+\frac{2(y^2-3)}{x},2y+\frac{3(x^2-2)}{y}\right)=k$ $ $
Let $n\geq 2$ be an integer. Let $a_{ij}, \ i,j=1,2,\ldots,n$ be $n^2$ positive real numbers satisfying the following conditions:
[list=1]
[*]For all $i=1,\ldots,n$ we have $a_{ii}=1$ and,
[*]For all $j=2,\ldots,n$ the numbers $a_{ij}, \ i=1,\ldots, j-1$ form a permutation of $1/a_{ji}, \ i=1,\ldots, j-1.$
[/list]
Given that $S_i=a_{i1}+\cdots+a_{in}$, determine the maximum value of the sum $1/S_1+\cdots+1/S_n.$
For a positive integer $n$ define $S_n=1!+2!+\ldots +n!$. Prove that there exists an integer $n$ such that $S_n$ has a prime divisor greater than $10^{2012}$.
Consider a $3k \times 3k$ square grid (where $k$ is a positive integer), the cells in the grid are coordinated in terms of columns and rows: Cell $(i, j)$ is at the $i^{\text{th}}$ column from left to right and the $j^{\text{th}}$ row from bottom up. We want to place $4k$ marbles in the cells of the grid, with each cell containing at most one marble, such that
- Each row and each column has at least one marble
- For each marble, there is another marble placed on the same row or column with that marble.
a) Assume $k=1$. Determine the number of ways to place the marbles to satisfy the above conditions (Two ways to place marbles are different if there is a cell $(i, j)$ having a marble placed in one way but not in the other way).
b) Assume $k \geq 1$. Find the largest positive integer $N$ such that if we mark any $N$ cells on the board, there is always a way to place $4k$ marbles satisfying the above conditions such that none of the marbles are placed on any of the marked cells.
For an integer $n \geq 3$, let $\mathcal M$ be the set $\{(x, y) | x, y \in \mathbb Z, 1 \leq x \leq n, 1 \leq y \leq n\}$ of points in the plane.
What is the maximum possible number of points in a subset $S \subseteq \mathcal M$ which does not contain three distinct points being the vertices of a right triangle?
Let $f$ be a function $f: \mathbb{N} \cup \{0\} \mapsto \mathbb{N},$ and satisfies the following conditions:
(1) $f(0) = 0, f(1) = 1,$
(2) $f(n+2) = 23 \cdot f(n+1) + f(n), n = 0,1, \ldots.$
Prove that for any $m \in \mathbb{N}$, there exist a $d \in \mathbb{N}$ such that $m | f(f(n)) \Leftrightarrow d | n.$
Let $ S$ be a set that contains $ n$ elements. Let $ A_{1},A_{2},\cdots,A_{k}$ be $ k$ distinct subsets of $ S$, where $ k\geq 2, |A_{i}| \equal{} a_{i}\geq 1 ( 1\leq i\leq k)$. Prove that the number of subsets of $ S$ that don't contain any $ A_{i} (1\leq i\leq k)$ is greater than or equal to $ 2^n\prod_{i \equal{} 1}^k(1 \minus{} \frac {1}{2^{a_{i}}}).$
A tree with $n\geq 2$ vertices is given. (A tree is a connected graph without cycles.) The vertices of the tree have real numbers $x_1,x_2,\dots,x_n$ associated with them. Each edge is associated with the product of the two numbers corresponding to the vertices it connects. Let $S$ be a sum of number across all edges. Prove that \[\sqrt{n-1}\left(x_1^2+x_2^2+\dots+x_n^2\right)\geq 2S.\]
(Author: V. Dolnikov)
For which positive integers $b > 2$ do there exist infinitely many positive integers $n$ such that $n^2$ divides $b^n+1$?
[i]Evan Chen and Ankan Bhattacharya[/i]
Let $x_1, x_2, \dots, x_n$ be different real numbers. Prove that
\[\sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}}=\left\{\begin{array}{ll}
0, & \text { if } n \text { is even; } \\
1, & \text { if } n \text { is odd. }
\end{array}\right.\]
In a sequence, $x_1=\frac{1}{2}$ and $x_{n+1}=1-x_1x_2x_3...x_n$ for $n\ge 1$. Prove that $0.99<x_{100}<0.991$.
Fresh translation. This problem may be similar to one of the 9th grade problems.
We call a graph symmetric, if we can put its vertices on the plane such that if the edges are segments, the graph has a reflectional symmetry with respect to a line not passing through its vertices. Find the least value of $K$ such that the edges of every graph with $100$ vertices, can be divided into $K$ symmetric subgraphs.
Let $a_1,a_2,\ldots a_n,k$, and $M$ be positive integers such that
$$\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_n}=k\quad\text{and}\quad a_1a_2\cdots a_n=M.$$
If $M>1$, prove that the polynomial
$$P(x)=M(x+1)^k-(x+a_1)(x+a_2)\cdots (x+a_n)$$
has no positive roots.
Show that $r = 2$ is the largest real number $r$ which satisfies the following condition:
If a sequence $a_1$, $a_2$, $\ldots$ of positive integers fulfills the inequalities
\[a_n \leq a_{n+2} \leq\sqrt{a_n^2+ra_{n+1}}\]
for every positive integer $n$, then there exists a positive integer $M$ such that $a_{n+2} = a_n$ for every $n \geq M$.
Let $m$ circles intersect in points $A$ and $B$. We write numbers using the following algorithm: we write $1$ in points $A$ and $B$, in every midpoint of the open arc $AB$ we write $2$, then between every two numbers written in the midpoint we write their sum and so on repeating $n$ times. Let $r(n,m)$
be the number of appearances of the number $n$ writing all of them on our $m$ circles.
a) Determine $r(n,m)$;
b) For $n=2006$, find the smallest $m$ for which $r(n,m)$ is a perfect square.
Example for half arc: $1-1$;
$1-2-1$;
$1-3-2-3-1$;
$1-4-3-5-2-5-3-4-1$;
$1-5-4-7-3-8-5-7-2-7-5-8-3-7-4-5-1$...
Find the smallest $\lambda \in \mathbb{R}$ such that for all $n \in \mathbb{N}_+$, there exists $x_1, x_2, \ldots, x_n$ satisfying $n = x_1 x_2 \ldots x_{2023}$, where $x_i$ is either a prime or a positive integer not exceeding $n^\lambda$ for all $i \in \left\{ 1,2, \ldots, 2023 \right\}$.
[i]Proposed by Yinghua Ai[/i]
(a) Prove that if $n$ is a integer such that $n \geq 4011^2$ then there exists an integer $l$ such that \[ n < l^2 < (1 + \frac{1}{{2005}})n . \]
(b) Find the smallest positive integer $M$ for which whenever an integer $n$ is such that $n \geq M$
then there exists an integer $l$ such that \[ n < l^2 < (1 + \frac{1}{{2005}})n . \]
Let $ G$ be a connected graph with $ n$ vertices and $ m$ edges such that each edge is contained in at least one triangle. Find the minimum value of $ m$.
An infinite triangular lattice is given, such that the distance between any two adjacent points is always equal to $1$.
Points $A$, $B$, and $C$ are chosen on the lattice such that they are the vertices of an equilateral triangle of side length $L$, and the sides of $ABC$ contain no points from the lattice. Prove that, inside triangle $ABC$, there are exactly $\frac{L^2-1}{2}$ points from the lattice.