Olympiad problems

1994 Romania TST for IMO, 1:

Find the smallest nomial of this sequence that $a_1=1993^{1994^{1995}}$ and \[ a_{n+1}=\begin{cases}\frac{a_n}{2}&\text{if $n$ is even}\\a_n+7 &\text{if $n$ is odd.} \end{cases} \]

2011 ELMO Shortlist, 4

Tags: modular arithmetic , conic , ellipse , geometric transformation , reflection , geometry

Prove that for any convex pentagon $A_1A_2A_3A_4A_5$, there exists a unique pair of points $\{P,Q\}$ (possibly with $P=Q$) such that $\measuredangle{PA_i A_{i-1}} = \measuredangle{A_{i+1}A_iQ}$ for $1\le i\le 5$, where indices are taken $\pmod5$ and angles are directed $\pmod\pi$. [i]Calvin Deng.[/i]

2012 Online Math Open Problems, 48

Tags: modular arithmetic , quadratic , gauss , geometric series

Suppose that \[\sum_{i=1}^{982} 7^{i^2}\] can be expressed in the form $983q + r$, where $q$ and $r$ are integers and $0 \leq r \leq 492$. Find $r$. [i]Author: Alex Zhu[/i]

2004 Switzerland Team Selection Test, 8

Tags: modular arithmetic , number theory , sequence , divisibility

Let $m$ be a fixed integer greater than $1$. The sequence $x_0$, $x_1$, $x_2$, $\ldots$ is defined as follows: \[x_i = \begin{cases}2^i&\text{if }0\leq i \leq m - 1;\\\sum_{j=1}^mx_{i-j}&\text{if }i\geq m.\end{cases}\] Find the greatest $k$ for which the sequence contains $k$ consecutive terms divisible by $m$ . [i]Proposed by Marcin Kuczma, Poland[/i]

2010 Stanford Mathematics Tournament, 13

Tags: number theory , modular arithmetic

Find all the integers $x$ in $[20, 50]$ such that $6x+5\equiv 19 \mod 10$, that is, $10$ divides $(6x+15)+19$.

2024 Bosnia and Herzegovina Junior BMO TST, 2.

Tags: number theory , modular arithmetic

Determine all $x$, $y$, $k$ and $n$ positive integers such that: $10^x$ + $10^y$ + $n!$ = $2024^k$

2012 Iran MO (3rd Round), 4

Tags: algebra , polynomial , ring theory , modular arithmetic , number theory

$P(x)$ and $Q(x)$ are two polynomials with integer coefficients such that $P(x)|Q(x)^2+1$. [b]a)[/b] Prove that there exists polynomials $A(x)$ and $B(x)$ with rational coefficients and a rational number $c$ such that $P(x)=c(A(x)^2+B(x)^2)$. [b]b)[/b] If $P(x)$ is a monic polynomial with integer coefficients, Prove that there exists two polynomials $A(x)$ and $B(x)$ with integer coefficients such that $P(x)$ can be written in the form of $A(x)^2+B(x)^2$. [i]Proposed by Mohammad Gharakhani[/i]

2011 All-Russian Olympiad, 4

Tags: algebra , polynomial , modular arithmetic , symmetry , rectangle , combinatorics

There are some counters in some cells of $100\times 100$ board. Call a cell [i]nice[/i] if there are an even number of counters in adjacent cells. Can exactly one cell be [i]nice[/i]? [i]K. Knop[/i]

2013 Rioplatense Mathematical Olympiad, Level 3, 5

Tags: greatest common divisor , modular arithmetic , algorithm , number theory

Find all positive integers $n$ for which there exist two distinct numbers of $n$ digits, $\overline{a_1a_2\ldots a_n}$ and $\overline{b_1b_2\ldots b_n}$, such that the number of $2n$ digits $\overline{a_1a_2\ldots a_nb_1b_2\ldots b_n}$ is divisible by $\overline{b_1b_2\ldots b_na_1a_2\ldots a_n}$.

2006 Germany Team Selection Test, 2

Tags: factorial , modular arithmetic , number theory , divisibility , exponential , chinese remainder theorem

Find all positive integers $ n$ such that there exists a unique integer $ a$ such that $ 0\leq a < n!$ with the following property: \[ n!\mid a^n \plus{} 1 \] [i]Proposed by Carlos Caicedo, Colombia[/i]

1992 IMO Longlists, 6

Tags: probability , modular arithmetic , function , algebra , combinatorics

Suppose that n numbers $x_1, x_2, . . . , x_n$ are chosen randomly from the set $\{1, 2, 3, 4, 5\}$. Prove that the probability that $x_1^2+ x_2^2 +\cdots+ x_n^2 \equiv 0 \pmod 5$ is at least $\frac 15.$

2010 USAMO, 5

Tags: partial fractions , modular arithmetic

Let $q = \frac{3p-5}{2}$ where $p$ is an odd prime, and let\[ S_q = \frac{1}{2\cdot 3 \cdot 4} + \frac{1}{5\cdot 6 \cdot 7} + \cdots + \frac{1}{q(q+1)(q+2)} \]Prove that if $\frac{1}{p}-2S_q = \frac{m}{n}$ for integers $m$ and $n$, then $m - n$ is divisible by $p$.

2024 Bangladesh Mathematical Olympiad, P4

Tags: combinatorics , sequence , modular arithmetic , pigeonhole principle

Let $a_1, a_2, \ldots, a_{11}$ be integers. Prove that there exist numbers $b_1, b_2, \ldots, b_{11}$ such that [list] [*] $b_i$ is equal to $-1,0$ or $1$ for all $i \in \{1, 2,\dots, 11\}$. [*] all numbers can't be zero at a time. [*] the number $N=a_1b_1+a_2b_2+\ldots+a_{11}b_{11}$ is divisible by $2024$. [/list]

2005 Germany Team Selection Test, 3

Tags: inequalities , modular arithmetic , algorithm , induction , number theory

We have $2p-1$ integer numbers, where $p$ is a prime number. Prove that we can choose exactly $p$ numbers (from these $2p-1$ numbers) so that their sum is divisible by $p$.

2008 Bulgaria National Olympiad, 3

Tags: inequalities , trigonometry , modular arithmetic , induction , ceiling function , pigeonhole principle , algebra

Let $n\in\mathbb{N}$ and $0\leq a_1\leq a_2\leq\ldots\leq a_n\leq\pi$ and $b_1,b_2,\ldots ,b_n$ are real numbers for which the following inequality is satisfied : \[\left|\sum_{i\equal{}1}^{n} b_i\cos(ka_i)\right|<\frac{1}{k}\] for all $ k\in\mathbb{N}$. Prove that $ b_1\equal{}b_2\equal{}\ldots \equal{}b_n\equal{}0$.

2013 International Zhautykov Olympiad, 2

Tags: modular arithmetic , number theory

Find all odd positive integers $n>1$ such that there is a permutation $a_1, a_2, a_3, \ldots, a_n$ of the numbers $1, 2,3, \ldots, n$ where $n$ divides one of the numbers $a_k^2 - a_{k+1} - 1$ and $a_k^2 - a_{k+1} + 1$ for each $k$, $1 \leq k \leq n$ (we assume $a_{n+1}=a_1$).

2011 China Girls Math Olympiad, 6

Tags: modular arithmetic , number theory

Do there exist positive integers $m,n$, such that $m^{20}+11^n$ is a square number?

PEN D Problems, 12

Tags: congruence , modular arithmetic , floor function , abstract algebra , number theory , relatively prime , group theory

Suppose that $m>2$, and let $P$ be the product of the positive integers less than $m$ that are relatively prime to $m$. Show that $P \equiv -1 \pmod{m}$ if $m=4$, $p^n$, or $2p^{n}$, where $p$ is an odd prime, and $P \equiv 1 \pmod{m}$ otherwise.

1970 IMO Longlists, 2

Tags: modular arithmetic , euler , number theory

Prove that the two last digits of $9^{9^{9}}$ and $9^{9^{9^{9}}}$ are the same in decimal representation.

1989 IMO Longlists, 86

Tags: modular arithmetic , number theory , least common multiple , divisibility

Let $ m$ be a positive odd integer, $ m > 2.$ Find the smallest positive integer $ n$ such that $ 2^{1989}$ divides $ m^n \minus{} 1.$

1968 AMC 12/AHSME, 21

Tags: factorial , modular arithmetic

If $S=1!+2!+3!+ \cdots +99!$, then the units' digit in the value of $S$ is: $\textbf{(A)}\ 9 \qquad\textbf{(B)}\ 8 \qquad\textbf{(C)}\ 5 \qquad\textbf{(D)}\ 3 \qquad\textbf{(E)}\ 0$

1969 IMO Shortlist, 7

Tags: modular arithmetic , number theory , diophantine equation , additive number theory , perfect cube

$(BUL 1)$ Prove that the equation $\sqrt{x^3 + y^3 + z^3}=1969$ has no integral solutions.

2006 USAMO, 1

Tags: inequalities , floor function , modular arithmetic , pigeonhole principle , number theory

Let $p$ be a prime number and let $s$ be an integer with $0 < s < p.$ Prove that there exist integers $m$ and $n$ with $0 < m < n < p$ and \[ \left \{\frac{sm}{p} \right\} < \left \{\frac{sn}{p} \right \} < \frac{s}{p} \] if and only if $s$ is not a divisor of $p-1$. Note: For $x$ a real number, let $\lfloor x \rfloor$ denote the greatest integer less than or equal to $x$, and let $\{x\} = x - \lfloor x \rfloor$ denote the fractional part of x.

2006 Romania Team Selection Test, 3

Tags: modular arithmetic , induction , number theory

For which pairs of positive integers $(m,n)$ there exists a set $A$ such that for all positive integers $x,y$, if $|x-y|=m$, then at least one of the numbers $x,y$ belongs to the set $A$, and if $|x-y|=n$, then at least one of the numbers $x,y$ does not belong to the set $A$? [i]Adapted by Dan Schwarz from A.M.M.[/i]

1998 Putnam, 6

Tags: geometry , 3d geometry , modular arithmetic

Prove that, for any integers $a,b,c$, there exists a positive integer $n$ such that $\sqrt{n^3+an^2+bn+c}$ is not an integer.