Olympiad problems

1997 Pre-Preparation Course Examination, 1

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

1983 IMO, 3

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.

1997 Romania Team Selection Test, 2

Tags: combinatorics , additive combinatorics

Find the number of sets $A$ containing $9$ positive integers with the following property: for any positive integer $n\le 500$, there exists a subset $B\subset A$ such that $\sum_{b\in B}{b}=n$. [i]Bogdan Enescu & Dan Ismailescu[/i]

2009 China Team Selection Test, 2

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

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

1993 IMO Shortlist, 2

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

2015 Peru IMO TST, 11

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]

2012 Belarus Team Selection Test, 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]

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.

2014 Brazil Team Selection Test, 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$.

1992 IMO Longlists, 29

Tags: algebra , convex polygon , incircle , polygon , additive combinatorics

Show that in the plane there exists a convex polygon of 1992 sides satisfying the following conditions: [i](i)[/i] its side lengths are $ 1, 2, 3, \ldots, 1992$ in some order; [i](ii)[/i] the polygon is circumscribable about a circle. [i]Alternative formulation:[/i] Does there exist a 1992-gon with side lengths $ 1, 2, 3, \ldots, 1992$ circumscribed about a circle? Answer the same question for a 1990-gon.

Russian TST 2014, P2

Tags: induction , combinatorics , additive combinatorics , partition

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.

2020 Olympic Revenge, 4

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

Let $n$ be a positive integer and $A$ a set of integers such that the set $\{x = a + b\ |\ a, b \in A\}$ contains $\{1^2, 2^2, \dots, n^2\}$. Prove that there is a positive integer $N$ such that if $n \ge N$, then $|A| > n^{0.666}$.

1979 IMO Longlists, 50

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

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.

2016 Taiwan TST Round 1, 6

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.

1989 IMO, 1

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.

1992 IMO Shortlist, 8

Tags: algebra , convex polygon , incircle , polygon , additive combinatorics

Show that in the plane there exists a convex polygon of 1992 sides satisfying the following conditions: [i](i)[/i] its side lengths are $ 1, 2, 3, \ldots, 1992$ in some order; [i](ii)[/i] the polygon is circumscribable about a circle. [i]Alternative formulation:[/i] Does there exist a 1992-gon with side lengths $ 1, 2, 3, \ldots, 1992$ circumscribed about a circle? Answer the same question for a 1990-gon.

2011 Israel National Olympiad, 1

Tags: combinatorics , additive combinatorics

We are given 5771 weights weighing 1,2,3,...,5770,5771. We partition the weights into $n$ sets of equal weight. What is the maximal $n$ for which this is possible?

2014 Taiwan TST Round 1, 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$.

2009 China Team Selection Test, 6

Tags: algebra , number theory , combinatorics , additive combinatorics

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.

2008 Germany Team Selection Test, 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]

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]

1995 Miklós Schweitzer, 5

Tags: combinatorics , additive combinatorics , fourier analysis

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.

2008 South East Mathematical Olympiad, 1

Tags: combinatorics , set systems , additive combinatorics , ramsey theory

Given a set $S=\{1,2,3,\ldots,3n\},(n\in N^*)$, let $T$ be a subset of $S$, such that for any $x, y, z\in T$ (not necessarily distinct) we have $x+y+z\not \in T$. Find the maximum number of elements $T$ can have.

2014 IMO Shortlist, N1

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]