Olympiad problems

2001 Mexico National Olympiad, 4

For positive integers $n, m$ define $f(n,m)$ as follows. Write a list of $ 2001$ numbers $a_i$, where $a_1 = m$, and $a_{k+1}$ is the residue of $a_k^2$ $mod \, n$ (for $k = 1, 2,..., 2000$). Then put $f(n,m) = a_1-a_2 + a_3 -a_4 + a_5- ... + a_{2001}$. For which $n \ge 5$ can we find m such that $2 \le m \le n/2$ and $f(m,n) > 0$?

1992 IMO Longlists, 43

Tags: relatively prime , series summation , number theoretic functions , floor function , number theory

Find the number of positive integers $n$ satisfying $\phi(n) | n$ such that \[\sum_{m=1}^{\infty} \left( \left[ \frac nm \right] - \left[\frac{n-1}{m} \right] \right) = 1992\] What is the largest number among them? As usual, $\phi(n)$ is the number of positive integers less than or equal to $n$ and relatively prime to $n.$

1998 IMO, 3

Tags: number theoretic functions , prime factorization , divisor , number theory

For any positive integer $n$, let $\tau (n)$ denote the number of its positive divisors (including 1 and itself). Determine all positive integers $m$ for which there exists a positive integer $n$ such that $\frac{\tau (n^{2})}{\tau (n)}=m$.

1986 China Team Selection Test, 3

Tags: decimal representation , number theoretic functions , digit , algebra

Given a positive integer $A$ written in decimal expansion: $(a_{n},a_{n-1}, \ldots, a_{0})$ and let $f(A)$ denote $\sum^{n}_{k=0} 2^{n-k}\cdot a_k$. Define $A_1=f(A), A_2=f(A_1)$. Prove that: [b]I.[/b] There exists positive integer $k$ for which $A_{k+1}=A_k$. [b]II.[/b] Find such $A_k$ for $19^{86}.$

1989 IMO Longlists, 35

Tags: modular arithmetic , summation , number theoretic functions , number theory

Define sequence $ (a_n)$ by $ \sum_{d|n} a_d \equal{} 2^n.$ Show that $ n|a_n.$

1992 IMO Longlists, 11

Tags: function , relatively prime , number theoretic functions , number theory , inequalities

Let $\phi(n,m), m \neq 1$, be the number of positive integers less than or equal to $n$ that are coprime with $m.$ Clearly, $\phi(m,m) = \phi(m)$, where $\phi(m)$ is Euler’s phi function. Find all integers $m$ that satisfy the following inequality: \[\frac{\phi(n,m)}{n} \geq \frac{\phi(m)}{m}\] for every positive integer $n.$

1986 China Team Selection Test, 3

Tags: number theoretic functions , decimal representation , digit , algebra

Given a positive integer $A$ written in decimal expansion: $(a_{n},a_{n-1}, \ldots, a_{0})$ and let $f(A)$ denote $\sum^{n}_{k=0} 2^{n-k}\cdot a_k$. Define $A_1=f(A), A_2=f(A_1)$. Prove that: [b]I.[/b] There exists positive integer $k$ for which $A_{k+1}=A_k$. [b]II.[/b] Find such $A_k$ for $19^{86}.$

1998 IMO Shortlist, 6

Tags: number theory , number theoretic functions , prime factorization , divisor

For any positive integer $n$, let $\tau (n)$ denote the number of its positive divisors (including 1 and itself). Determine all positive integers $m$ for which there exists a positive integer $n$ such that $\frac{\tau (n^{2})}{\tau (n)}=m$.

1989 IMO Shortlist, 11

Tags: modular arithmetic , summation , number theoretic functions , number theory

Define sequence $ (a_n)$ by $ \sum_{d|n} a_d \equal{} 2^n.$ Show that $ n|a_n.$

2023 Thailand Online MO, 5

Tags: number theory , arithmetic function , number theoretic functions , functional equation

For each positive integer $k$, let $d(k)$ be the number of positive divisors of $k$ and $\sigma(k)$ be the sum of positive divisors of $k$. Let $\mathbb N$ be the set of all positive integers. Find all functions $f: \mathbb{N} \to \mathbb N$ such that \begin{align*} f(d(n+1)) &= d(f(n)+1)\quad \text{and} \\ f(\sigma(n+1)) &= \sigma(f(n)+1) \end{align*} for all positive integers $n$.

1987 China Team Selection Test, 1

Tags: number theoretic functions , set , combinatorics

a.) For all positive integer $k$ find the smallest positive integer $f(k)$ such that $5$ sets $s_1,s_2, \ldots , s_5$ exist satisfying: [b]i.[/b] each has $k$ elements; [b]ii.[/b] $s_i$ and $s_{i+1}$ are disjoint for $i=1,2,...,5$ ($s_6=s_1$) [b]iii.[/b] the union of the $5$ sets has exactly $f(k)$ elements. b.) Generalisation: Consider $n \geq 3$ sets instead of $5$.

1987 China Team Selection Test, 1

Tags: set , combinatorics , number theoretic functions

a.) For all positive integer $k$ find the smallest positive integer $f(k)$ such that $5$ sets $s_1,s_2, \ldots , s_5$ exist satisfying: [b]i.[/b] each has $k$ elements; [b]ii.[/b] $s_i$ and $s_{i+1}$ are disjoint for $i=1,2,...,5$ ($s_6=s_1$) [b]iii.[/b] the union of the $5$ sets has exactly $f(k)$ elements. b.) Generalisation: Consider $n \geq 3$ sets instead of $5$.