Olympiad problems

1996 Vietnam Team Selection Test, 2

For each positive integer $n$, let $f(n)$ be the maximal natural number such that: $2^{f(n)}$ divides $\sum^{\left\lfloor \frac{n - 1}{2}\right\rfloor}_{i=0} \binom{n}{2 \cdot i + 1} 3^i$. Find all $n$ such that $f(n) = 1996.$ [hide="old version"]For each positive integer $n$, let $f(n)$ be the maximal natural number such that: $2^{f(n)}$ divides $\sum^{n + 1/2}_{i=1} \binom{2 \cdot i + 1}{n}$. Find all $n$ such that $f(n) = 1996.$[/hide]

2004 South africa National Olympiad, 6

Tags: induction , number theory unsolved , number theory

The numbers $a_1,a_2$ and $a_3$ are distinct positive integers, such that (i) $a_1$ is a divisor of $a_2+a_3+a_2a_3$; (ii) $a_2$ is a divisor of $a_3+a_1+a_3a_1$; (iii) $a_3$ is a divisor of $a_1+a_2+a_1a_2$. Prove that $a_1,a_2$ and $a_3$ cannot all be prime.

2012 Kyrgyzstan National Olympiad, 1

Tags: number theory unsolved , number theory

Prove that $ n $ must be prime in order to have only one solution to the equation $\frac{1}{x}-\frac{1}{y}=\frac{1}{n}$, $x,y\in\mathbb{N}$.

1994 IberoAmerican, 1

Tags: number theory unsolved , number theory

A number $n$ is said to be [i]nice[/i] if it exists an integer $r>0$ such that the expression of $n$ in base $r$ has all its digits equal. For example, 62 and 15 are $\emph{nice}$ because 62 is 222 in base 5, and 15 is 33 in base 4. Show that 1993 is not [i]nice[/i], but 1994 is.

1995 Vietnam Team Selection Test, 2

Tags: modular arithmetic , number theory unsolved , number theory

For any nonnegative integer $ n$, let $ f(n)$ be the greatest integer such that $ 2^{f(n)} | n \plus{} 1$. A pair $ (n, p)$ of nonnegative integers is called nice if $ 2^{f(n)} > p$. Find all triples $ (n, p, q)$ of nonnegative integers such that the pairs $ (n, p)$, $ (p, q)$ and $ (n \plus{} p \plus{} q, n)$ are all nice.

2007 Estonia Math Open Senior Contests, 3

Tags: number theory unsolved , number theory

Let $ b$ be an even positive integer for which there exists a natural number n such that $ n>1$ and $ \frac{b^n\minus{}1}{b\minus{}1}$ is a perfect square. Prove that $ b$ is divisible by 8.

1984 IMO Longlists, 37

Tags: number theory unsolved , number theory

$(MOR 1)$ Denote by $[x]$ the greatest integer not exceeding $x$. For all real $k > 1$, define two sequences: \[a_n(k) = [nk]\text{ and } b_n(k) =\left[\frac{nk}{k - 1}\right]\] If $A(k) = \{a_n(k) : n \in\mathbb{N}\}$ and $B(k) = \{b_n(k) : n \in \mathbb{N}\}$, prove that $A(k)$ and $B(k)$ form a partition of $\mathbb{N}$ if and only if $k$ is irrational.

2014 Irish Math Olympiad, 2

Tags: number theory , number theory unsolved , Divisibility , induction

Prove that for $N>1$ that $(N^{2})^{2014} - (N^{11})^{106}$ is divisible by $N^6 + N^3 +1$ Is this just a proof by induction or is there a more elegant method? I don't think calculating $N = 2$ was expected.

2006 MOP Homework, 4

Tags: factorial , number theory unsolved , number theory

Let $n$ be a positive integer, and let $p$ be a prime number. Prove that if $p^p | n!$, then $p^{p+1} | n!$.

2007 China Team Selection Test, 3

Tags: least common multiple , number theory , relatively prime , number theory unsolved

Let $ n$ be a positive integer, let $ A$ be a subset of $ \{1, 2, \cdots, n\}$, satisfying for any two numbers $ x, y\in A$, the least common multiple of $ x$, $ y$ not more than $ n$. Show that $ |A|\leq 1.9\sqrt {n} \plus{} 5$.

1998 Taiwan National Olympiad, 5

Tags: number theory unsolved , number theory

For a positive integer $n$, let $\omega(n)$ denote the number of positive prime divisors of $n$. Find the smallest positive tinteger $k$ such that $2^{\omega(n)}\leq k\sqrt[4]{n}\forall n\in\mathbb{N}$.

2004 India IMO Training Camp, 2

Tags: number theory unsolved , number theory

Find all triples $(x,y,n)$ of positive integers such that \[ (x+y)(1+xy) = 2^{n} \]

2007 Olympic Revenge, 1

Tags: function , search , number theory unsolved , number theory

Let $a$, $b$, $n$ be positive integers with $a,b > 1$ and $\gcd(a,b) = 1$. Prove that $n$ divides $\phi\left(a^{n}+b^{n}\right)$.

2006 Tuymaada Olympiad, 4

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

For a positive integer, we define it's [i]set of exponents[/i] the unordered list of all the exponents of the primes, in it`s decomposition. For example, $18=2\cdot 3^{2}$ has it`s set of exponents $1,2$ and $300=2^{2}\cdot 3\cdot 5^{2}$ has it`s set of exponents $1,2,2$. There are given two arithmetical progressions $\big(a_{n}\big)_{n}$ and $\big(b_{n}\big)_{n}$, such that for any positive integer $n$, $a_{n}$ and $b_{n}$ have the same set of exponents. Prove that the progressions are proportional (that is, there is $k$ such that $a_{n}=kb_{n}$ for any $n$). [i]Proposed by A. Golovanov[/i]

2005 Uzbekistan National Olympiad, 3

Tags: modular arithmetic , number theory unsolved , number theory

Find the last five digits of $1^{100}+2^{100}+3^{100}+...+999999^{100}$

2013 Indonesia MO, 4

Tags: modular arithmetic , number theory unsolved , number theory

Suppose $p > 3$ is a prime number and \[S = \sum_{2 \le i < j < k \le p-1} ijk\] Prove that $S+1$ is divisible by $p$.

2001 Tournament Of Towns, 1

Tags: greatest common divisor , number theory unsolved , number theory

Do there exist postive integers $a_1<a_2<\cdots<a_{100}$ such that for $2\le k\le100$ the greatest common divisor of $a_{k-1}$ and $a_k$ is greater than the greatest common divisor of $a_k$ and $a_{k+1}$?

1992 Kurschak Competition, 2

Tags: modular arithmetic , number theory unsolved , number theory

For any positive integer $k$ define $f_1(k)$ as the square of the digital sum of $k$ in the decimal system, and $f_{n}(k)=f_1(f_{n-1}(k))$ $\forall n>1$. Compute $f_{1992}(2^{1991})$.

1994 Hong Kong TST, 3

Tags: number theory unsolved , number theory

Let $m$ and $n$ be positive integers where $m$ has $d$ digits in base ten and $d\leq n$. Find the sum of all the digits (in base ten) of the product $(10^n-1)m$.

2005 Germany Team Selection Test, 1

Tags: Putnam , inequalities , number theory unsolved , number theory

Find the smallest positive integer $n$ with the following property: For any integer $m$ with $0 < m < 2004$, there exists an integer $k$ such that \[\frac{m}{2004}<\frac{k}{n}<\frac{m+1}{2005}.\]

2007 ISI B.Stat Entrance Exam, 10

Tags: number theory unsolved , number theory

Let $A$ be a set of positive integers satisfying the following properties: (i) if $m$ and $n$ belong to $A$, then $m+n$ belong to $A$; (ii) there is no prime number that divides all elements of $A$. (a) Suppose $n_1$ and $n_2$ are two integers belonging to $A$ such that $n_2-n_1 >1$. Show that you can find two integers $m_1$ and $m_2$ in $A$ such that $0< m_2-m_1 < n_2-n_1$ (b) Hence show that there are two consecutive integers belonging to $A$. (c) Let $n_0$ and $n_0+1$ be two consecutive integers belonging to $A$. Show that if $n\geq n_0^2$ then $n$ belongs to $A$.

2011 China Team Selection Test, 2

Tags: ceiling function , floor function , number theory unsolved , number theory

Let $a_1,a_2,\ldots,a_n,\ldots$ be any permutation of all positive integers. Prove that there exist infinitely many positive integers $i$ such that $\gcd(a_i,a_{i+1})\leq \frac{3}{4} i$.

2004 Postal Coaching, 15

Tags: function , number theory unsolved , number theory

Show that for each integer $a$, there is a unique decomposition \[ a = \sum_{j=0}^{n} d_j 2^j , d_j \in (-1,0,1) \] such that no two consecutive $d_j$'s are nonzero. Show further that if $f$ is nondecreasing function from the set of all non-negative integers in to the set of all non-negative real numbers, and if $a = \sum_{j=0}^{n} c_j 2^j$ is any other decomposition of $a$ with $c_j \in (-1,0,1)$ , then \[ \sum_{j=0}^{n} |d_j| f(j) \leq \sum_{j=0}^{n} |c_j| f(j) \]

2005 India IMO Training Camp, 2

Tags: number theory unsolved , number theory

Given real numbers $a,\alpha,\beta, \sigma \ and \ \varrho$ s.t. $\sigma, \varrho > 0$ and $\sigma \varrho = \frac{1}{16}$, prove that there exist integers $x$ and $y$ s.t. \[ - \sigma \leq (x+\alpha_(ax + y + \beta ) \leq \varrho \]

1998 Canada National Olympiad, 1

Tags: number theory unsolved , number theory

Determine the number of real solutions $a$ to the equation: \[ \left[\,\frac{1}{2}\;a\,\right]+\left[\,\frac{1}{3}\;a\,\right]+\left[\,\frac{1}{5}\;a\,\right] = a. \] Here, if $x$ is a real number, then $[\,x\,]$ denotes the greatest integer that is less than or equal to $x$.