Olympiad problems

2003 Tournament Of Towns, 5

Prior to the game John selects an integer greater than $100$. Then Mary calls out an integer $d$ greater than $1$. If John's integer is divisible by $d$, then Mary wins. Otherwise, John subtracts $d$ from his number and the game continues (with the new number). Mary is not allowed to call out any number twice. When John's number becomes negative, Mary loses. Does Mary have a winning strategy?

1995 IMO Shortlist, 2

Tags: quadratic , modular arithmetic , number theory , partition

Let $ \mathbb{Z}$ denote the set of all integers. Prove that for any integers $ A$ and $ B,$ one can find an integer $ C$ for which $ M_1 \equal{} \{x^2 \plus{} Ax \plus{} B : x \in \mathbb{Z}\}$ and $ M_2 \equal{} {2x^2 \plus{} 2x \plus{} C : x \in \mathbb{Z}}$ do not intersect.

1991 IMO Shortlist, 15

Tags: factorial , modular arithmetic , periodic sequence , decimal representation , digit

Let $ a_n$ be the last nonzero digit in the decimal representation of the number $ n!.$ Does the sequence $ a_1, a_2, \ldots, a_n, \ldots$ become periodic after a finite number of terms?

1989 IMO Longlists, 27

Tags: calculus , integration , modular arithmetic , number theory , relatively prime , combinatorics

Let $ L$ denote the set of all lattice points of the plane (points with integral coordinates). Show that for any three points $ A,B,C$ of $ L$ there is a fourth point $ D,$ different from $ A,B,C,$ such that the interiors of the segments $ AD,BD,CD$ contain no points of $ L.$ Is the statement true if one considers four points of $ L$ instead of three?

2012 AIME Problems, 11

Tags: invariant , modular arithmetic , analytic geometry , graphing lines , slope , rotation , geometry

A frog begins at $P_0 = (0,0)$ and makes a sequence of jumps according to the following rule: from $P_n=(x_n,y_n)$, the frog jumps to $P_{n+1}$, which may be any of the points $(x_n+7, y_n+2)$, $(x_n+2,y_n+7)$, $(x_n-5, y_n-10)$, or $(x_n-10,y_n-5)$. There are $M$ points $(x,y)$ with $|x|+|y| \le 100$ that can be reached by a sequence of such jumps. Find the remainder when $M$ is divided by $1000$.

2011 ELMO Shortlist, 4

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

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]

2013 All-Russian Olympiad, 1

Tags: modular arithmetic , combinatorics , #5 , graph theory

$2n$ real numbers with a positive sum are aligned in a circle. For each of the numbers, we can see there are two sets of $n$ numbers such that this number is on the end. Prove that at least one of the numbers has a positive sum for both of these two sets.

1992 Iran MO (2nd round), 1

Tags: modular arithmetic , number theory

Prove that for any positive integer $t,$ \[1+2^t+3^t+\cdots+9^t - 3(1 + 6^t +8^t )\] is divisible by $18.$

2013 Bundeswettbewerb Mathematik, 4

Tags: modular arithmetic , quadratic , floor function , combinatorics

Two players $A$ and $B$ play the following game taking alternate moves. In each move, a player writes one digit on the blackboard. Each new digit is written either to the right or left of the sequence of digits already written on the blackboard. Suppose that $A$ begins the game and initially the blackboard was empty. $B$ wins the game if ,after some move of $B$, the sequence of digits written in the blackboard represents a perfect square. Prove that $A$ can prevent $B$ from winning.

2012 AMC 10, 22

Tags: modular arithmetic , number theory , diophantine equation , system of equations , algebra

The sum of the first $m$ positive odd integers is $212$ more than the sum of the first $n$ positive even integers. What is the sum of all possible values of $n$? $ \textbf{(A)}\ 255 \qquad\textbf{(B)}\ 256 \qquad\textbf{(C)}\ 257 \qquad\textbf{(D)}\ 258 \qquad\textbf{(E)}\ 259 $

2014 USA TSTST, 4

Tags: algebra , polynomial , vector , floor function , modular arithmetic , pigeonhole principle , linear algebra

Let $P(x)$ and $Q(x)$ be arbitrary polynomials with real coefficients, and let $d$ be the degree of $P(x)$. Assume that $P(x)$ is not the zero polynomial. Prove that there exist polynomials $A(x)$ and $B(x)$ such that: (i) both $A$ and $B$ have degree at most $d/2$ (ii) at most one of $A$ and $B$ is the zero polynomial. (iii) $\frac{A(x)+Q(x)B(x)}{P(x)}$ is a polynomial with real coefficients. That is, there is some polynomial $C(x)$ with real coefficients such that $A(x)+Q(x)B(x)=P(x)C(x)$.

1999 IMO Shortlist, 3

Tags: modular arithmetic , number theory , integer sequence , divisibility , sequence

Prove that there exists two strictly increasing sequences $(a_{n})$ and $(b_{n})$ such that $a_{n}(a_{n}+1)$ divides $b^{2}_{n}+1$ for every natural n.

2009 Baltic Way, 9

Tags: modular arithmetic , inequalities , number theory

Determine all positive integers $n$ for which $2^{n+1}-n^2$ is a prime number.

2014 NIMO Problems, 4

Tags: modular arithmetic , euler , floor function , logarithm

Let $n$ be largest number such that \[ \frac{2014^{100!}-2011^{100!}}{3^n} \] is still an integer. Compute the remainder when $3^n$ is divided by $1000$.

2010 Malaysia National Olympiad, 9

Tags: euler , modular arithmetic , number theory

Let $m$ and $n$ be positive integers such that $2^n+3^m$ is divisible by $5$. Prove that $2^m+3^n$ is divisible by $5$.

2007 Princeton University Math Competition, 6

Tags: modular arithmetic

Find the last three digits of \[2008^{2007^{\cdot^{\cdot^{\cdot ^{2^1}}}}}.\]

2012 China National Olympiad, 3

Tags: modular arithmetic , pigeonhole principle , inequalities , combinatorics

Find the smallest positive integer $k$ such that, for any subset $A$ of $S=\{1,2,\ldots,2012\}$ with $|A|=k$, there exist three elements $x,y,z$ in $A$ such that $x=a+b$, $y=b+c$, $z=c+a$, where $a,b,c$ are in $S$ and are distinct integers. [i]Proposed by Huawei Zhu[/i]

2013 USAMO, 5

Tags: modular arithmetic , probability , function , ratio , number theory

Given positive integers $m$ and $n$, prove that there is a positive integer $c$ such that the numbers $cm$ and $cn$ have the same number of occurrences of each non-zero digit when written in base ten.

2012 Online Math Open Problems, 43

Tags: probability , modular arithmetic , number theory , relatively prime

An integer $x$ is selected at random between 1 and $2011!$ inclusive. The probability that $x^x - 1$ is divisible by $2011$ can be expressed in the form $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m$. [i]Author: Alex Zhu[/i]

2010 Indonesia TST, 2

Tags: modular arithmetic , number theory

Let $ A\equal{}\{n: 1 \le n \le 2009^{2009},n \in \mathbb{N} \}$ and let $ S\equal{}\{n: n \in A,\gcd \left(n,2009^{2009}\right)\equal{}1\}$. Let $ P$ be the product of all elements of $ S$. Prove that \[ P \equiv 1 \pmod{2009^{2009}}.\] [i]Nanang Susyanto, Jogjakarta[/i]

2015 Bangladesh Mathematical Olympiad, 3

Tags: number theory , algebra , modular arithmetic

Let $n$ be a positive integer.Consider the polynomial $p(x)=x^2+x+1$. What is the remainder of $ x^3$ when divided by $x^2+x+1$.For what positive integers values of $n$ is $ x^{2n}+x^n+1$ divisible by $p(x)$? Post no:[size=300]$100$[/size]

2008 Ukraine Team Selection Test, 10

Tags: modular arithmetic , number theory , divisibility

Let $b,n > 1$ be integers. Suppose that for each $k > 1$ there exists an integer $a_k$ such that $b - a^n_k$ is divisible by $k$. Prove that $b = A^n$ for some integer $A$. [i]Author: Dan Brown, Canada[/i]

1996 IMO Shortlist, 1

Tags: rectangle , combinatorics , graph theory , modular arithmetic

We are given a positive integer $ r$ and a rectangular board $ ABCD$ with dimensions $ AB \equal{} 20, BC \equal{} 12$. The rectangle is divided into a grid of $ 20 \times 12$ unit squares. The following moves are permitted on the board: one can move from one square to another only if the distance between the centers of the two squares is $ \sqrt {r}$. The task is to find a sequence of moves leading from the square with $ A$ as a vertex to the square with $ B$ as a vertex. (a) Show that the task cannot be done if $ r$ is divisible by 2 or 3. (b) Prove that the task is possible when $ r \equal{} 73$. (c) Can the task be done when $ r \equal{} 97$?

PEN E Problems, 33

Tags: modular arithmetic

Prove that there are no positive integers $a$ and $b$ such that for all different primes $p$ and $q$ greater than $1000$, the number $ap+bq$ is also prime.

2006 China Team Selection Test, 3

Tags: algebra , polynomial , number theory , greatest common divisor , modular arithmetic , vector , linear algebra

Let $a_{i}$ and $b_{i}$ ($i=1,2, \cdots, n$) be rational numbers such that for any real number $x$ there is: \[x^{2}+x+4=\sum_{i=1}^{n}(a_{i}x+b)^{2}\] Find the least possible value of $n$.