Olympiad problems

2012 ELMO Shortlist, 3

Let $s(k)$ be the number of ways to express $k$ as the sum of distinct $2012^{th}$ powers, where order does not matter. Show that for every real number $c$ there exists an integer $n$ such that $s(n)>cn$. [i]Alex Zhu.[/i]

PEN P Problems, 42

Tags: pigeonhole principle , inequalities , Additive Number Theory

Prove that for each positive integer $K$ there exist infinitely many even positive integers which can be written in more than $K$ ways as the sum of two odd primes.

1969 IMO Shortlist, 63

Tags: quadratics , number theory , Additive Number Theory , IMO Shortlist , IMO Longlist

$(SWE 6)$ Prove that there are infinitely many positive integers that cannot be expressed as the sum of squares of three positive integers.

1992 IMO Longlists, 60

Tags: number theory , Perfect Powers , Additive combinatorics , Additive Number Theory , IMO Shortlist , IMO Longlist

Does there exist a set $ M$ with the following properties? [i](i)[/i] The set $ M$ consists of 1992 natural numbers. [i](ii)[/i] Every element in $ M$ and the sum of any number of elements have the form $ m^k$ $ (m, k \in \mathbb{N}, k \geq 2).$

PEN P Problems, 43

Tags: number theory , prime factorization , Additive Number Theory

A positive integer $n$ is abundant if the sum of its proper divisors exceeds $n$. Show that every integer greater than $89 \times 315$ is the sum of two abundant numbers.

PEN P Problems, 19

Tags: number theory , relatively prime , Additive Number Theory

Let $n$ be an integer of the form $a^2 + b^2$, where $a$ and $b$ are relatively prime integers and such that if $p$ is a prime, $p \leq \sqrt{n}$, then $p$ divides $ab$. Determine all such $n$.

1975 IMO, 2

Tags: modular arithmetic , number theory , Sequence , Additive Number Theory , IMO , IMO 1975

Let $a_{1}, \ldots, a_{n}$ be an infinite sequence of strictly positive integers, so that $a_{k} < a_{k+1}$ for any $k.$ Prove that there exists an infinity of terms $ a_{m},$ which can be written like $a_m = x \cdot a_p + y \cdot a_q$ with $x,y$ strictly positive integers and $p \neq q.$

1969 IMO Longlists, 25

Tags: number theory , Divisibility , Frobenius , Additive Number Theory , IMO Shortlist , IMO Longlist

$(GBR 2)$ Let $a, b, x, y$ be positive integers such that $a$ and $b$ have no common divisor greater than $1$. Prove that the largest number not expressible in the form $ax + by$ is $ab - a - b$. If $N(k)$ is the largest number not expressible in the form $ax + by$ in only $k$ ways, find $N(k).$

PEN P Problems, 1

Tags: Additive Number Theory

Show that any integer can be expressed as a sum of two squares and a cube.

1977 Germany Team Selection Test, 3

Tags: modular arithmetic , number theory , Sequence , Additive Number Theory , IMO , IMO 1975

Let $a_{1}, \ldots, a_{n}$ be an infinite sequence of strictly positive integers, so that $a_{k} < a_{k+1}$ for any $k.$ Prove that there exists an infinity of terms $ a_{m},$ which can be written like $a_m = x \cdot a_p + y \cdot a_q$ with $x,y$ strictly positive integers and $p \neq q.$

1969 IMO Longlists, 7

Tags: modular arithmetic , number theory , Diophantine equation , Additive Number Theory , perfect cube , IMO Shortlist , IMO Longlist

$(BUL 1)$ Prove that the equation $\sqrt{x^3 + y^3 + z^3}=1969$ has no integral solutions.

PEN P Problems, 20

Tags: Additive Number Theory

If an integer $n$ is such that $7n$ is the form $a^2 +3b^2$, prove that $n$ is also of that form.

1989 IMO Shortlist, 15

Tags: number theory , system of equations , Diophantine equation , Additive Number Theory , IMO Shortlist

Let $ a, b, c, d,m, n \in \mathbb{Z}^\plus{}$ such that \[ a^2\plus{}b^2\plus{}c^2\plus{}d^2 \equal{} 1989,\] \[ a\plus{}b\plus{}c\plus{}d \equal{} m^2,\] and the largest of $ a, b, c, d$ is $ n^2.$ Determine, with proof, the values of $m$ and $ n.$

1969 IMO Shortlist, 7

Tags: modular arithmetic , number theory , Diophantine equation , Additive Number Theory , perfect cube , IMO Shortlist , IMO Longlist

$(BUL 1)$ Prove that the equation $\sqrt{x^3 + y^3 + z^3}=1969$ has no integral solutions.

2015 India IMO Training Camp, 1

Tags: IMO Shortlist , number theory , Frobenius , Additive combinatorics , Additive Number Theory , additive representation , induction

Let $n \ge 2$ be an integer, and let $A_n$ be the set \[A_n = \{2^n - 2^k\mid k \in \mathbb{Z},\, 0 \le k < n\}.\] Determine the largest positive integer that cannot be written as the sum of one or more (not necessarily distinct) elements of $A_n$ . [i]Proposed by Serbia[/i]

PEN P Problems, 3

Tags: function , algebra , floor function , Additive Number Theory , pen

Prove that infinitely many positive integers cannot be written in the form \[{x_{1}}^{3}+{x_{2}}^{5}+{x_{3}}^{7}+{x_{4}}^{9}+{x_{5}}^{11},\] where $x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\in \mathbb{N}$.

PEN P Problems, 18

Tags: modular arithmetic , number theory , Additive Number Theory

Let $p$ be a prime with $p \equiv 1 \pmod{4}$. Let $a$ be the unique integer such that \[p=a^{2}+b^{2}, \; a \equiv-1 \pmod{4}, \; b \equiv 0 \; \pmod{2}\] Prove that \[\sum^{p-1}_{i=0}\left( \frac{i^{3}+6i^{2}+i }{p}\right) = 2 \left( \frac{2}{p}\right),\] where $\left(\frac{k}{p}\right)$ denotes the Legendre Symbol.

PEN P Problems, 14

Tags: Additive Number Theory

Let $n$ be a non-negative integer. Find all non-negative integers $a$, $b$, $c$, $d$ such that \[a^{2}+b^{2}+c^{2}+d^{2}= 7 \cdot 4^{n}.\]

PEN P Problems, 36

Tags: Additive Number Theory

Let $k$ and $s$ be odd positive integers such that \[\sqrt{3k-2}-1 \le s \le \sqrt{4k}.\] Show that there are nonnegative integers $t$, $u$, $v$, and $w$ such that \[k=t^{2}+u^{2}+v^{2}+w^{2}, \;\; \text{and}\;\; s=t+u+v+w.\]

1992 IMO Longlists, 64

Tags: algorithm , algebra , Additive Number Theory , Additive combinatorics , IMO Shortlist , IMO Longlist

For any positive integer $n$ consider all representations $n = a_1 + \cdots+ a_k$, where $a_1 > a_2 > \cdots > a_k > 0$ are integers such that for all $i \in \{1, 2, \cdots , k - 1\}$, the number $a_i$ is divisible by $a_{i+1}$. Find the longest such representation of the number $1992.$

2015 Belarus Team Selection Test, 1

Tags: IMO Shortlist , number theory , Frobenius , Additive combinatorics , Additive Number Theory , additive representation , induction

Let $n \ge 2$ be an integer, and let $A_n$ be the set \[A_n = \{2^n - 2^k\mid k \in \mathbb{Z},\, 0 \le k < n\}.\] Determine the largest positive integer that cannot be written as the sum of one or more (not necessarily distinct) elements of $A_n$ . [i]Proposed by Serbia[/i]

2001 Romania Team Selection Test, 3

Tags: modular arithmetic , number theory , combinatorics , Additive Number Theory , Additive combinatorics , IMO Shortlist , Frobenius

Let $ p$ and $ q$ be relatively prime positive integers. A subset $ S$ of $ \{0, 1, 2, \ldots \}$ is called [b]ideal[/b] if $ 0 \in S$ and for each element $ n \in S,$ the integers $ n \plus{} p$ and $ n \plus{} q$ belong to $ S.$ Determine the number of ideal subsets of $ \{0, 1, 2, \ldots \}.$

2001 Romania Team Selection Test, 4

Tags: number theory , Additive Number Theory , Sum of Squares , Perfect Square , IMO Shortlist

Show that the set of positive integers that cannot be represented as a sum of distinct perfect squares is finite.

1997 Pre-Preparation Course Examination, 1

Tags: combinatorics , Additive combinatorics , Additive Number Theory , Extremal combinatorics , Subsets , IMO Shortlist

Let $ k,m,n$ be integers such that $ 1 < n \leq m \minus{} 1 \leq k.$ Determine the maximum size of a subset $ S$ of the set $ \{1,2,3, \ldots, k\minus{}1,k\}$ such that no $ n$ distinct elements of $ S$ add up to $ m.$

PEN P Problems, 11

Tags: inequalities , Additive Number Theory

For each positive integer $n$, let $f(n)$ denote the number of ways of representing $n$ as a sum of powers of 2 with nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For instance, $f(4)=4$, because the number $4$ can be represented in the following four ways: \[4, 2+2, 2+1+1, 1+1+1+1.\] Prove that, for any integer $n \geq 3$, \[2^{n^{2}/4}< f(2^{n}) < 2^{n^{2}/2}.\]