Olympiad problems

2010 Serbia National Math Olympiad, 3

Let $a_0$ and $a_n$ be different divisors of a natural number $m$, and $a_0, a_1, \ldots, a_n$ be a sequence of natural numbers such that it satisfies \[a_{i+1} = |a_i\pm a_{i-1}|\text{ for }0 < i < n\] If $gcd(a_0,a_1,\ldots, a_n) = 1$, show that there exists a term of the sequence that is smaller than $\sqrt{m}$ . [i]Proposed by Dusan Djukic[/i]

2002 Hungary-Israel Binational, 3

Tags: number theory unsolved , number theory

Let $p \geq 5$ be a prime number. Prove that there exists a positive integer $a < p-1$ such that neither of $a^{p-1}-1$ and $(a+1)^{p-1}-1$ is divisible by $p^{2}$ .

1989 IMO Longlists, 31

Tags: induction , number theory unsolved , number theory

Let $ n$ be a positive integer. Show that \[ \left(\sqrt{2} \plus{} 1 \right)^n \equal{} \sqrt{m} \plus{} \sqrt{m\minus{}1}\] for some positive integer $ m.$

1992 Taiwan National Olympiad, 6

Tags: inequalities , number theory unsolved , number theory

Find the greatest positive integer $A$ with the following property: For every permutation of $\{1001,1002,...,2000\}$ , the sum of some ten consecutive terms is great than or equal to $A$.

2011 Postal Coaching, 2

Tags: modular arithmetic , number theory unsolved , number theory

Let $S(k)$ denote the digit-sum of a positive integer $k$(in base $10$). Determine the smallest positive integer $n$ such that \[S(n^2 ) = S(n) - 7\]

2005 MOP Homework, 6

Tags: arithmetic sequence , number theory unsolved , number theory

Let $a_1=0$, $a_2=1$, and $a_{n+2}=a_{n+1}+a_n$ for all positive integers $n$. Show that there exists an increasing infinite arithmetic progression of integers, which has no number in common in the sequence $\{a_n\}_{n \ge 0}$.

2001 IberoAmerican, 1

Tags: modular arithmetic , number theory unsolved , number theory

We say that a natural number $n$ is [i]charrua[/i] if it satisfy simultaneously the following conditions: - Every digit of $n$ is greater than 1. - Every time that four digits of $n$ are multiplied, it is obtained a divisor of $n$ Show that every natural number $k$ there exists a [i]charrua[/i] number with more than $k$ digits.

2007 Kazakhstan National Olympiad, 3

Tags: modular arithmetic , number theory unsolved , number theory

Let $p$ be a prime such that $2^{p-1}\equiv 1 \pmod{p^2}$. Show that $(p-1)(p!+2^n)$ has at least three distinct prime divisors for each $n\in \mathbb{N}$ .

2010 Iran MO (2nd Round), 1

Tags: algorithm , number theory , Euclidean algorithm , number theory unsolved

Let $a,b$ be two positive integers and $a>b$.We know that $\gcd(a-b,ab+1)=1$ and $\gcd(a+b,ab-1)=1$. Prove that $(a-b)^2+(ab+1)^2$ is not a perfect square.

1996 Canada National Olympiad, 5

Tags: function , LaTeX , number theory unsolved , number theory

Let $r_1$, $r_2$, $\ldots$, $r_m$ be a given set of $m$ positive rational numbers such that $\sum_{k=1}^m r_k = 1$. Define the function $f$ by $f(n)= n-\sum_{k=1}^m \: [r_k n]$ for each positive integer $n$. Determine the minimum and maximum values of $f(n)$. Here ${\ [ x ]}$ denotes the greatest integer less than or equal to $x$.

2000 Kurschak Competition, 3

Tags: pigeonhole principle , modular arithmetic , number theory unsolved , number theory

Let $k\ge 0$ be an integer and suppose the integers $a_1,a_2,\dots,a_n$ give at least $2k$ different residues upon division by $(n+k)$. Show that there are some $a_i$ whose sum is divisible by $n+k$.

2007 Federal Competition For Advanced Students, Part 2, 1

Tags: number theory unsolved , number theory

For which non-negative integers $ a<2007$ the congruence $ x^2\plus{}a \equiv 0 \mod 2007$ has got exactly two different non-negative integer solutions? That means, that there exist exactly two different non-negative integers $ u$ and $ v$ less than $ 2007$, such that $ u^2\plus{}a$ and $ v^2\plus{}a$ are both divisible by $ 2007$.

1998 Iran MO (3rd Round), 1

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

Define the sequence $(x_n)$ by $x_0 = 0$ and for all $n \in \mathbb N,$ \[x_n=\begin{cases} x_{n-1} + (3^r - 1)/2,&\mbox{ if } n = 3^{r-1}(3k + 1);\\ x_{n-1} - (3^r + 1)/2, & \mbox{ if } n = 3^{r-1}(3k + 2).\end{cases}\] where $k \in \mathbb N_0, r \in \mathbb N$. Prove that every integer occurs in this sequence exactly once.

1993 APMO, 2

Tags: function , number theory unsolved , number theory

Find the total number of different integer values the function \[ f(x) = [x] + [2x] + [\frac{5x}{3}] + [3x] + [4x] \] takes for real numbers $x$ with $0 \leq x \leq 100$.

2005 MOP Homework, 3

Tags: modular arithmetic , number theory unsolved , number theory

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

1992 IMTS, 4

Tags: number theory unsolved , number theory

An international firm has 250 employees, each of whom speaks several languages. For each pair of employees, $(A,B)$, there is a language spoken by $A$ and not $B$, and there is another language spoken by $B$ but not $A$. At least how many languages must be spoken at the firm?

2010 Kyrgyzstan National Olympiad, 8

Tags: geometry , 3D geometry , number theory unsolved , number theory

Solve in none-negative integers ${x^3} + 7{x^2} + 35x + 27 = {y^3}$.

2006 China National Olympiad, 2

Tags: number theory unsolved , number theory

For positive integers $a_1,a_2 ,\ldots,a_{2006}$ such that $\frac{a_1}{a_2},\frac{a_2}{a_3},\ldots,\frac{a_{2005}}{a_{2006}}$ are pairwise distinct, find the minimum possible amount of distinct positive integers in the set$\{a_1,a_2,...,a_{2006}\}$.

2006 China Team Selection Test, 2

Tags: modular arithmetic , number theory unsolved , number theory

Prove that for any given positive integer $m$ and $n$, there is always a positive integer $k$ so that $2^k-m$ has at least $n$ different prime divisors.

2000 China Team Selection Test, 3

Tags: number theory unsolved , number theory

For positive integer $a \geq 2$, denote $N_a$ as the number of positive integer $k$ with the following property: the sum of squares of digits of $k$ in base a representation equals $k$. Prove that: a.) $N_a$ is odd; b.) For every positive integer $M$, there exist a positive integer $a \geq 2$ such that $N_a \geq M$.

2007 Federal Competition For Advanced Students, Part 1, 1

Tags: quadratics , number theory unsolved , number theory

In a quadratic table with $ 2007$ rows and $ 2007$ columns is an odd number written in each field. For $ 1\leq i\leq2007$ is $ Z_i$ the sum of the numbers in the $ i$-th row and for $ 1\leq j\leq2007$ is $ S_j$ the sum of the numbers in the $ j$-th column. $ A$ is the product of all $ Z_i$ and $ B$ the product of all $ S_j$. Show that $ A\plus{}B\neq0$

2013 ELMO Shortlist, 8

Tags: counting , distinguishability , modular arithmetic , algebra , polynomial , function , number theory unsolved

We define the [i]Fibonacci sequence[/i] $\{F_n\}_{n\ge0}$ by $F_0=0$, $F_1=1$, and for $n\ge2$, $F_n=F_{n-1}+F_{n-2}$; we define the [i]Stirling number of the second kind[/i] $S(n,k)$ as the number of ways to partition a set of $n\ge1$ distinguishable elements into $k\ge1$ indistinguishable nonempty subsets. For every positive integer $n$, let $t_n = \sum_{k=1}^{n} S(n,k) F_k$. Let $p\ge7$ be a prime. Prove that \[ t_{n+p^{2p}-1} \equiv t_n \pmod{p} \] for all $n\ge1$. [i]Proposed by Victor Wang[/i]

1978 IMO Longlists, 11

Tags: number theory , relatively prime , number theory unsolved

Find all natural numbers $n < 1978$ with the following property: If $m$ is a natural number, $1 < m < n$, and $(m, n) = 1$ (i.e., $m$ and $n$ are relatively prime), then $m$ is a prime number.

2003 CHKMO, 4

Tags: modular arithmetic , quadratics , number theory unsolved , number theory

Let $p$ be a prime number such that $p\equiv 1\pmod{4}$. Determine $\sum_{k=1}^{\frac{p-1}{2}}\left \lbrace \frac{k^2}{p} \right \rbrace$, where $\{x\}=x-[x]$.

2012 Czech-Polish-Slovak Match, 1

Tags: number theory , relatively prime , number theory unsolved

Given a positive integer $n$, let $\tau(n)$ denote the number of positive divisors of $n$ and $\varphi(n)$ denote the number of positive integers not exceeding $n$ that are relatively prime to $n$. Find all $n$ for which one of the three numbers $n,\tau(n), \varphi(n)$ is the arithmetic mean of the other two.