Olympiad problems

2014 Taiwan TST Round 2, 2

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 Brazil Team Selection Test, 2

Tags: additive combinatorics , combinatorics , algorithm

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

2013 IMO Shortlist, C4

Tags: combinatorics , additive combinatorics , partition , induction

Let $n$ be a positive integer, and let $A$ be a subset of $\{ 1,\cdots ,n\}$. An $A$-partition of $n$ into $k$ parts is a representation of n as a sum $n = a_1 + \cdots + a_k$, where the parts $a_1 , \cdots , a_k $ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\{ a_1 , a_2 , \cdots , a_k \} $. We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r<k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6n}$ different parts.

1983 IMO, 3

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

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 Peru IMO TST, 11

Tags: frobenius , additive combinatorics , additive number theory , additive representation , number theory , 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]

1997 Pre-Preparation Course Examination, 1

Tags: combinatorics , additive combinatorics , additive number theory , extremal combinatorics , subset

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

1992 IMO Longlists, 45

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

Let $n$ be a positive integer. Prove that the number of ways to express $n$ as a sum of distinct positive integers (up to order) and the number of ways to express $n$ as a sum of odd positive integers (up to order) are the same.

2014 India IMO Training Camp, 2

Tags: algorithm , additive combinatorics , 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$.

2014 Germany Team Selection Test, 1

Tags: algorithm , additive combinatorics , 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$.

1992 IMO Longlists, 64

Tags: algorithm , additive number theory , additive combinatorics , algebra

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

1983 IMO Longlists, 27

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

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.

2009 China Team Selection Test, 6

Tags: combinatorics , additive combinatorics , algebra , number theory

Determine whether there exists an arithimethical progression consisting of 40 terms and each of whose terms can be written in the form $ 2^m \plus{} 3^n$ or not. where $ m,n$ are nonnegative integers.

1999 IMO Shortlist, 4

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

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

1979 IMO Longlists, 50

Tags: number theory , additive number theory , additive combinatorics , system of equations

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.

2009 China Team Selection Test, 2

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

2016 Peru IMO TST, 7

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 Longlists, 51

Tags: number theory , additive number theory , additive combinatorics

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

1983 IMO Shortlist, 15

Tags: number theory , additive number theory , additive combinatorics

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

1995 Miklós Schweitzer, 5

Tags: additive combinatorics , fourier analysis , combinatorics

Let A be a subset of the set $\{1,2, ...,n\}$ with at least $100\sqrt n$ elements. Prove that there is a four-element arithmetic sequence in which each element is the sum of two different elements of the set A.

1989 IMO Longlists, 68

Tags: combinatorics , partition , additive combinatorics , set systems

Prove that in the set $ \{1,2, \ldots, 1989\}$ can be expressed as the disjoint union of subsets $ A_i, \{i \equal{} 1,2, \ldots, 117\}$ such that [b]i.)[/b] each $ A_i$ contains 17 elements [b]ii.)[/b] the sum of all the elements in each $ A_i$ is the same.

2015 India IMO Training Camp, 1

Tags: induction , frobenius , additive combinatorics , additive number theory , additive representation , number theory

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]

1989 IMO Shortlist, 22

Tags: combinatorics , partition , additive combinatorics , set systems

Prove that in the set $ \{1,2, \ldots, 1989\}$ can be expressed as the disjoint union of subsets $ A_i, \{i \equal{} 1,2, \ldots, 117\}$ such that [b]i.)[/b] each $ A_i$ contains 17 elements [b]ii.)[/b] the sum of all the elements in each $ A_i$ is the same.

2017 Romanian Masters In Mathematics, 1

Tags: algebra , additive combinatorics , representation

[b](a)[/b] Prove that every positive integer $n$ can be written uniquely in the form \[n=\sum_{j=1}^{2k+1}(-1)^{j-1}2^{m_j},\] where $k\geq 0$ and $0\le m_1<m_2\cdots <m_{2k+1}$ are integers. This number $k$ is called [i]weight[/i] of $n$. [b](b)[/b] Find (in closed form) the difference between the number of positive integers at most $2^{2017}$ with even weight and the number of positive integers at most $2^{2017}$ with odd weight.

2014 Contests, 1

Tags: combinatorics , algorithm , 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$.

1992 IMO Longlists, 77

Tags: combinatorics , ramsey theory , additive number theory , additive combinatorics , extremal combinatorics

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.