Olympiad problems

2007 China Team Selection Test, 1

Find all the pairs of positive integers $ (a,b)$ such that $ a^2 \plus{} b \minus{} 1$ is a power of prime number $ ; a^2 \plus{} b \plus{} 1$ can divide $ b^2 \minus{} a^3 \minus{} 1,$ but it can't divide $ (a \plus{} b \minus{} 1)^2.$

1990 Polish MO Finals, 3

Tags: number theory , modular arithmetic

Prove that for all integers $n > 2$, \[ 3| \sum\limits_{i=0}^{[n/3]} (-1)^i C _n ^{3i} \]

2012 AIME Problems, 10

Tags: modular arithmetic

Let $\mathcal{S}$ be the set of all perfect squares whose rightmost three digits in base $10$ are $256$. Let $\mathcal{T}$ be the set of all numbers of the form $\frac{x-256}{1000}$, where $x$ is in $\mathcal{S}$. In other words, $\mathcal{T}$ is the set of numbers that result when the last three digits of each number in $\mathcal{S}$ are truncated. Find the remainder when the tenth smallest element of $\mathcal{T}$ is divided by $1000$.

2010 ELMO Shortlist, 5

Tags: number theory , modular arithmetic

Find the set $S$ of primes such that $p \in S$ if and only if there exists an integer $x$ such that $x^{2010} + x^{2009} + \cdots + 1 \equiv p^{2010} \pmod{p^{2011}}$. [i]Brian Hamrick.[/i]

1994 IMO, 6

Tags: number theory , prime number , combinatorial number theory , combinatorics , modular arithmetic

Show that there exists a set $ A$ of positive integers with the following property: for any infinite set $ S$ of primes, there exist [i]two[/i] positive integers $ m$ in $ A$ and $ n$ not in $ A$, each of which is a product of $ k$ distinct elements of $ S$ for some $ k \geq 2$.

1978 IMO Longlists, 32

Tags: circumcircle , analytic geometry , geometry , modular arithmetic

Let $\mathcal{C}$ be the circumcircle of the square with vertices $(0, 0), (0, 1978), (1978, 0), (1978, 1978)$ in the Cartesian plane. Prove that $\mathcal{C}$ contains no other point for which both coordinates are integers.

2014 PUMaC Number Theory A, 6

Tags: modular arithmetic

Let $S = \{2,5,8,11,14,17,20,\dots\}$. Given that one can choose $n$ different numbers from $S$, $\{A_1,A_2,\dots,A_n\}$ s.t. $\sum_{i=1}^n \frac{1}{A_i} = 1$, find the minimum possible value of $n$.

2002 China Team Selection Test, 3

Tags: induction , number theory , modular arithmetic

Find all groups of positive integers $ (a,x,y,n,m)$ that satisfy $ a(x^n \minus{} x^m) \equal{} (ax^m \minus{} 4) y^2$ and $ m \equiv n \pmod{2}$ and $ ax$ is odd.

2005 Turkey MO (2nd round), 2

Tags: geometry , radical axis , power of a point , parallelogram , circumcircle , modular arithmetic

In a triangle $ABC$ with $AB<AC<BC$, the perpendicular bisectors of $AC$ and $BC$ intersect $BC$ and $AC$ at $K$ and $L$, respectively. Let $O$, $O_1$, and $O_2$ be the circumcentres of triangles $ABC$, $CKL$, and $OAB$, respectively. Prove that $OCO_1O_2$ is a parallelogram.

2008 Bosnia And Herzegovina - Regional Olympiad, 3

Tags: modular arithmetic

Let $ b$ be an even positive integer. Assume that there exist integer $ n > 1$ such that $ \frac {b^{n} \minus{} 1}{b \minus{} 1}$ is perfect square. Prove that $ b$ is divisible by 8.

PEN O Problems, 41

Tags: induction , modular arithmetic

Prove that for every positive integer $n$ there exists an $n$-digit number divisible by $5^n$ all of whose digits are odd.

2001 IMO Shortlist, 6

Tags: number theory , sum , additive number theory , modular arithmetic

Is it possible to find $100$ positive integers not exceeding $25,000$, such that all pairwise sums of them are different?

2006 Putnam, A3

Tags: vector , linear algebra , matrix , modular arithmetic

Let $1,2,3,\dots,2005,2006,2007,2009,2012,2016,\dots$ be a sequence defined by $x_{k}=k$ for $k=1,2\dots,2006$ and $x_{k+1}=x_{k}+x_{k-2005}$ for $k\ge 2006.$ Show that the sequence has 2005 consecutive terms each divisible by 2006.

2009 Indonesia TST, 3

Tags: floor function , inequalities , number theory , modular arithmetic , ceiling function

Let $ n \ge 2009$ be an integer and define the set: \[ S \equal{} \{2^x|7 \le x \le n, x \in \mathbb{N}\}. \] Let $ A$ be a subset of $ S$ and the sum of last three digits of each element of $ A$ is $ 8$. Let $ n(X)$ be the number of elements of $ X$. Prove that \[ \frac {28}{2009} < \frac {n(A)}{n(S)} < \frac {82}{2009}. \]

2013 AIME Problems, 9

Tags: combinatorics , modular arithmetic , recurrence

A $7 \times 1$ board is completely covered by $m \times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the board. Each tile is either red, blue, or green. Let $N$ be the number of tilings of the $7 \times 1$ board in which all three colors are used at least once. For example, a $1 \times 1$ red tile followed by a $2 \times 1$ green tile, a $1 \times 1$ green tile, a $2 \times 1$ blue tile, and a $1 \times 1$ green tile is a valid tiling. Note that if the $2 \times 1$ blue tile is replaced by two $1 \times 1$ blue tiles, this results in a different tiling. Find the remainder when $N$ is divided by $1000$.

2004 USA Team Selection Test, 2

Tags: invariant , induction , polynomial , algebra , vector , modular arithmetic

Assume $n$ is a positive integer. Considers sequences $a_0, a_1, \ldots, a_n$ for which $a_i \in \{1, 2, \ldots , n\}$ for all $i$ and $a_n = a_0$. (a) Suppose $n$ is odd. Find the number of such sequences if $a_i - a_{i-1} \not \equiv i \pmod{n}$ for all $i = 1, 2, \ldots, n$. (b) Suppose $n$ is an odd prime. Find the number of such sequences if $a_i - a_{i-1} \not \equiv i, 2i \pmod{n}$ for all $i = 1, 2, \ldots, n$.

2006 Germany Team Selection Test, 2

Tags: invariant , modular arithmetic , combinatorics

There are $ n$ markers, each with one side white and the other side black. In the beginning, these $ n$ markers are aligned in a row so that their white sides are all up. In each step, if possible, we choose a marker whose white side is up (but not one of the outermost markers), remove it, and reverse the closest marker to the left of it and also reverse the closest marker to the right of it. Prove that, by a finite sequence of such steps, one can achieve a state with only two markers remaining if and only if $ n \minus{} 1$ is not divisible by $ 3$. [i]Proposed by Dusan Dukic, Serbia[/i]

2006 India IMO Training Camp, 2

Tags: analytic geometry , geometry , number theory , 3d geometry , pigeonhole principle , modular arithmetic

Let $u_{jk}$ be a real number for each $j=1,2,3$ and each $k=1,2$ and let $N$ be an integer such that \[\max_{1\le k \le 2} \sum_{j=1}^3 |u_{jk}| \leq N\] Let $M$ and $l$ be positive integers such that $l^2 <(M+1)^3$. Prove that there exist integers $\xi_1,\xi_2,\xi_3$ not all zero, such that \[\max_{1\le j \le 3}\xi_j \le M\ \ \ \ \text{and} \ \ \ \left|\sum_{j=1}^3 u_{jk}\xi_k\right| \le \frac{MN}{l} \ \ \ \ \text{for k=1,2}\]

2011 Preliminary Round - Switzerland, 4

Tags: combinatorics , geometric transformation , geometry , modular arithmetic

Given is a circular bus route with $n\geqslant2$ bus stops. The route can be frequented in both directions. The way between two stops is called [i]section[/i] and one of the bus stops is called [i]Zürich[/i]. A bus shall start at Zürich, pass through all the bus stops [b]at least once[/b] and drive along exactly $n+2$ sections before it returns to Zürich in the end. Assuming that the bus can chance directions at each bus stop, how many possible routes are there? EDIT: Sorry, there was a mistake...corrected now, thanks mavropnevma! :oops:

2006 CentroAmerican, 1

Tags: 3d geometry , geometry , modular arithmetic

For $0 \leq d \leq 9$, we define the numbers \[S_{d}=1+d+d^{2}+\cdots+d^{2006}\]Find the last digit of the number \[S_{0}+S_{1}+\cdots+S_{9}.\]

2011 Mongolia Team Selection Test, 1

Tags: modular arithmetic , number theory

Let $v(n)$ be the order of $2$ in $n!$. Prove that for any positive integers $a$ and $m$ there exists $n$ ($n>1$) such that $v(n) \equiv a (\mod m)$. I have a book with Mongolian problems from this year, and this problem appeared in it. Perhaps I am terribly misinterpreting this problem, but it seems like it is wrong. Any ideas?

2014 Putnam, 1

Tags: modular arithmetic , induction

A [i]base[/i] 10 [i]over-expansion[/i] of a positive integer $N$ is an expression of the form $N=d_k10^k+d_{k-1}10^{k-1}+\cdots+d_0 10^0$ with $d_k\ne 0$ and $d_i\in\{0,1,2,\dots,10\}$ for all $i.$ For instance, the integer $N=10$ has two base 10 over-expansions: $10=10\cdot 10^0$ and the usual base 10 expansion $10=1\cdot 10^1+0\cdot 10^0.$ Which positive integers have a unique base 10 over-expansion?

2013 India Regional Mathematical Olympiad, 6

Tags: number theory , modular arithmetic , quadratic , diophantine equation

Suppose that $m$ and $n$ are integers, such that both the quadratic equations $x^2+mx-n=0$ and $x^2-mx+n=0$ have integer roots. Prove that $n$ is divisible by $6$.

2007 Pre-Preparation Course Examination, 9

Tags: number theory , modular arithmetic

Solve the equation $4xy-x-y=z^2$ in positive integers.

2014 Romania Team Selection Test, 2

Tags: modular arithmetic , algebra , number theory , induction

Let $n \ge 2$ be an integer. Show that there exist $n+1$ numbers $x_1, x_2, \ldots, x_{n+1} \in \mathbb{Q} \setminus \mathbb{Z}$, so that $\{ x_1^3 \} + \{ x_2^3 \} + \cdots + \{ x_n^3 \}=\{ x_{n+1}^3 \}$, where $\{ x \}$ is the fractionary part of $x$.