Olympiad problems

2000 Iran MO (2nd round), 1

Find all positive integers $n$ such that we can divide the set $\{1,2,3,\ldots,n\}$ into three sets with the same sum of members.

2018 Danube Mathematical Competition, 4

Tags: combinatorics , Subsets , Sets

Let $M$ be the set of positive odd integers. For every positive integer $n$, denote $A(n)$ the number of the subsets of $M$ whose sum of elements equals $n$. For instance, $A(9) = 2$, because there are exactly two subsets of $M$ with the sum of their elements equal to $9$: $\{9\}$ and $\{1, 3, 5\}$. a) Prove that $A(n) \le A(n + 1)$ for every integer $n \ge 2$. b) Find all the integers $n \ge 2$ such that $A(n) = A(n + 1)$

2017 Federal Competition For Advanced Students, P2, 6

Tags: Subsets , Maximal , combinatorics

Let $S = \{1,2,..., 2017\}$. Find the maximal $n$ with the property that there exist $n$ distinct subsets of $S$ such that for no two subsets their union equals $S$. Proposed by Gerhard Woeginger

2004 Singapore MO Open, 1

Tags: combinatorics , Subsets , inequalities

Let $m,n$ be integers so that $m \ge n > 1$. Let $F_1,...,F_k$ be a collection of $n$-element subsets of $\{1,...,m\}$ so that $F_i\cap F_j$ contains at most $1$ element, $1 \le i < j \le k$. Show that $k\le \frac{m(m-1)}{n(n-1)} $

2015 Saudi Arabia BMO TST, 2

Tags: combinatorics , Subsets

Given $2015$ subsets $A_1, A_2,...,A_{2015}$ of the set $\{1, 2,..., 1000\}$ such that $|A_i| \ge 2$ for every $i \ge 1$ and $|A_i \cap A_j| \ge 1$ for every $1 \le i < j \le 2015$. Prove that $k = 3$ is the smallest number of colors such that we can always color the elements of the set $\{1, 2,..., 1000\}$ by $k$ colors with the property that the subset $A_i$ has at least two elements of different colors for every $i \ge 1$. Lê Anh Vinh

1961 Putnam, A7

Tags: Putnam , topology , Subsets , college contests

Let $S$ be a nonempty closed set in the euclidean plane for which there is a closed disk $D$ containing $S$ such that $D$ is a subset of every closed disk that contains $S$. Prove that every point inside $D$ is the midpoint of a segment joining two points of $S.$

1986 Czech And Slovak Olympiad IIIA, 6

Tags: combinatorics , Subsets , inequalities

Assume that $M \subset N$ has the property that every two numbers $m,n$ of $M$ satisfy $|m-n| \ge mn/25$. Prove that the set $M$ contains no more than $9$ elements. Decide whether there exists such set M.

1993 Romania Team Selection Test, 4

Tags: Subsets , function , algebra

Let $Y$ be the family of all subsets of $X = \{1,2,...,n\}$ ($n > 1$) and let $f : Y \to X$ be an arbitrary mapping. Prove that there exist distinct subsets $A,B$ of $X$ such that $f(A) = f(B) = max A\triangle B$, where $A\triangle B = (A-B)\cup(B-A)$.

2019 Junior Balkan Team Selection Tests - Romania, 4

Tags: combinatorics , Subsets

Consider two disjoint finite sets of positive integers, $A$ and $B$, have $n$ and $m$ elements, respectively. It is knows that all $k$ belonging to $A \cup B$ satisfies at least one of the conditions $k + 17 \in A$ and $k - 31 \in B$. Prove that $17n = 31m$.

2008 IMAC Arhimede, 6

Tags: Subsets , combinatorics , Sets , partition

Consider the set of natural numbers $ U = \{1,2,3, ..., 6024 \} $ Prove that for any partition of the $ U $ in three subsets with $ 2008 $ elements each, we can choose a number in each subset so that one of the numbers is the sum of the other two numbers.

2001 Switzerland Team Selection Test, 10

Tags: Subsets , number theory , Sum , power of 2

Prove that every $1000$-element subset $M$ of the set $\{0,1,...,2001\}$ contains either a power of two or two distinct numbers whose sum is a power of two.

1986 Czech And Slovak Olympiad IIIA, 1

Tags: Even , Subsets , combinatorics

Given $n \in N$, let $A$ be a family of subsets of $\{1,2,...,n\}$. If for every two sets $B,C \in A$ the set $(B \cup C) -(B \cap C)$ has an even number of elements, find the largest possible number of elements of $A$ .

2016 Saudi Arabia IMO TST, 3

Tags: combinatorics , set , Subsets

Given two positive integers $r > s$, and let $F$ be an infinite family of sets, each of size $r$, no two of which share fewer than $s$ elements. Prove that there exists a set of size $r -1$ that shares at least $s$ elements with each set in $F$.

2006 Lithuania National Olympiad, 4

Tags: combinatorics , combinatorics proposed , combinatorics solved , Sets , Subsets , cardinality , uniqueness

Find the maximal cardinality $|S|$ of the subset $S \subset A=\{1, 2, 3, \dots, 9\}$ given that no two sums $a+b | a, b \in S, a \neq b$ are equal.

1995 Austrian-Polish Competition, 2

Tags: Subsets , set , combinatorial geometry , combinatorics , disks

Let $X= \{A_1, A_2, A_3, A_4\}$ be a set of four distinct points in the plane. Show that there exists a subset $Y$ of $X$ with the property that there is no (closed) disk $K$ such that $K\cap X = Y$.

1994 Italy TST, 4

Tags: Subsets , algebra , Sets

Let $X$ be a set of $n$ elements and $k$ be a positive integer. Consider the family $S_k$ of all $k$-tuples $(E_1,...,E_k)$ with $E_i \subseteq X$ for each $i$. Evaluate the sums $\sum_{(E_1,...,E_k) \in S_k }|E_1 \cap ... \cap E_k|$ and $\sum_{(E_1,...,E_k) \in S_k }|E_1 \cup ... \cup E_k|$

2010 Contests, 1

Tags: combinatorics proposed , combinatorics , combinatorics solved , symmetry , Subsets , Bounding

A finite set of integers is called [i]bad[/i] if its elements add up to $2010$. A finite set of integers is a [i]Benelux-set[/i] if none of its subsets is bad. Determine the smallest positive integer $n$ such that the set $\{502, 503, 504, . . . , 2009\}$ can be partitioned into $n$ Benelux-sets. (A partition of a set $S$ into $n$ subsets is a collection of $n$ pairwise disjoint subsets of $S$, the union of which equals $S$.) [i](2nd Benelux Mathematical Olympiad 2010, Problem 1)[/i]

2012 Belarus Team Selection Test, 2

Tags: Subsets , combinatorics

Determine the greatest possible value of n that satisfies the following condition: for any choice of $n$ subsets $M_1, ...,M_n$ of the set $M = \{1,2,...,n\}$ satisfying the conditions i) $i \in M_i$ and ii) $i \in M_j \Leftrightarrow j \notin M_i$ for all $i \ne j$, there exist $M_k$ and $M_l$ such that $M_k \cup M_l = M$. (Moscow regional olympiad,adopted)

2016 Kurschak Competition, 1

Tags: combinatorics , Subsets

Let $1\le k\le n$ be integers. At most how many $k$-element subsets can we select from $\{1,2,\dots,n\}$ such that for any two selected subsets, one of the subsets consists of the $k$ smallest elements of their union?

1978 Swedish Mathematical Competition, 5

Tags: Subsets , partition , combinatorics

$k > 1$ is fixed. Show that for $n$ sufficiently large for every partition of $\{1,2,\dots,n\}$ into $k$ disjoint subsets we can find $a \neq b$ such that $a$ and $b$ are in the same subset and $a+1$ and $b+1$ are in the same subset. What is the smallest $n$ for which this is true?

2014 Czech-Polish-Slovak Junior Match, 1

Tags: number theory , greatest common divisor , Subsets , Product

The set of $\{1,2,3,...,63\}$ was divided into three non-empty disjoint sets $A,B$. Let $a,b,c$ be the product of all numbers in each set $A,B,C$ respectively and finally we have determined the greatest common divisor of these three products. What was the biggest result we could get?

1998 Czech And Slovak Olympiad IIIA, 2

Tags: Sum , algebra , Subsets

Given any set of $14$ (different) natural numbers, prove that for some $k$ ($1 \le k \le 7$) there exist two disjoint $k$-element subsets $\{a_1,...,a_k\}$ and $\{b_1,...,b_k\}$ such that $A =\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_k}$ and $B =\frac{1}{b_1}+\frac{1}{b_2}+...+\frac{1}{b_k}$ differ by less than $0.001$, i.e. $|A-B| < 0.001$

2025 Kyiv City MO Round 2, Problem 3

Tags: combinatorics , Subsets

In a school, $ n $ different languages are taught. It is known that for any subset of these languages (including the empty set), there is exactly one student who knows these and only these languages (there are $ 2^n $ students in total). Each day, the students are divided into pairs and teach each other the languages that only one of them knows. If students are not allowed to be in the same pair twice, what is the minimum number of days the school administration needs to guarantee that all their students know all $ n $ languages? [i]Proposed by Oleksii Masalitin[/i]

1969 IMO Longlists, 42

Tags: algebra , combinatorics , Subsets , Intersection , IMO Shortlist , IMO Longlist

$(MON 3)$ Let $A_k (1 \le k \le h)$ be $n-$element sets such that each two of them have a nonempty intersection. Let $A$ be the union of all the sets $A_k,$ and let $B$ be a subset of $A$ such that for each $k (1\le k \le h)$ the intersection of $A_k$ and $B$ consists of exactly two different elements $a_k$ and $b_k$. Find all subsets $X$ of the set $A$ with $r$ elements satisfying the condition that for at least one index $k,$ both elements $a_k$ and $b_k$ belong to $X$.

2002 USAMO, 1

Tags: USAMO , induction , combinatorics , Subsets

Let $S$ be a set with 2002 elements, and let $N$ be an integer with $0 \leq N \leq 2^{2002}$. Prove that it is possible to color every subset of $S$ either black or white so that the following conditions hold: (a) the union of any two white subsets is white; (b) the union of any two black subsets is black; (c) there are exactly $N$ white subsets.