Olympiad problems

2012 AMC 12/AHSME, 17

Let $S$ be a subset of $\{1,2,3,\dots,30\}$ with the property that no pair of distinct elements in $S$ has a sum divisible by $5$. What is the largest possible size of $S$? $ \textbf{(A)}\ 10\qquad\textbf{(B)}\ 13\qquad\textbf{(C)}\ 15\qquad\textbf{(D)}\ 16\qquad\textbf{(E)}\ 18 $

2009 All-Russian Olympiad, 4

Tags: modular arithmetic , combinatorics

There are n cups arranged on the circle. Under one of cups is hiden a coin. For every move, it is allowed to choose 4 cups and verify if the coin lies under these cups. After that, the cups are returned into its former places and the coin moves to one of two neigbor cups. What is the minimal number of moves we need in order to eventually find where the coin is?

2014 AMC 8, 4

Tags: modular arithmetic , number theory , prime number

The sum of two prime numbers is $85$. What is the product of these two prime numbers? $\textbf{(A) }85\qquad\textbf{(B) }91\qquad\textbf{(C) }115\qquad\textbf{(D) }133\qquad \textbf{(E) }166$

PEN D Problems, 2

Tags: abstract algebra , modular arithmetic , congruence , group theory

Suppose that $p$ is an odd prime. Prove that \[\sum_{j=0}^{p}\binom{p}{j}\binom{p+j}{j}\equiv 2^{p}+1\pmod{p^{2}}.\]

2014 Turkey Team Selection Test, 1

Tags: modular arithmetic , number theory

Find all pairs $(m,n)$ of positive odd integers, such that $n \mid 3m+1$ and $m \mid n^2+3$.

PEN J Problems, 6

Tags: prime factorization , modular arithmetic , divisor function , quadratic , relatively prime , number theory

Show that if $m$ and $n$ are relatively prime positive integers, then $\phi( 5^m -1) \neq 5^{n}-1$.

1999 IMO Shortlist, 3

Tags: symmetry , rotation , counting , combinatorics , graph theory , modular arithmetic

A game is played by $n$ girls ($n \geq 2$), everybody having a ball. Each of the $\binom{n}{2}$ pairs of players, is an arbitrary order, exchange the balls they have at the moment. The game is called nice [b]nice[/b] if at the end nobody has her own ball and it is called [b]tiresome[/b] if at the end everybody has her initial ball. Determine the values of $n$ for which there exists a nice game and those for which there exists a tiresome game.

PEN B Problems, 5

Tags: polynomial , induction , symmetry , modular arithmetic , vieta , search , algebra

Let $p$ be an odd prime. If $g_{1}, \cdots, g_{\phi(p-1)}$ are the primitive roots $\pmod{p}$ in the range $1<g \le p-1$, prove that \[\sum_{i=1}^{\phi(p-1)}g_{i}\equiv \mu(p-1) \pmod{p}.\]

1999 Harvard-MIT Mathematics Tournament, 2

Tags: modular arithmetic

For what single digit $n$ does $91$ divide the $9$-digit number $12345n789$?

1998 Turkey MO (2nd round), 1

Tags: number theory , quadratic , modular arithmetic

Find all positive integers $x$ and $n$ such that ${{x}^{3}}+3367={{2}^{n}}$.

1992 Hungary-Israel Binational, 1

Tags: number theory , modular arithmetic

We examine the following two sequences: The Fibonacci sequence: $F_{0}= 0, F_{1}= 1, F_{n}= F_{n-1}+F_{n-2 }$ for $n \geq 2$; The Lucas sequence: $L_{0}= 2, L_{1}= 1, L_{n}= L_{n-1}+L_{n-2}$ for $n \geq 2$. It is known that for all $n \geq 0$ \[F_{n}=\frac{\alpha^{n}-\beta^{n}}{\sqrt{5}},L_{n}=\alpha^{n}+\beta^{n}, \] where $\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2}$. These formulae can be used without proof. Prove that $1+L_{2^{j}}\equiv 0 \pmod{2^{j+1}}$ for $j \geq 0$.

2005 Irish Math Olympiad, 3

Tags: modular arithmetic , number theory

Let $ x$ be an integer and $ y,z,w$ be odd positive integers. Prove that $ 17$ divides $ x^{y^{z^w}}\minus{}x^{y^z}$.

2000 Balkan MO, 3

Tags: geometry , modular arithmetic , rectangle

How many $1 \times 10\sqrt 2$ rectangles can be cut from a $50\times 90$ rectangle using cuts parallel to its edges?

Oliforum Contest III 2012, 1

Tags: number theory , modular arithmetic

Prove that exist infinite integers $n$ so that $n^2$ divides $2^n+3^n$. Thanks

2008 Baltic Way, 12

Tags: combinatorics , function , modular arithmetic , divisibility tests , graph theory , number theory

In a school class with $ 3n$ children, any two children make a common present to exactly one other child. Prove that for all odd $ n$ it is possible that the following holds: For any three children $ A$, $ B$ and $ C$ in the class, if $ A$ and $ B$ make a present to $ C$ then $ A$ and $ C$ make a present to $ B$.

2011 IMO, 5

Tags: symmetry , function , modular arithmetic , number theory

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers $m$ and $n$, the difference $f(m) - f(n)$ is divisible by $f(m- n)$. Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$, the number $f(n)$ is divisible by $f(m)$. [i]Proposed by Mahyar Sefidgaran, Iran[/i]

2007 Harvard-MIT Mathematics Tournament, 7

Tags: modular arithmetic , college

A student at Harvard named Kevin Was counting his stones by $11$ He messed up $n$ times And instead counted $9$s And wound up at $2007$. How many values of $n$ could make this limerick true?

PEN A Problems, 88

Tags: divisibility theory , modular arithmetic , induction , function

Find all positive integers $n$ such that $9^{n}-1$ is divisible by $7^n$.

2005 MOP Homework, 3

Tags: number theory , modular arithmetic

Prove that the equation $a^3-b^3=2004$ does not have any solutions in positive integers.

MathLinks Contest 7th, 2.2

Tags: number theory , prime factorization , modular arithmetic , vector

For a prime $ p$ an a positive integer $ n$, denote by $ \nu_p(n)$ the exponent of $ p$ in the prime factorization of $ n!$. Given a positive integer $ d$ and a finite set $ \{p_1,p_2,\ldots, p_k\}$ of primes, show that there are infinitely many positive integers $ n$ such that $ \nu_{p_i}(n) \equiv 0 \pmod d$, for all $ 1\leq i \leq k$.

2012 Romania Team Selection Test, 3

Tags: modular arithmetic , number theory , polynomial , algebra

Let $a_1$ , $\ldots$ , $a_n$ be positive integers and $a$ a positive integer that is greater than $1$ and is divisible by the product $a_1a_2\ldots a_n$. Prove that $a^{n+1}+a-1$ is not divisible by the product $(a+a_1-1)(a+a_2-1)\ldots(a+a_n-1)$.

2010 AMC 10, 24

Tags: ratio , geometric sequence , modular arithmetic

A high school basketball game between the Raiders and Wildcats was tied at the end of the first quarter. The number of points scored by the Raiders in each of the four quarters formed an increasing geometric sequence, and the number of points scored by the Wildcats in each of the four quarters formed an increasing arithmetic sequence. At the end of the fourth quarter, the Raiders had won by one point. Neither team scored more than $ 100$ points. What was the total number of points scored by the two teams in the first half? $ \textbf{(A)}\ 30 \qquad \textbf{(B)}\ 31 \qquad \textbf{(C)}\ 32 \qquad \textbf{(D)}\ 33 \qquad \textbf{(E)}\ 34$

2007 Iran Team Selection Test, 2

Tags: combinatorics , search , pigeonhole principle , modular arithmetic , ceiling function

Let $A$ be the largest subset of $\{1,\dots,n\}$ such that for each $x\in A$, $x$ divides at most one other element in $A$. Prove that \[\frac{2n}3\leq |A|\leq \left\lceil \frac{3n}4\right\rceil. \]

2002 National Olympiad First Round, 22

Tags: modular arithmetic

If $2^n$ divides $5^{256} - 1$, what is the largest possible value of $n$? $ \textbf{a)}\ 8 \qquad\textbf{b)}\ 10 \qquad\textbf{c)}\ 11 \qquad\textbf{d)}\ 12 \qquad\textbf{e)}\ \text{None of above} $

1998 National Olympiad First Round, 14

Tags: calculus , integration , modular arithmetic

Find the number of distinct integral solutions of $ x^{4} \plus{}2x^{3} \plus{}3x^{2} \minus{}x\plus{}1\equiv 0\, \, \left(mod\, 30\right)$ where $ 0\le x<30$. $\textbf{(A)}\ 0 \qquad\textbf{(B)}\ 1 \qquad\textbf{(C)}\ 2 \qquad\textbf{(D)}\ 3 \qquad\textbf{(E)}\ 4$