Olympiad problems

1988 Romania Team Selection Test, 8

The positive integer $n$ is given and for all positive integers $k$, $1\leq k\leq n$, denote by $a_{kn}$ the number of all ordered sequences $(i_1,i_2,\ldots,i_k)$ of positive integers which verify the following two conditions: a) $1\leq i_1<i_2< \cdots i_k \leq n$; b) $i_{r+1}-i_r \equiv 1 \pmod 2$, for all $r \in\{1,2,\ldots,k-1\}$. Compute the number $a(n) = \sum\limits_{k=1}^n a_{kn}$. [i]Ioan Tomescu[/i]

2007 National Olympiad First Round, 34

Tags: quadratic , modular arithmetic

For how many primes $p$ less than $15$, there exists integer triples $(m,n,k)$ such that \[ \begin{array}{rcl} m+n+k &\equiv& 0 \pmod p \\ mn+mk+nk &\equiv& 1 \pmod p \\ mnk &\equiv& 2 \pmod p. \end{array} \] $ \textbf{(A)}\ 2 \qquad\textbf{(B)}\ 3 \qquad\textbf{(C)}\ 4 \qquad\textbf{(D)}\ 5 \qquad\textbf{(E)}\ 6 $

2013 Kazakhstan National Olympiad, 2

Tags: modular arithmetic , number theory , relatively prime

Let for natural numbers $a,b,c$ and any natural $n$ we have that $(abc)^n$ divides $ ((a^n-1)(b^n-1)(c^n-1)+1)^3$. Prove that then $a=b=c$.

1999 Italy TST, 1

Tags: modular arithmetic , number theory

Prove that for any prime number $p$ the equation $2^p+3^p=a^n$ has no solution $(a,n)$ in integers greater than $1$.

2012 China National Olympiad, 3

Tags: inequalities , modular arithmetic , pigeonhole principle , 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]

2006 Vietnam National Olympiad, 2

Tags: geometry , modular arithmetic , circumcircle

Let $ABCD$ be a convex quadrilateral. Take an arbitrary point $M$ on the line $AB$, and let $N$ be the point of intersection of the circumcircles of triangles $MAC$ and $MBC$ (different from $M$). Prove that: a) The point $N$ lies on a fixed circle; b) The line $MN$ passes though a fixed point.

2006 Germany Team Selection Test, 3

Tags: modular arithmetic , number theory

Is the following statement true? For each positive integer $n$, we can find eight nonnegative integers $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ such that $n=\frac{2^a-2^b}{2^c-2^d}\cdot\frac{2^e-2^f}{2^g-2^h}$.

1987 IMO, 2

Tags: coordinate geometry , combinatorial geometry , modular arithmetic , geometry

Let $n\ge3$ be an integer. Prove that there is a set of $n$ points in the plane such that the distance between any two points is irrational and each set of three points determines a non-degenerate triangle with rational area.

2010 Contests, 3

Tags: combinatorics , modular arithmetic

Let $a_0, a_1, \ldots, a_9$ and $b_1 , b_2, \ldots,b_9$ be positive integers such that $a_9<b_9$ and $a_k \neq b_k, 1 \leq k \leq 8.$ In a cash dispenser/automated teller machine/ATM there are $n\geq a_9$ levs (Bulgarian national currency) and for each $1 \leq i \leq 9$ we can take $a_i$ levs from the ATM (if in the bank there are at least $a_i$ levs). Immediately after that action the bank puts $b_i$ levs in the ATM or we take $a_0$ levs. If we take $a_0$ levs from the ATM the bank doesn’t put any money in the ATM. Find all possible positive integer values of $n$ such that after finite number of takings money from the ATM there will be no money in it.

2011 ELMO Shortlist, 4

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

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]

2002 China Western Mathematical Olympiad, 2

Tags: inequalities , modular arithmetic , number theory

Given a positive integer $ n$, find all integers $ (a_{1},a_{2},\cdots,a_{n})$ satisfying the following conditions: $ (1): a_{1}\plus{}a_{2}\plus{}\cdots\plus{}a_{n}\ge n^2;$ $ (2): a_{1}^2\plus{}a_{2}^2\plus{}\cdots\plus{}a_{n}^2\le n^3\plus{}1.$

2013 China Western Mathematical Olympiad, 1

Tags: modular arithmetic , number theory

Does there exist any integer $a,b,c$ such that $a^2bc+2,ab^2c+2,abc^2+2$ are perfect squares?

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]

2014 NIMO Problems, 6

Tags: modular arithmetic , linear algebra , matrix

We know $\mathbb Z_{210} \cong \mathbb Z_2 \times \mathbb Z_3 \times \mathbb Z_5 \times \mathbb Z_7$. Moreover,\begin{align*} 53 & \equiv 1 \pmod{2} \\ 53 & \equiv 2 \pmod{3} \\ 53 & \equiv 3 \pmod{5} \\ 53 & \equiv 4 \pmod{7}. \end{align*} Let \[ M = \left( \begin{array}{ccc} 53 & 158 & 53 \\ 23 & 93 & 53 \\ 50 & 170 & 53 \end{array} \right). \] Based on the above, find $\overline{(M \mod{2})(M \mod{3})(M \mod{5})(M \mod{7})}$.

2013 All-Russian Olympiad, 3

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

Find all positive integers $k$ such that for the first $k$ prime numbers $2, 3, \ldots, p_k$ there exist positive integers $a$ and $n>1$, such that $2\cdot 3\cdot\ldots\cdot p_k - 1=a^n$. [i]V. Senderov[/i]

2013 National Olympiad First Round, 18

Tags: modular arithmetic

What is remainder when the sum \[\binom{2013}{1}+2013\binom{2013}{3} + 2013^2\binom{2013}{5} + \dots + 2013^{1006}\binom{2013}{2013}\] is divided by $41$? $ \textbf{(A)}\ 20 \qquad\textbf{(B)}\ 14 \qquad\textbf{(C)}\ 7 \qquad\textbf{(D)}\ 1 \qquad\textbf{(E)}\ \text{None} $

2004 Germany Team Selection Test, 2

Tags: modular arithmetic , induction , number theory

Find all pairs of positive integers $\left(n;\;k\right)$ such that $n!=\left( n+1\right)^{k}-1$.

1984 AIME Problems, 12

Tags: reflection , function , modular arithmetic , geometric transformation , geometry , floor function

A function $f$ is defined for all real numbers and satisfies \[f(2 + x) = f(2 - x)\qquad\text{and}\qquad f(7 + x) = f(7 - x)\] for all real $x$. If $x = 0$ is a root of $f(x) = 0$, what is the least number of roots $f(x) = 0$ must have in the interval $-1000 \le x \le 1000$?

2010 Tuymaada Olympiad, 2

Tags: number theory , modular arithmetic

We have a number $n$ for which we can find 5 consecutive numbers, none of which is divisible by $n$, but their product is. Show that we can find 4 consecutive numbers, none of which is divisible by $n$, but their product is.

2005 Romania Team Selection Test, 1

Tags: number theory , modular arithmetic , induction

Solve the equation $3^x=2^xy+1$ in positive integers.

2011 Turkey Team Selection Test, 3

Tags: number theory , modular arithmetic , function , induction

Let $p$ be a prime, $n$ be a positive integer, and let $\mathbb{Z}_{p^n}$ denote the set of congruence classes modulo $p^n.$ Determine the number of functions $f: \mathbb{Z}_{p^n} \to \mathbb{Z}_{p^n}$ satisfying the condition \[ f(a)+f(b) \equiv f(a+b+pab) \pmod{p^n} \] for all $a,b \in \mathbb{Z}_{p^n}.$

2012 EGMO, 8

Tags: complex number , modular arithmetic , combinatorics

A [i]word[/i] is a finite sequence of letters from some alphabet. A word is [i]repetitive[/i] if it is a concatenation of at least two identical subwords (for example, $ababab$ and $abcabc$ are repetitive, but $ababa$ and $aabb$ are not). Prove that if a word has the property that swapping any two adjacent letters makes the word repetitive, then all its letters are identical. (Note that one may swap two adjacent identical letters, leaving a word unchanged.) [i]Romania (Dan Schwarz)[/i]

2013 Princeton University Math Competition, 7

Tags: modular arithmetic

Evaluate \[\sqrt{2013+276\sqrt{2027+278\sqrt{2041+280\sqrt{2055+\ldots}}}}\]

2007 IMC, 4

Tags: inequalities , matrix , linear algebra , trigonometry , modular arithmetic , algebra , induction

Let $ n > 1$ be an odd positive integer and $ A = (a_{ij})_{i, j = 1..n}$ be the $ n \times n$ matrix with \[ a_{ij}= \begin{cases}2 & \text{if }i = j \\ 1 & \text{if }i-j \equiv \pm 2 \pmod n \\ 0 & \text{otherwise}\end{cases}.\] Find $ \det A$.

2013 AMC 8, 1

Tags: modular arithmetic

Danica wants to arrange her model cars in rows with exactly 6 cars in each row. She now has 23 model cars. What is the smallest number of additional cars she must buy in order to be able to arrange all her cars this way? $\textbf{(A)}\ 1 \qquad \textbf{(B)}\ 2 \qquad \textbf{(C)}\ 3 \qquad \textbf{(D)}\ 4 \qquad \textbf{(E)}\ 5$