Found problems: 800
Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a,b,c,d \in S$ with $\gcd(a,b) \neq \gcd(c,d)$. Prove that there exist three pairwise distinct $x,y,z \in S$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$.
For any finite sets $X$ and $Y$ of positive integers, denote by $f_X(k)$ the $k^{\text{th}}$ smallest positive integer not in $X$, and let $$X*Y=X\cup \{ f_X(y):y\in Y\}.$$Let $A$ be a set of $a>0$ positive integers and let $B$ be a set of $b>0$ positive integers. Prove that if $A*B=B*A$, then $$\underbrace{A*(A*\cdots (A*(A*A))\cdots )}_{\text{ A appears $b$ times}}=\underbrace{B*(B*\cdots (B*(B*B))\cdots )}_{\text{ B appears $a$ times}}.$$
[i]Proposed by Alex Zhai, United States[/i]
Prove that for any natural numbers$a,b$ there exist infinity many prime numbers $p$ so that $Ord_p(a)=Ord_p(b)$(Proving that there exist infinity prime numbers $p$ so that $Ord_p(a) \ge Ord_p(b)$ will get a partial mark)
Let $\sqrt 3 = 1.b_1b_2b_3 \dots _{(2)}$ be the binary representation of $\sqrt 3$. Prove that for any positive integer $n$, at least one of the digits $b_n$, $b_{n+1}$, $\dots$, $b_{2n}$ equals $1$.
Let $N \geq 2$ be an integer, and let $\mathbf a$ $= (a_1, \ldots, a_N)$ and $\mathbf b$ $= (b_1, \ldots b_N)$ be sequences of non-negative integers. For each integer $i \not \in \{1, \ldots, N\}$, let $a_i = a_k$ and $b_i = b_k$, where $k \in \{1, \ldots, N\}$ is the integer such that $i-k$ is divisible by $n$. We say $\mathbf a$ is $\mathbf b$-[i]harmonic[/i] if each $a_i$ equals the following arithmetic mean: \[a_i = \frac{1}{2b_i+1} \sum_{s=-b_i}^{b_i} a_{i+s}.\]
Suppose that neither $\mathbf a $ nor $\mathbf b$ is a constant sequence, and that both $\mathbf a$ is $\mathbf b$-[i]harmonic[/i] and $\mathbf b$ is $\mathbf a$-[i]harmonic[/i].
Prove that at least $N+1$ of the numbers $a_1, \ldots, a_N,b_1, \ldots, b_N$ are zero.
A rectangle $ D$ is partitioned in several ($ \ge2$) rectangles with sides parallel to those of $ D$. Given that any line parallel to one of the sides of $ D$, and having common points with the interior of $ D$, also has common interior points with the interior of at least one rectangle of the partition; prove that there is at least one rectangle of the partition having no common points with $ D$'s boundary.
[i]Author: Kei Irie, Japan[/i]
Let $n \geq 4$ be an integer. Find all positive real solutions to the following system of $2n$ equations:
\begin{align*}
a_{1} &=\frac{1}{a_{2 n}}+\frac{1}{a_{2}}, & a_{2}&=a_{1}+a_{3}, \\
a_{3}&=\frac{1}{a_{2}}+\frac{1}{a_{4}}, & a_{4}&=a_{3}+a_{5}, \\
a_{5}&=\frac{1}{a_{4}}+\frac{1}{a_{6}}, & a_{6}&=a_{5}+a_{7} \\
&\vdots & &\vdots \\
a_{2 n-1}&=\frac{1}{a_{2 n-2}}+\frac{1}{a_{2 n}}, & a_{2 n}&=a_{2 n-1}+a_{1}
\end{align*}
Given a prime $p$, prove that the sum $\sum_{k=1}^{\lfloor \frac{q}{p} \rfloor}{k^{p-1}}$ is not divisible by $q$ for all but finitely many primes $q$.
Can the number obtained by writing the numbers from 1 to $n$ in order ($n > 1$) be the same when read left-to-right and right-to-left?
[i]N. Agakhanov[/i]
Let $P$ be a point in the plane of triangle $ABC$ such that the segments $PA$, $PB$, and $PC$ are the sides of an obtuse triangle. Assume that in this triangle the obtuse angle opposes the side congruent to $PA$. Prove that $\angle BAC$ is acute.
Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function, and let $f^m$ be $f$ applied $m$ times. Suppose that for every $n \in \mathbb{N}$ there exists a $k \in \mathbb{N}$ such that $f^{2k}(n)=n+k$, and let $k_n$ be the smallest such $k$. Prove that the sequence $k_1,k_2,\ldots $ is unbounded.
[i]Proposed by Palmer Mebane, United States[/i]
Let $n>1$ be a positive integer. Each cell of an $n\times n$ table contains an integer. Suppose that the following conditions are satisfied:
[list=1]
[*] Each number in the table is congruent to $1$ modulo $n$.
[*] The sum of numbers in any row, as well as the sum of numbers in any column, is congruent to $n$ modulo $n^2$.
[/list]
Let $R_i$ be the product of the numbers in the $i^{\text{th}}$ row, and $C_j$ be the product of the number in the $j^{\text{th}}$ column. Prove that the sums $R_1+\hdots R_n$ and $C_1+\hdots C_n$ are congruent modulo $n^4$.
Let $a_1,a_2,\dots,a_{2023}$ be positive integers such that
[list=disc]
[*] $a_1,a_2,\dots,a_{2023}$ is a permutation of $1,2,\dots,2023$, and
[*] $|a_1-a_2|,|a_2-a_3|,\dots,|a_{2022}-a_{2023}|$ is a permutation of $1,2,\dots,2022$.
[/list]
Prove that $\max(a_1,a_{2023})\ge 507$.
A blackboard contains 68 pairs of nonzero integers. Suppose that for each positive integer $k$ at most one of the pairs $(k, k)$ and $(-k, -k)$ is written on the blackboard. A student erases some of the 136 integers, subject to the condition that no two erased integers may add to 0. The student then scores one point for each of the 68 pairs in which at least one integer is erased. Determine, with proof, the largest number $N$ of points that the student can guarantee to score regardless of which 68 pairs have been written on the board.
We say that a set $S$ of integers is [i]rootiful[/i] if, for any positive integer $n$ and any $a_0, a_1, \cdots, a_n \in S$, all integer roots of the polynomial $a_0+a_1x+\cdots+a_nx^n$ are also in $S$. Find all rootiful sets of integers that contain all numbers of the form $2^a - 2^b$ for positive integers $a$ and $b$.
There are $n$ boxes $A_1, ..., A_n$ with non-negative number of pebbles inside it(so it can be empty). Let $a_n$ be the number of pebbles in the box $A_n$. There are total $3n$ pebbles in the boxes. From now on, Alice plays the following operation.
In each operation, Alice choose one of these boxes which is non-empty. Then she divide this pebbles into $n$ group such that difference of number of pebbles in any two group is at most 1, and put these $n$ group of pebbles into $n$ boxes one by one. This continues until only one box has all the pebbles, and the rest of them are empty. And when it's over, define $Length$ as the total number of operations done by Alice.
Let $f(a_1, ..., a_n)$ be the smallest value of $Length$ among all the possible operations on $(a_1, ..., a_n)$. Find the maximum possible value of $f(a_1, ..., a_n)$ among all the ordered pair $(a_1, ..., a_n)$, and find all the ordered pair $(a_1, ..., a_n)$ that equality holds.
Let $P(x)$ be a polynomial of degree $n > 1$ with integer coefficients and let $k$ be a positive integer. Consider the polynomial $Q(x) = P(P(\ldots P(P(x)) \ldots ))$, where $P$ occurs $k$ times. Prove that there are at most $n$ integers $t$ such that $Q(t) = t$.
Let $P$ be a point inside triangle $ABC$. Let $AP$ meet $BC$ at $A_1$, let $BP$ meet $CA$ at $B_1$, and let $CP$ meet $AB$ at $C_1$. Let $A_2$ be the point such that $A_1$ is the midpoint of $PA_2$, let $B_2$ be the point such that $B_1$ is the midpoint of $PB_2$, and let $C_2$ be the point such that $C_1$ is the midpoint of $PC_2$. Prove that points $A_2, B_2$, and $C_2$ cannot all lie strictly inside the circumcircle of triangle $ABC$.
(Australia)
In a regular 100-gon, 41 vertices are colored black and the remaining 59 vertices are colored white. Prove that there exist 24 convex quadrilaterals $Q_{1}, \ldots, Q_{24}$ whose corners are vertices of the 100-gon, so that
[list]
[*] the quadrilaterals $Q_{1}, \ldots, Q_{24}$ are pairwise disjoint, and
[*] every quadrilateral $Q_{i}$ has three corners of one color and one corner of the other color.
[/list]
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.
Consider a 4-point configuration in the plane such that every 3 points can be covered by a strip of a unit width. Prove that:
1) the four points can be covered by a strip of length at most $\sqrt2$ and
2)if no strip of length less that $\sqrt2$ covers all the four points, then the points are vertices of a square of length $\sqrt2$
Let $ABCDE$ be a convex pentagon with $CD= DE$ and $\angle EDC \ne 2 \cdot \angle ADB$.
Suppose that a point $P$ is located in the interior of the pentagon such that $AP =AE$ and $BP= BC$.
Prove that $P$ lies on the diagonal $CE$ if and only if area $(BCD)$ + area $(ADE)$ = area $(ABD)$ + area $(ABP)$.
(Hungary)
A hunter and an invisible rabbit play a game on an infinite square grid. First the hunter fixes a colouring of the cells with finitely many colours. The rabbit then secretly chooses a cell to start in. Every minute, the rabbit reports the colour of its current cell to the hunter, and then secretly moves to an adjacent cell that it has not visited before (two cells are adjacent if they share an edge). The hunter wins if after some finite time either:[list][*]the rabbit cannot move; or
[*]the hunter can determine the cell in which the rabbit started.[/list]Decide whether there exists a winning strategy for the hunter.
[i]Proposed by Aron Thomas[/i]
A circle is divided into $2n$ equal by $2n$ points. Ali draws $n+1$ arcs, of length $1,2,\ldots,n+1$. Prove that we can find two arcs, such that one of them is inside in the other one.
Let $P(x)$ and $Q(x)$ be two polynomials with integer coefficients, such that no nonconstant polynomial with rational coefficients divides both $P(x)$ and $Q(x).$ Suppose that for every positive integer $n$ the integers $P(n)$ and $Q(n)$ are positive, and $2^{Q(n)}-1$ divides $3^{P(n)}-1.$ Prove that $Q(x)$ is a constant polynomial.
[i]Proposed by Oleksiy Klurman, Ukraine[/i]