Olympiad problems

2014 Germany Team Selection Test, 1

Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$.

1990 IMO Longlists, 3

Tags: number theory , additive combinatorics , additive number theory , counting

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?

2001 Romania Team Selection Test, 3

Tags: modular arithmetic , number theory , combinatorics , additive number theory , additive combinatorics , 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 \}.$

1990 IMO Shortlist, 1

Tags: number theory , additive combinatorics , additive number theory , counting

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?

1976 IMO Longlists, 48

Tags: algebra , polynomial , additive combinatorics , counting , combinatorics

The polynomial $1976(x+x^2+ \cdots +x^n)$ is decomposed into a sum of polynomials of the form $a_1x + a_2x^2 + \cdots + a_nx^n$, where $a_1, a_2, \ldots , a_n$ are distinct positive integers not greater than $n$. Find all values of $n$ for which such a decomposition is possible.

2015 Belarus Team Selection Test, 1

Tags: 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, 60

Tags: number theory , perfect power , additive combinatorics , additive number theory

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

1992 IMO Shortlist, 15

Tags: number theory , perfect power , additive combinatorics , additive number theory

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

2012 India IMO Training Camp, 3

Tags: arithmetic sequence , combinatorics , additive combinatorics

Determine the greatest positive integer $k$ that satisfies the following property: The set of positive integers can be partitioned into $k$ subsets $A_1, A_2, \ldots, A_k$ such that for all integers $n \geq 15$ and all $i \in \{1, 2, \ldots, k\}$ there exist two distinct elements of $A_i$ whose sum is $n.$ [i]Proposed by Igor Voronovich, Belarus[/i]

2009 China Team Selection Test, 2

Tags: modular arithmetic , polynomial , number theory , combinatorics , additive combinatorics , algebra

Find all the pairs of integers $ (a,b)$ satisfying $ ab(a \minus{} b)\not \equal{} 0$ such that there exists a subset $ Z_{0}$ of set of integers $ Z,$ for any integer $ n$, exactly one among three integers $ n,n \plus{} a,n \plus{} b$ belongs to $ Z_{0}$.

2012 Romanian Master of Mathematics, 3

Tags: function , algebra , additive combinatorics , combinatorics

Each positive integer is coloured red or blue. A function $f$ from the set of positive integers to itself has the following two properties: (a) if $x\le y$, then $f(x)\le f(y)$; and (b) if $x,y$ and $z$ are (not necessarily distinct) positive integers of the same colour and $x+y=z$, then $f(x)+f(y)=f(z)$. Prove that there exists a positive number $a$ such that $f(x)\le ax$ for all positive integers $x$. [i](United Kingdom) Ben Elliott[/i]

2013 IMO Shortlist, C1

Tags: algorithm , combinatorics , additive combinatorics

Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$.

1999 IMO Shortlist, 4

Tags: modular arithmetic , combinatorics , counting , additive combinatorics , additive number theory

Let $A$ be a set of $N$ residues $\pmod{N^{2}}$. Prove that there exists a set $B$ of of $N$ residues $\pmod{N^{2}}$ such that $A + B = \{a+b|a \in A, b \in B\}$ contains at least half of all the residues $\pmod{N^{2}}$.

2014 Contests, 1

Tags: algorithm , combinatorics , additive combinatorics

Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$.

1990 IMO Longlists, 16

Tags: number theory , additive number theory , additive combinatorics

We call an integer $k \geq 1$ having property $P$, if there exists at least one integer $m \geq 1$ which cannot be expressed in the form $m = \varepsilon_1 z_1^k + \varepsilon_2 z_2^k + \cdots + \varepsilon_{2k} z_{2k}^k $ , where $z_i$ are nonnegative integer and $\varepsilon _i = 1$ or $-1$, $i = 1, 2, \ldots, 2k$. Prove that there are infinitely many integers $k$ having the property $P.$

2014 India IMO Training Camp, 2

Tags: algorithm , combinatorics , additive combinatorics

Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$.

2016 Brazil Team Selection Test, 4

Tags: combinatorics , additive combinatorics

Let $S$ be a nonempty set of positive integers. We say that a positive integer $n$ is [i]clean[/i] if it has a unique representation as a sum of an odd number of distinct elements from $S$. Prove that there exist infinitely many positive integers that are not clean.

1983 IMO Shortlist, 18

Tags: modular arithmetic , number theory , frobenius , additive number theory , additive combinatorics

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.

2015 India IMO Training Camp, 1

Tags: 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]

1995 IMO Shortlist, 7

Tags: combinatorics , partition , additive combinatorics , additive number theory

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.

2007 IMO Shortlist, 3

Tags: modular arithmetic , number theory , divisibility , extremal combinatorics , additive combinatorics

Let $ X$ be a set of 10,000 integers, none of them is divisible by 47. Prove that there exists a 2007-element subset $ Y$ of $ X$ such that $ a \minus{} b \plus{} c \minus{} d \plus{} e$ is not divisible by 47 for any $ a,b,c,d,e \in Y.$ [i]Author: Gerhard Wöginger, Netherlands[/i]

2015 India IMO Training Camp, 1

Tags: 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]

2013 IMO Shortlist, C5

Tags: function , combinatorics , additive combinatorics , sequence

Let $r$ be a positive integer, and let $a_0 , a_1 , \cdots $ be an infinite sequence of real numbers. Assume that for all nonnegative integers $m$ and $s$ there exists a positive integer $n \in [m+1, m+r]$ such that \[ a_m + a_{m+1} +\cdots +a_{m+s} = a_n + a_{n+1} +\cdots +a_{n+s} \] Prove that the sequence is periodic, i.e. there exists some $p \ge 1 $ such that $a_{n+p} =a_n $ for all $n \ge 0$.

2014 India IMO Training Camp, 3

Tags: function , combinatorics , additive combinatorics , sequence

Let $r$ be a positive integer, and let $a_0 , a_1 , \cdots $ be an infinite sequence of real numbers. Assume that for all nonnegative integers $m$ and $s$ there exists a positive integer $n \in [m+1, m+r]$ such that \[ a_m + a_{m+1} +\cdots +a_{m+s} = a_n + a_{n+1} +\cdots +a_{n+s} \] Prove that the sequence is periodic, i.e. there exists some $p \ge 1 $ such that $a_{n+p} =a_n $ for all $n \ge 0$.

2000 IMO Shortlist, 6

Tags: modular arithmetic , number theory , combinatorics , additive number theory , additive combinatorics , 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 \}.$