Olympiad problems

2013 Iran Team Selection Test, 4

Tags: modular arithmetic , parallelogram , geometry , combinatorics , analytic geometry , vector , number theory

$m$ and $n$ are two nonnegative integers. In the Philosopher's Chess, The chessboard is an infinite grid of identical regular hexagons and a new piece named the Donkey moves on it as follows: Starting from one of the hexagons, the Donkey moves $m$ cells in one of the $6$ directions, then it turns $60$ degrees clockwise and after that moves $n$ cells in this new direction until it reaches it's final cell. At most how many cells are in the Philosopher's chessboard such that one cannot go from anyone of them to the other with a finite number of movements of the Donkey? [i]Proposed by Shayan Dashmiz[/i]

2013 National Olympiad First Round, 30

Tags: modular arithmetic

For how many postive integers $n$ less than $2013$, does $p^2+p+1$ divide $n$ where $p$ is the least prime divisor of $n$? $ \textbf{(A)}\ 212 \qquad\textbf{(B)}\ 206 \qquad\textbf{(C)}\ 191 \qquad\textbf{(D)}\ 185 \qquad\textbf{(E)}\ 173 $

1979 USAMO, 1

Tags: integration , calculus , modular arithmetic

Determine all non-negative integral solutions $ (n_{1},n_{2},\dots , n_{14}) $ if any, apart from permutations, of the Diophantine Equation \[n_{1}^{4}+n_{2}^{4}+\cdots+n_{14}^{4}=1,599.\]

2009 Croatia Team Selection Test, 4

Tags: modular arithmetic , number theory

Determine all triplets off positive integers $ (a,b,c)$ for which $ \mid2^a\minus{}b^c\mid\equal{}1$

2006 Costa Rica - Final Round, 2

Tags: modular arithmetic , floor function , number theory

Let $n$ be a positive integer, and let $p$ be a prime, such that $n>p$. Prove that : \[ \displaystyle \binom np \equiv \left\lfloor\frac{n}{p}\right\rfloor \ \pmod p. \]

2020 Durer Math Competition Finals, 1

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

Show that, for any fixed integer $\,n \geq 1,\,$ the sequence \[ 2, \; 2^2, \; 2^{2^2}, \; 2^{2^{2^2}}, \ldots (\mbox{mod} \; n) \] is eventually constant. [The tower of exponents is defined by $a_1 = 2, \; a_{i+1} = 2^{a_i}$. Also $a_i \; (\mbox{mod} \; n)$ means the remainder which results from dividing $a_i$ by $n$.]

2005 Taiwan TST Round 3, 3

Tags: modular arithmetic , divisibility , remainder , number theory

Given an integer ${n>1}$, denote by $P_{n}$ the product of all positive integers $x$ less than $n$ and such that $n$ divides ${x^2-1}$. For each ${n>1}$, find the remainder of $P_{n}$ on division by $n$. [i]Proposed by John Murray, Ireland[/i]

2003 IMO Shortlist, 6

Tags: function , combinatorics , modular arithmetic , counting , decimal representation

Let $f(k)$ be the number of integers $n$ satisfying the following conditions: (i) $0\leq n < 10^k$ so $n$ has exactly $k$ digits (in decimal notation), with leading zeroes allowed; (ii) the digits of $n$ can be permuted in such a way that they yield an integer divisible by $11$. Prove that $f(2m) = 10f(2m-1)$ for every positive integer $m$. [i]Proposed by Dirk Laurie, South Africa[/i]

2007 ITest, 11

Tags: modular arithmetic

Consider the "tower of power" $2^{2^{2^{.^{.^{.^2}}}}}$, where there are $2007$ twos including the base. What is the last (units) digit of this number? $\textbf{(A) }0\hspace{14em}\textbf{(B) }1\hspace{14em}\textbf{(C) }2$ $\textbf{(D) }3\hspace{14em}\textbf{(E) }4\hspace{14em}\textbf{(F) }5$ $\textbf{(G) }6\hspace{14em}\textbf{(H) }7\hspace{14em}\textbf{(I) }8$ $\textbf{(J) }9\hspace{14.3em}\textbf{(K) }2007$

2011 Indonesia TST, 4

Tags: modular arithmetic , number theory , induction

A prime number $p$ is a [b]moderate[/b] number if for every $2$ positive integers $k > 1$ and $m$, there exists k positive integers $n_1, n_2, ..., n_k $ such that \[ n_1^2+n_2^2+ ... +n_k^2=p^{k+m} \] If $q$ is the smallest [b]moderate[/b] number, then determine the smallest prime $r$ which is not moderate and $q < r$.

1974 IMO Longlists, 30

Tags: summation , divisibility , binomial coefficient , modular arithmetic , number theory

Prove that for any n natural, the number \[ \sum \limits_{k=0}^{n} \binom{2n+1}{2k+1} 2^{3k} \] cannot be divided by $5$.

2009 Romanian Master of Mathematics, 2

Tags: combinatorial geometry , analytic geometry , number theory , combinatorics , modular arithmetic

A set $ S$ of points in space satisfies the property that all pairwise distances between points in $ S$ are distinct. Given that all points in $ S$ have integer coordinates $ (x,y,z)$ where $ 1 \leq x,y, z \leq n,$ show that the number of points in $ S$ is less than $ \min \Big((n \plus{} 2)\sqrt {\frac {n}{3}}, n \sqrt {6}\Big).$ [i]Dan Schwarz, Romania[/i]

PEN H Problems, 27

Tags: modular arithmetic , diophantine equation , inradius , perimeter , geometry

Prove that there exist infinitely many positive integers $n$ such that $p=nr$, where $p$ and $r$ are respectively the semi-perimeter and the inradius of a triangle with integer side lengths.

2004 France Team Selection Test, 1

Tags: number theory , quadratic , modular arithmetic

If $n$ is a positive integer, let $A = \{n,n+1,...,n+17 \}$. Does there exist some values of $n$ for which we can divide $A$ into two disjoints subsets $B$ and $C$ such that the product of the elements of $B$ is equal to the product of the elements of $C$?

2005 National Olympiad First Round, 10

Tags: euler , modular arithmetic

Which of the following does not divide $n^{2225}-n^{2005}$ for every integer value of $n$? $ \textbf{(A)}\ 3 \qquad\textbf{(B)}\ 5 \qquad\textbf{(C)}\ 7 \qquad\textbf{(D)}\ 11 \qquad\textbf{(E)}\ 23 $

2004 IMO Shortlist, 6

Tags: remainder , number theory , divisibility , modular arithmetic

Given an integer ${n>1}$, denote by $P_{n}$ the product of all positive integers $x$ less than $n$ and such that $n$ divides ${x^2-1}$. For each ${n>1}$, find the remainder of $P_{n}$ on division by $n$. [i]Proposed by John Murray, Ireland[/i]

2005 USAMO, 2

Tags: modular arithmetic , algebra , diophantine equation

Prove that the system \begin{align*} x^6+x^3+x^3y+y & = 147^{157} \\ x^3+x^3y+y^2+y+z^9 & = 157^{147} \end{align*} has no solutions in integers $x$, $y$, and $z$.

2021 JBMO TST - Turkey, 6

Tags: number theory , modular arithmetic

Integers $a_1, a_2, \dots a_n$ are different at $\text{mod n}$. If $a_1, a_2-a_1, a_3-a_2, \dots a_n-a_{n-1}$ are also different at $\text{mod n}$, we call the ordered $n$-tuple $(a_1, a_2, \dots a_n)$ [i]lucky[/i]. For which positive integers $n$, one can find a lucky $n$-tuple?

2011 Putnam, A4

Tags: linear algebra , vector , putnam matrices , modular arithmetic , polynomial , matrix

For which positive integers $n$ is there an $n\times n$ matrix with integer entries such that every dot product of a row with itself is even, while every dot product of two different rows is odd?

2013 Gulf Math Olympiad, 3

Tags: combinatorics , rotation , geometry , modular arithmetic , vector , function , geometric transformation

There are $n$ people standing on a circular track. We want to perform a number of [i]moves[/i] so that we end up with a situation where the distance between every two neighbours is the same. The [i]move[/i] that is allowed consists in selecting two people and asking one of them to walk a distance $d$ on the circular track clockwise, and asking the other to walk the same distance on the track anticlockwise. The two people selected and the quantity $d$ can vary from move to move. Prove that it is possible to reach the desired situation (where the distance between every two neighbours is the same) after at most $n-1$ moves.

2009 Ukraine Team Selection Test, 7

Tags: number theory , sequence , divisibility , modular arithmetic

Let $ a_1$, $ a_2$, $ \ldots$, $ a_n$ be distinct positive integers, $ n\ge 3$. Prove that there exist distinct indices $ i$ and $ j$ such that $ a_i \plus{} a_j$ does not divide any of the numbers $ 3a_1$, $ 3a_2$, $ \ldots$, $ 3a_n$. [i]Proposed by Mohsen Jamaali, Iran[/i]