Olympiad problems

2012 ELMO Shortlist, 6

Tags: number theory , least common multiple , inequalities , induction , function , pigeonhole principle , logarithm

Consider a directed graph $G$ with $n$ vertices, where $1$-cycles and $2$-cycles are permitted. For any set $S$ of vertices, let $N^{+}(S)$ denote the out-neighborhood of $S$ (i.e. set of successors of $S$), and define $(N^{+})^k(S)=N^{+}((N^{+})^{k-1}(S))$ for $k\ge2$. For fixed $n$, let $f(n)$ denote the maximum possible number of distinct sets of vertices in $\{(N^{+})^k(X)\}_{k=1}^{\infty}$, where $X$ is some subset of $V(G)$. Show that there exists $n>2012$ such that $f(n)<1.0001^n$. [i]Linus Hamilton.[/i]

2013 Mexico National Olympiad, 5

Tags: inequalities , number theory

A pair of integers is special if it is of the form $(n, n-1)$ or $(n-1, n)$ for some positive integer $n$. Let $n$ and $m$ be positive integers such that pair $(n, m)$ is not special. Show $(n, m)$ can be expressed as a sum of two or more different special pairs if and only if $n$ and $m$ satisfy the inequality $ n+m\geq (n-m)^2 $. Note: The sum of two pairs is defined as $ (a, b)+(c, d) = (a+c, b+d) $.

2004 Italy TST, 2

Tags: induction , least common multiple , arithmetic sequence , number theory

A positive integer $n$ is said to be a [i]perfect power[/i] if $n=a^b$ for some integers $a,b$ with $b>1$. $(\text{a})$ Find $2004$ perfect powers in arithmetic progression. $(\text{b})$ Prove that perfect powers cannot form an infinite arithmetic progression.

2017 BMT Spring, 4

Tags: number theory

What is the greatest multiple of $9$ that can be formed by using each of the digits in the set $\{1, 3,5, 7, 9\}$ at most once.

2019 IMO Shortlist, N6

Tags: number theory , floor function

Let $H = \{ \lfloor i\sqrt{2}\rfloor : i \in \mathbb Z_{>0}\} = \{1,2,4,5,7,\dots \}$ and let $n$ be a positive integer. Prove that there exists a constant $C$ such that, if $A\subseteq \{1,2,\dots, n\}$ satisfies $|A| \ge C\sqrt{n}$, then there exist $a,b\in A$ such that $a-b\in H$. (Here $\mathbb Z_{>0}$ is the set of positive integers, and $\lfloor z\rfloor$ denotes the greatest integer less than or equal to $z$.)

2022 AMC 12/AHSME, 4

Tags: number theory

The least common multiple of a positive integer $n$ and 18 is 180, and the greatest common divisor of $n$ and 45 is 15. What is the sum of the digits of $n$? $\textbf{(A) }3\qquad\textbf{(B) }6\qquad\textbf{(C) }8\qquad\textbf{(D) }9\qquad\textbf{(E) }12$

1993 Miklós Schweitzer, 2

Tags: number theory

Let A be a subset of natural numbers and let k , r be positive integers. Suppose that for any r different elements selected from A , their greatest common divisor has at most k different prime factors. Prove that A can be partitioned into B and C , where any element of B has at most k + 1 different prime divisors and $$\sum_{n\in C} \frac{1}{n} <\infty$$

2017 Balkan MO Shortlist, C2

Tags: lattice points , combinatorics , number theory , congruent triangles , coloring

Let $n,a,b,c$ be natural numbers. Every point on the coordinate plane with integer coordinates is colored in one of $n$ colors. Prove there exists $c$ triangles whose vertices are colored in the same color, which are pairwise congruent, and which have a side whose lenght is divisible by $a$ and a side whose lenght is divisible by $b$.

2019 Malaysia National Olympiad, 4

Tags: number theory

Let $A=\{1,2,...,100\}$ and $f(k), k\in N$ be the size of the largest subset of $A$ such that no two elements differ by $k$. How many solutions are there to $f(k)=50$?

2013 BMT Spring, P2

Tags: number theory

Let $p$ be an odd prime, and let $(p^p)!=mp^k$ for some positive integers $m$ and $k$. Find in terms of $p$ the number of ordered pairs $(m,k)$ satisfying $m+k\equiv0\pmod p$.

2024-IMOC, N3

Tags: number theory

Find all positive integers $n$ such that $$n(2^n-1)$$ is a perfect square

2023 Hong Kong Team Selection Test, Problem 4

Tags: number theory

A two digit number $s$ is special if $s$ is the common two leading digits of the decimal expansion of $4^n$ and $5^n$, where $n$ is a certain positive integer. Given that there are two special number, find these two special numbers.

2013 National Olympiad First Round, 10

Tags: number theory , relatively prime

How many positive integers $n$ are there such that there are exactly $20$ positive odd integers that are less than $n$ and relatively prime with $n$? $ \textbf{(A)}\ 5 \qquad\textbf{(B)}\ 4 \qquad\textbf{(C)}\ 3 \qquad\textbf{(D)}\ 2 \qquad\textbf{(E)}\ \text{None of above} $

2014 Belarus Team Selection Test, 3

Tags: number theory , prime divisor , polynomial

Prove that there exist infinitely many positive integers $n$ such that the largest prime divisor of $n^4 + n^2 + 1$ is equal to the largest prime divisor of $(n+1)^4 + (n+1)^2 +1$.

2012 Grigore Moisil Intercounty, 2

Tags: base 10 , number theory , base 10 number theory , inequalities

[b]a)[/b] Prove that $$ k+\frac{1}{2}-\frac{1}{8k}<\sqrt{k^2+k}<k+\frac{1}{2}-\frac{1}{8k}+\frac{1}{16k^2} , $$ for any natural number $ k. $ [b]b)[/b] Prove that there exists four numbers $ \alpha,\beta,\gamma,\delta\in\{0,1,2,3,4,5,6,7,8,9\} $ such that $$ \left\lfloor\sum_{k=1}^{2012} \sqrt{k(k+1)\left( k^2+k+1 \right)}\right\rfloor =\underbrace{\ldots\alpha \beta\gamma\delta}_{\text{decimal form}} $$ and $ \alpha +\delta =\gamma . $

2001 APMO, 1

Tags: induction , number theory , easy

For a positive integer $n$ let $S(n)$ be the sum of digits in the decimal representation of $n$. Any positive integer obtained by removing several (at least one) digits from the right-hand end of the decimal representation of $n$ is called a [i]stump[/i] of $n$. Let $T(n)$ be the sum of all stumps of $n$. Prove that $n=S(n)+9T(n)$.

1992 Mexico National Olympiad, 4

Tags: number theory , divisor

Show that $1 + 11^{11} + 111^{111} + 1111^{1111} +...+ 1111111111^{1111111111}$ is divisible by $100$.

2025 Israel National Olympiad (Gillis), P7

Tags: algebra , number theory

For a positive integer $n$, let $A_n$ be the set of quadruplets $(a,b,c,d)$ of integers, satisfying the following properties simultaneously: [list] [*] $0\le a\le c\le n,$ [*] $0\le b\le d\le n,$ [*] $c+d>n,$ and [*] $bc=ad+1.$ [/list] Moreover, define $$\alpha_n=\sum_{(a,b,c,d)\in A_n}\frac{1}{ab+cd}.$$ Find all real numbers $t$ such that $\alpha_n>t$ for every positive integer $n$.

2007 Baltic Way, 20

Tags: geometry , search , function , number theory

Let $a$ and $b$ be positive integers, $b<a$, such that $a^3+b^3+ab$ is divisible by $ab(a-b)$. Prove that $ab$ is a perfect cube.

1992 French Mathematical Olympiad, Problem 5

Tags: number theory , floor function

Determine the number of digits $1$ in the integer part of $\frac{10^{1992}}{10^{83}+7}$.

2023 China Girls Math Olympiad, 7

Tags: number theory

Let $p$ be an odd prime. Suppose that positive integers $a,b,m,r$ satisfy $p\nmid ab$ and $ab > m^2$. Prove that there exists at most one pair of coprime positive integers $(x,y)$ such that $ax^2+by^2=mp^r$.

2004 Tournament Of Towns, 1

Tags: arithmetic progression , sum , power of 2 , number theory

The sum of all terms of a finite arithmetical progression of integers is a power of two. Prove that the number of terms is also a power of two.

2016 Romania Team Selection Tests, 4

Tags: number theory

Determine the integers $k\geq 2$ for which the sequence $\Big\{ \binom{2n}{n} \pmod{k}\Big\}_{n\in \mathbb{Z}_{\geq 0}}$ is eventually periodic.

2023 NMTC Junior, P7

Tags: number theory

Let $n$ be a positive integer; and $S(n)$ denote the sum of all digits in the decimal representation of $n$. A positive integer obtained by removing one or several digits from the right hand end of the decimal representation of $n$ is called the [i]truncation[/i] of $n$. The sum of all truncations of $n$ is denoted as $T(n)$. Prove that $S(n)+9T(n)=n$

1991 Poland - Second Round, 3

Tags: number theory

There are positive integers $ a $, $ b $, $ c $, $ d $, $ e $, $ f $ such that $ a+b = c+d = e+f = 101 $. Prove that the number $ \frac{ace}{bdf} $ cannot be written as a fraction $ \frac{m}{n} $ where $ m $, $ n $ are positive integers with a sum less than $ 101 $.