Olympiad problems

2001 Poland - Second Round, 1

Find all integers $n\ge 3$ for which the following statement is true: Any arithmetic progression $a_1,\ldots ,a_n$ with $n$ terms for which $a_1+2a_2+\ldots+na_n$ is rational contains at least one rational term.

2012 Hanoi Open Mathematics Competitions, 11

Tags: modular arithmetic , greatest common divisor

[b]Q11.[/b] Let be given a sequense $a_1=5, \; a_2=8$ and $a_{n+1}=a_n+3a_{n-1}, \qquad n=1,2,3,...$ Calculate the greatest common divisor of $a_{2011}$ and $a_{2012}$.

2009 Indonesia TST, 1

Tags: modular arithmetic , induction , number theory

Prove that for all odd $ n > 1$, we have $ 8n \plus{} 4|C^{4n}_{2n}$.

2014 USA Team Selection Test, 2

Tags: modular arithmetic , induction , quadratic residue , quadratic , number theory

Let $a_1,a_2,a_3,\ldots$ be a sequence of integers, with the property that every consecutive group of $a_i$'s averages to a perfect square. More precisely, for every positive integers $n$ and $k$, the quantity \[\frac{a_n+a_{n+1}+\cdots+a_{n+k-1}}{k}\] is always the square of an integer. Prove that the sequence must be constant (all $a_i$ are equal to the same perfect square). [i]Evan O'Dorney and Victor Wang[/i]

2001 CentroAmerican, 3

Tags: modular arithmetic

In a circumference of a circle, $ 10000$ points are marked, and they are numbered from $ 1$ to $ 10000$ in a clockwise manner. $ 5000$ segments are drawn in such a way so that the following conditions are met: 1. Each segment joins two marked points. 2. Each marked point belongs to one and only one segment. 3. Each segment intersects exactly one of the remaining segments. 4. A number is assigned to each segment that is the product of the number assigned to each end point of the segment. Let $ S$ be the sum of the products assigned to all the segments. Show that $ S$ is a multiple of $ 4$.

2012 Uzbekistan National Olympiad, 2

Tags: calculus , number theory , modular arithmetic , integration

For any positive integers $n$ and $m$ satisfying the equation $n^3+(n+1)^3+(n+2)^3=m^3$, prove that $4\mid n+1$.

2002 AIME Problems, 14

Tags: set , modular arithmetic

A set $\mathcal{S}$ of distinct positive integers has the following property: for every integer $x$ in $\mathcal{S},$ the arithmetic mean of the set of values obtained by deleting $x$ from $\mathcal{S}$ is an integer. Given that 1 belongs to $\mathcal{S}$ and that 2002 is the largest element of $\mathcal{S},$ what is the greatet number of elements that $\mathcal{S}$ can have?

2010 Germany Team Selection Test, 3

Tags: modular arithmetic , sequence , divisibility , number theory

Find all positive integers $n$ such that there exists a sequence of positive integers $a_1$, $a_2$,$\ldots$, $a_n$ satisfying: \[a_{k+1}=\frac{a_k^2+1}{a_{k-1}+1}-1\] for every $k$ with $2\leq k\leq n-1$. [i]Proposed by North Korea[/i]

2006 Turkey Team Selection Test, 1

Tags: induction , modular arithmetic , quadratic , gauss , prime number , number theory

For all integers $n\geq 1$ we define $x_{n+1}=x_1^2+x_2^2+\cdots +x_n^2$, where $x_1$ is a positive integer. Find the least $x_1$ such that 2006 divides $x_{2006}$.

2012 IMO Shortlist, N4

Tags: number theory , modular arithmetic , equation

An integer $a$ is called friendly if the equation $(m^2+n)(n^2+m)=a(m-n)^3$ has a solution over the positive integers. [b]a)[/b] Prove that there are at least $500$ friendly integers in the set $\{ 1,2,\ldots ,2012\}$. [b]b)[/b] Decide whether $a=2$ is friendly.

2013 Stanford Mathematics Tournament, 10

Tags: modular arithmetic

Consider a sequence given by $a_n=a_{n-1}+3a_{n-2}+a_{n-3}$, where $a_0=a_1=a_2=1$. What is the remainder of $a_{2013}$ divided by $7$?

PEN B Problems, 6

Tags: relatively prime , number theory , modular arithmetic , primitive root

Suppose that $m$ does not have a primitive root. Show that \[a^{ \frac{\phi(m)}{2}}\equiv 1 \; \pmod{m}\] for every $a$ relatively prime $m$.

2005 Baltic Way, 18

Tags: modular arithmetic , number theory

Let $x$ and $y$ be positive integers and assume that $z=\frac{4xy}{x+y}$ is an odd integer. Prove that at least one divisor of $z$ can be expressed in the form $4n-1$ where $n$ is a positive integer.

2006 Baltic Way, 17

Tags: number theory , modular arithmetic

Determine all positive integers $n$ such that $3^{n}+1$ is divisible by $n^{2}$.

2009 IMO, 1

Tags: number theory , modular arithmetic , induction

Let $ n$ be a positive integer and let $ a_1,a_2,a_3,\ldots,a_k$ $ ( k\ge 2)$ be distinct integers in the set $ { 1,2,\ldots,n}$ such that $ n$ divides $ a_i(a_{i + 1} - 1)$ for $ i = 1,2,\ldots,k - 1$. Prove that $ n$ does not divide $ a_k(a_1 - 1).$ [i]Proposed by Ross Atkins, Australia [/i]

2014 IberoAmerican, 1

Tags: modular arithmetic , induction , combinatorics

$N$ coins are placed on a table, $N - 1$ are genuine and have the same weight, and one is fake, with a different weight. Using a two pan balance, the goal is to determine with certainty the fake coin, and whether it is lighter or heavier than a genuine coin. Whenever one can deduce that one or more coins are genuine, they will be inmediately discarded and may no longer be used in subsequent weighings. Determine all $N$ for which the goal is achievable. (There are no limits regarding how many times one may use the balance). Note: the only difference between genuine and fake coins is their weight; otherwise, they are identical.

2013 India Regional Mathematical Olympiad, 1

Tags: modular arithmetic , number theory

Prove that there do not exist natural numbers $x$ and $y$ with $x>1$ such that , \[ \frac{x^7-1}{x-1}=y^5+1 \]

2002 China Girls Math Olympiad, 2

Tags: modular arithmetic , combinatorics

There are $ 3n, n \in \mathbb{Z}^\plus{}$ girl students who took part in a summer camp. There were three girl students to be on duty every day. When the summer camp ended, it was found that any two of the $ 3n$ students had just one time to be on duty on the same day. (1) When $ n\equal{}3,$ is there any arrangement satisfying the requirement above. Prove yor conclusion. (2) Prove that $ n$ is an odd number.

1984 IMO Longlists, 24

Tags: modular arithmetic , combinatorics , chessboard

(a) Decide whether the fields of the $8 \times 8$ chessboard can be numbered by the numbers $1, 2, \dots , 64$ in such a way that the sum of the four numbers in each of its parts of one of the forms [list][img]http://www.artofproblemsolving.com/Forum/download/file.php?id=28446[/img][/list] is divisible by four. (b) Solve the analogous problem for [list][img]http://www.artofproblemsolving.com/Forum/download/file.php?id=28447[/img][/list]

2010 China Team Selection Test, 3

Tags: modular arithmetic , number theory

Fine all positive integers $m,n\geq 2$, such that (1) $m+1$ is a prime number of type $4k-1$; (2) there is a (positive) prime number $p$ and nonnegative integer $a$, such that \[\frac{m^{2^n-1}-1}{m-1}=m^n+p^a.\]

2006 ISI B.Stat Entrance Exam, 3

Tags: modular arithmetic , number theory , induction , prime number

Prove that $n^4 + 4^{n}$ is composite for all values of $n$ greater than $1$.

2008 Harvard-MIT Mathematics Tournament, 25

Tags: algorithm , modular arithmetic

Alice and the Cheshire Cat play a game. At each step, Alice either (1) gives the cat a penny, which causes the cat to change the number of (magic) beans that Alice has from $ n$ to $ 5n$ or (2) gives the cat a nickel, which causes the cat to give Alice another bean. Alice wins (and the cat disappears) as soon as the number of beans Alice has is greater than $ 2008$ and has last two digits $ 42$. What is the minimum number of cents Alice can spend to win the game, assuming she starts with 0 beans?

2008 Harvard-MIT Mathematics Tournament, 2

Tags: modular arithmetic

Find the smallest positive integer $ n$ such that $ 107n$ has the same last two digits as $ n$.

1997 Romania Team Selection Test, 4

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

Let $n\ge 2$ be an integer and let $P(X)=X^n+a_{n-1}X^{n-1}+\ldots +a_1X+1$ be a polynomial with positive integer coefficients. Suppose that $a_k=a_{n-k}$ for all $k\in 1,2,\ldots,n-1$. Prove that there exist infinitely many pairs of positive integers $x,y$ such that $x|P(y)$ and $y|P(x)$. [i]Remus Nicoara[/i]

2004 Romania National Olympiad, 2

Tags: modular arithmetic , inequalities

Prove that the equation $x^2+y^2+z^2+t^2=2^{2004}$, where $0 \leq x \leq y \leq z \leq t$, has exactly $2$ solutions in $\mathbb Z$. [i]Mihai Baluna[/i]