Olympiad problems

1980 Bundeswettbewerb Mathematik, 1

Six free cells are given in a row. Players $A$ and $B$ alternately write digits from $0$ to $9$ in empty cells, with $A$ starting. When all the cells are filled, one considers the obtained six-digit number $z$. Player $B$ wins if $z$ is divisible by a given natural number $n$, and loses otherwise. For which values of $n$ not exceeding $20$ can $B$ win independently of his opponent’s moves?

2022 China Team Selection Test, 3

Tags: inequalities , number theory , divisibility

Let $a_1, a_2, \ldots, a_n$ be $n$ positive integers that are not divisible by each other, i.e. for any $i \neq j$, $a_i$ is not divisible by $a_j$. Show that \[ a_1+a_2+\cdots+a_n \ge 1.1n^2-2n. \] [i]Note:[/i] A proof of the inequality when $n$ is sufficient large will be awarded points depending on your results.

2021 China Team Selection Test, 2

Tags: number theory , number sequence , divisibility

Given distinct positive integer $ a_1,a_2,…,a_{2020} $. For $ n \ge 2021 $, $a_n$ is the smallest number different from $a_1,a_2,…,a_{n-1}$ which doesn't divide $a_{n-2020}...a_{n-2}a_{n-1}$. Proof that every number large enough appears in the sequence.

2018 Dutch BxMO TST, 3

Tags: number theory , prime number , divisibility

Let $p$ be a prime number. Prove that it is possible to choose a permutation $a_1, a_2,...,a_p$ of $1,2,...,p$ such that the numbers $a_1, a_1a_2, a_1a_2a_3,..., a_1a_2a_3...a_p$ all have different remainder upon division by $p$.

1962 IMO Shortlist, 1

Tags: number theory , decimal representation , divisibility

Find the smallest natural number $n$ which has the following properties: a) Its decimal representation has a 6 as the last digit. b) If the last digit 6 is erased and placed in front of the remaining digits, the resulting number is four times as large as the original number $n$.

2024 Francophone Mathematical Olympiad, 4

Tags: divisibility , sequence , number theory

Find all integers $n \ge 2$ for which there exists $n$ integers $a_1,a_2,\dots,a_n \ge 2$ such that for all indices $i \ne j$, we have $a_i \mid a_j^2+1$.

2009 Brazil Team Selection Test, 1

Tags: combinatorics , permutation , divisibility

Let $n \in \mathbb N$ and $A_n$ set of all permutations $(a_1, \ldots, a_n)$ of the set $\{1, 2, \ldots , n\}$ for which \[k|2(a_1 + \cdots+ a_k), \text{ for all } 1 \leq k \leq n.\] Find the number of elements of the set $A_n$. [i]Proposed by Vidan Govedarica, Serbia[/i]

2020 Iran MO (3rd Round), 1

Tags: number theory , divisibility , totient function

Find all positive integers $n$ such that the following holds. $$\tau(n)|2^{\sigma(n)}-1$$

1990 IMO Longlists, 75

Tags: number theory , divisibility , binary representation , minimization

Let $ n$ be a composite natural number and $ p$ a proper divisor of $ n.$ Find the binary representation of the smallest natural number $ N$ such that \[ \frac{(1 \plus{} 2^p \plus{} 2^{n\minus{}p})N \minus{} 1}{2^n}\] is an integer.

1969 IMO Longlists, 24

Tags: algebra , polynomial , number theory , divisibility

$(GBR 1)$ The polynomial $P(x) = a_0x^k + a_1x^{k-1} + \cdots + a_k$, where $a_0,\cdots, a_k$ are integers, is said to be divisible by an integer $m$ if $P(x)$ is a multiple of $m$ for every integral value of $x$. Show that if $P(x)$ is divisible by $m$, then $a_0 \cdot k!$ is a multiple of $m$. Also prove that if $a, k,m$ are positive integers such that $ak!$ is a multiple of $m$, then a polynomial $P(x)$ with leading term $ax^k$can be found that is divisible by $m.$

1977 IMO, 2

Tags: number theory , additive number theory , remainder , divisibility

Let $a,b$ be two natural numbers. When we divide $a^2+b^2$ by $a+b$, we the the remainder $r$ and the quotient $q.$ Determine all pairs $(a, b)$ for which $q^2 + r = 1977.$

1998 IMO Shortlist, 1

Tags: number theory , divisibility , polynomial

Determine all pairs $(x,y)$ of positive integers such that $x^{2}y+x+y$ is divisible by $xy^{2}+y+7$.

2019 Czech and Slovak Olympiad III A, 3

Tags: number theory , divisibility , perfect power

Let $a,b,c,n$ be positive integers such that the following conditions hold (i) numbers $a,b,c,a+b+c$ are pairwise coprime, (ii) number $(a+b)(b+c)(c+a)(a+b+c)(ab+bc+ca)$ is a perfect $n$-th power. Prove, that the product $abc$ can be expressed as a difference of two perfect $n$-th powers.

1946 Putnam, B5

Tags: ceiling function , divisibility

Show that $\lceil (\sqrt{3}+1)^{2n})\rceil$ is divisible by $2^{n+1}.$

2004 German National Olympiad, 3

Tags: number theory , divisibility , digit , sum of digits

Prove that for every positive integer $n$ there is an $n$-digit number $z$ with none of its digits $0$ and such that $z$ is divisible by its sum of digits.

2021 SAFEST Olympiad, 2

Tags: number theory , sequence , divisibility

Given a positive integer $k$ show that there exists a prime $p$ such that one can choose distinct integers $a_1,a_2\cdots, a_{k+3} \in \{1, 2, \cdots ,p-1\}$ such that p divides $a_ia_{i+1}a_{i+2}a_{i+3}-i$ for all $i= 1, 2, \cdots, k$. [i]South Africa [/i]

1990 IMO Longlists, 65

Tags: pigeonhole principle , number theory , decimal representation , divisibility , multiple , digit

Prove that every integer $ k$ greater than 1 has a multiple that is less than $ k^4$ and can be written in the decimal system with at most four different digits.

2022 Olimphíada, 1

Tags: divisibility , prime

Let $p,q$ prime numbers such that $$p+q \mid p^3-q^3$$ Show that $p=q$.

1998 IMO Shortlist, 3

Tags: modular arithmetic , pigeonhole principle , number theory , divisibility , combinatorics

Determine the smallest integer $n\geq 4$ for which one can choose four different numbers $a,b,c$ and $d$ from any $n$ distinct integers such that $a+b-c-d$ is divisible by $20$.

2017 Taiwan TST Round 2, 3

Tags: number theory , function , divisibility

Denote by $\mathbb{N}$ the set of all positive integers. Find all functions $f:\mathbb{N}\rightarrow \mathbb{N}$ such that for all positive integers $m$ and $n$, the integer $f(m)+f(n)-mn$ is nonzero and divides $mf(m)+nf(n)$. [i]Proposed by Dorlir Ahmeti, Albania[/i]

2019 India PRMO, 8

Tags: algebra , number theory , divisibility

Let $F_k(a,b)=(a+b)^k-a^k-b^k$ and let $S={1,2,3,4,5,6,7,8,9,10}$. For how many ordered pairs $(a,b)$ with $a,b\in S$ and $a\leq b$ is $\frac{F_5(a,b)}{F_3(a,b)}$ an integer?

2018 Pan-African Shortlist, N2

Tags: number theory , divisibility , digit

A positive integer is called special if its digits can be arranged to form an integer divisible by $4$. How many of the integers from $1$ to $2018$ are special?

1966 IMO Longlists, 42

Tags: sequence , divisibility , number theory

Given a finite sequence of integers $a_{1},$ $a_{2},$ $...,$ $a_{n}$ for $n\geq 2.$ Show that there exists a subsequence $a_{k_{1}},$ $a_{k_{2}},$ $...,$ $a_{k_{m}},$ where $1\leq k_{1}\leq k_{2}\leq...\leq k_{m}\leq n,$ such that the number $a_{k_{1}}^{2}+a_{k_{2}}^{2}+...+a_{k_{m}}^{2}$ is divisible by $n.$ [b]Note by Darij:[/b] Of course, the $1\leq k_{1}\leq k_{2}\leq ...\leq k_{m}\leq n$ should be understood as $1\leq k_{1}<k_{2}<...<k_{m}\leq n;$ else, we could take $m=n$ and $k_{1}=k_{2}=...=k_{m},$ so that the number $a_{k_{1}}^{2}+a_{k_{2}}^{2}+...+a_{k_{m}}^{2}=n^{2}a_{k_{1}}^{2}$ will surely be divisible by $n.$

2003 Federal Math Competition of S&M, Problem 1

Tags: number theory , floor function , divisibility , recursion

Prove that the number $\left\lfloor\left(5+\sqrt{35}\right)^{2n-1}\right\rfloor$ is divisible by $10^n$ for each $n\in\mathbb N$.

1992 IMO Shortlist, 19

Tags: algebra , polynomial , number theory , divisibility , coefficient

Let $ f(x) \equal{} x^8 \plus{} 4x^6 \plus{} 2x^4 \plus{} 28x^2 \plus{} 1.$ Let $ p > 3$ be a prime and suppose there exists an integer $ z$ such that $ p$ divides $ f(z).$ Prove that there exist integers $ z_1, z_2, \ldots, z_8$ such that if \[ g(x) \equal{} (x \minus{} z_1)(x \minus{} z_2) \cdot \ldots \cdot (x \minus{} z_8),\] then all coefficients of $ f(x) \minus{} g(x)$ are divisible by $ p.$