Olympiad problems

PEN P Problems, 41

Tags: Additive Number Theory

The famous conjecture of Goldbach is the assertion that every even integer greater than $2$ is the sum of two primes. Except $2$, $4$, and $6$, every even integer is a sum of two positive composite integers: $n=4+(n-4)$. What is the largest positive even integer that is not a sum of two odd composite integers?

1995 IMO Shortlist, 7

Tags: combinatorics , partition , Additive combinatorics , Additive Number Theory , IMO Shortlist

Does there exist an integer $ n > 1$ which satisfies the following condition? The set of positive integers can be partitioned into $ n$ nonempty subsets, such that an arbitrary sum of $ n \minus{} 1$ integers, one taken from each of any $ n \minus{} 1$ of the subsets, lies in the remaining subset.

1983 IMO Longlists, 51

Tags: number theory , Additive Number Theory , Additive combinatorics , IMO Shortlist

Decide whether there exists a set $M$ of positive integers satisfying the following conditions: (i) For any natural number $m>1$ there exist $a, b \in M$ such that $a+b = m.$ (ii) If $a, b, c, d \in M$, $a, b, c, d > 10$ and $a + b = c + d$, then $a = c$ or $a = d.$

2014 IMO Shortlist, N1

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]

1992 IMO Longlists, 77

Tags: combinatorics , Ramsey Theory , Additive Number Theory , Additive combinatorics , IMO Shortlist , Extremal combinatorics , IMO Longlist

Show that if $994$ integers are chosen from $1, 2,\cdots , 1992$ and one of the chosen integers is less than $64$, then there exist two among the chosen integers such that one of them is a factor of the other.

2019 IMO Shortlist, N7

Tags: number theory , IMO Shortlist , IMO Shortlist 2019 , Additive Number Theory

Prove that there is a constant $c>0$ and infinitely many positive integers $n$ with the following property: there are infinitely many positive integers that cannot be expressed as the sum of fewer than $cn\log(n)$ pairwise coprime $n$th powers. [i]Canada[/i]

1979 IMO Longlists, 69

Tags: number theory , perfect cube , Perfect Square , counting , Additive Number Theory , IMO Shortlist , IMO Longlist

Let $N$ be the number of integral solutions of the equation \[x^2 - y^2 = z^3 - t^3\] satisfying the condition $0 \leq x, y, z, t \leq 10^6$, and let $M$ be the number of integral solutions of the equation \[x^2 - y^2 = z^3 - t^3 + 1\] satisfying the condition $0 \leq x, y, z, t \leq 10^6$. Prove that $N >M.$

PEN P Problems, 29

Tags: Additive Number Theory

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

1979 IMO Shortlist, 18

Tags: number theory , Additive Number Theory , Additive combinatorics , system of equations , IMO Shortlist , IMO Longlist

Let $m$ positive integers $a_1, \dots , a_m$ be given. Prove that there exist fewer than $2^m$ positive integers $b_1, \dots , b_n$ such that all sums of distinct $b_k$’s are distinct and all $a_i \ (i \leq m)$ occur among them.

2017 Baltic Way, 3

Tags: algebra , Fibonacci , Additive Number Theory , Extremal combinatorics

Positive integers $x_1,...,x_m$ (not necessarily distinct) are written on a blackboard. It is known that each of the numbers $F_1,...,F_{2018}$ can be represented as a sum of one or more of the numbers on the blackboard. What is the smallest possible value of $m$? (Here $F_1,...,F_{2018}$ are the first $2018$ Fibonacci numbers: $F_1=F_2=1, F_{k+1}=F_k+F_{k-1}$ for $k>1$.)

PEN P Problems, 27

Tags: floor function , Additive Number Theory

Determine, with proof, the largest number which is the product of positive integers whose sum is $1976$.

PEN P Problems, 34

Tags: Additive Number Theory

If $n$ is a positive integer which can be expressed in the form $n=a^{2}+b^{2}+c^{2}$, where $a, b, c$ are positive integers, prove that for each positive integer $k$, $n^{2k}$ can be expressed in the form $A^2 +B^2 +C^2$, where $A, B, C$ are positive integers.

PEN P Problems, 8

Tags: algorithm , Additive Number Theory

Prove that any positive integer can be represented as an aggregate of different powers of $3$, the terms in the aggregate being combined by the signs $+$ and $-$ appropriately chosen.

1979 IMO Shortlist, 21

Tags: number theory , perfect cube , Perfect Square , counting , Additive Number Theory , IMO Shortlist , IMO Longlist

Let $N$ be the number of integral solutions of the equation \[x^2 - y^2 = z^3 - t^3\] satisfying the condition $0 \leq x, y, z, t \leq 10^6$, and let $M$ be the number of integral solutions of the equation \[x^2 - y^2 = z^3 - t^3 + 1\] satisfying the condition $0 \leq x, y, z, t \leq 10^6$. Prove that $N >M.$

PEN P Problems, 15

Tags: quadratics , algebra , Diophantine equation , Additive Number Theory

Find all integers $m>1$ such that $m^3$ is a sum of $m$ squares of consecutive integers.

PEN P Problems, 30

Tags: Additive Number Theory

Let $a_{1}, a_{2}, a_{3}, \cdots$ be an increasing sequence of nonnegative integers such that every nonnegative integer can be expressed uniquely in the form $a_{i}+2a_{j}+4a_{k}$, where $i, j, $ and $k$ are not necessarily distinct. Determine $a_{1998}$.

PEN P Problems, 16

Tags: search , Diophantine equation , Additive Number Theory

Prove that there exist infinitely many integers $n$ such that $n, n+1, n+2$ are each the sum of the squares of two integers.

PEN P Problems, 31

Tags: quadratics , Additive Number Theory

A finite sequence of integers $a_{0}, a_{1}, \cdots, a_{n}$ is called quadratic if for each $i \in \{1,2,\cdots,n \}$ we have the equality $\vert a_{i}-a_{i-1} \vert = i^2$. [list=a] [*] Prove that for any two integers $b$ and $c$, there exists a natural number $n$ and a quadratic sequence with $a_{0}=b$ and $a_{n}=c$. [*] Find the smallest natural number $n$ for which there exists a quadratic sequence with $a_{0}=0$ and $a_{n}=1996$. [/list]

1992 IMO Longlists, 34

Tags: linear algebra , number theory , system of equations , Additive Number Theory , IMO Shortlist , IMO Longlist

Let $a, b, c$ be integers. Prove that there are integers $p_1, q_1, r_1, p_2, q_2, r_2$ such that \[a = q_1r_2 - q_2r_1, b = r_1p_2 - r_2p_1, c = p_1q_2 - p_2q_1.\]

PEN P Problems, 10

Tags: Additive Number Theory

For each positive integer $\,n,\;S(n)\,$ is defined to be the greatest integer such that, for every positive integer $\,k\leq S(n),\;n^{2}\,$ can be written as the sum of $\,k\,$ positive squares. [list=a] [*] Prove that $S(n)\leq n^{2}-14$ for each $n\geq 4$. [*] Find an integer $n$ such that $S(n)=n^{2}-14$. [*] Prove that there are infinitely many integers $n$ such that $S(n)=n^{2}-14$. [/list]

2001 IMO Shortlist, 6

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

Is it possible to find $100$ positive integers not exceeding $25,000$, such that all pairwise sums of them are different?

1983 IMO, 3

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

Let $a,b$ and $c$ be positive integers, no two of which have a common divisor greater than $1$. Show that $2abc-ab-bc-ca$ is the largest integer which cannot be expressed in the form $xbc+yca+zab$, where $x,y,z$ are non-negative integers.

1977 IMO Shortlist, 3

Tags: number theory , Additive Number Theory , remainder , Divisibility , IMO , IMO 1977

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.$

1993 IMO Shortlist, 2

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

Let $n,k \in \mathbb{Z}^{+}$ with $k \leq n$ and let $S$ be a set containing $n$ distinct real numbers. Let $T$ be a set of all real numbers of the form $x_1 + x_2 + \ldots + x_k$ where $x_1, x_2, \ldots, x_k$ are distinct elements of $S.$ Prove that $T$ contains at least $k(n-k)+1$ distinct elements.

1990 IMO Longlists, 3

Tags: number theory , Additive combinatorics , Additive Number Theory , counting , IMO Shortlist

The integer $ 9$ can be written as a sum of two consecutive integers: $ 9 \equal{} 4\plus{}5.$ Moreover, it can be written as a sum of (more than one) consecutive positive integers in exactly two ways: $ 9 \equal{} 4\plus{}5 \equal{} 2\plus{}3\plus{}4.$ Is there an integer that can be written as a sum of $ 1990$ consecutive integers and that can be written as a sum of (more than one) consecutive positive integers in exactly $ 1990$ ways?