Olympiad problems

2015 Irish Math Olympiad, 7

Let $n > 1$ be an integer and $\Omega=\{1,2,...,2n-1,2n\}$ the set of all positive integers that are not larger than $2n$. A nonempty subset $S$ of $\Omega$ is called [i]sum-free[/i] if, for all elements $x, y$ belonging to $S, x + y$ does not belong to $S$. We allow $x = y$ in this condition. Prove that $\Omega$ has more than $2^n$ distinct [i]sum-free[/i] subsets.

2022 SG Originals, Q2

Tags: functional equation , set , integer , algebra , function

Find all functions $f$ mapping non-empty finite sets of integers, to integers, such that $$f(A+B)=f(A)+f(B)$$ for all non-empty sets of integers $A$ and $B$. $A+B$ is defined as $\{a+b: a \in A, b \in B\}$.

2015 Korea Junior Math Olympiad, 8

Tags: combinatorics , set

A positive integer $n$ is given. If there exist sets $F_1, F_2, \cdots F_m$ satisfying the following, prove that $m \le n$. (For sets $A, B$, $|A|$ is the number of elements in $A$. $A-B$ is the set of elements that are in $A$ but not $B$) (i): For all $1 \le i \le m$, $F_i \subseteq \{1,2,\cdots n\}$ (ii): $|F_1| \le |F_2| \le \cdots \le |F_m|$ (iii): For all $1 \le i < j \le m$, $|F_i-F_j|=1$.

2014 Saudi Arabia GMO TST, 4

Tags: rational , set , algebra

Let $X$ be a set of rational numbers satisfying the following two conditions: (a) The set $X$ contains at least two elements, (b) For any $x, y$ in $X$, if $x \ne y$ then there exists $z$ in $X$ such that either $\left| \frac{x- z}{y - z} \right|= 2$ or $\left| \frac{y -z}{x - z} \right|= 2$ . Prove that $X$ contains infinitely many elements.

2021 Korea - Final Round, P4

Tags: combinatorics , easy , set

There are $n$($\ge 2$) clubs $A_1,A_2,...A_n$ in Korean Mathematical Society. Prove that there exist $n-1$ sets $B_1,B_2,...B_{n-1}$ that satisfy the condition below. (1) $A_1\cup A_2\cup \cdots A_n=B_1\cup B_2\cup \cdots B_{n-1}$ (2) for any $1\le i<j\le n-1$, $B_i\cap B_j=\emptyset, -1\le\left\vert B_i \right\vert -\left\vert B_j \right\vert\le 1$ (3) for any $1\le i \le n-1$, there exist $A_k,A_j $($1\le k\le j\le n$)such that $B_i\subseteq A_k\cup A_j$

2015 Greece JBMO TST, 4

Tags: combinatorics , set theory , set

Pupils of a school are divided into $112$ groups, of $11$ members each. Any two groups have exactly one common pupil. Prove that: a) there is a pupil that belongs to at least $12$ groups. b) there is a pupil that belongs to all the groups.

2008 Bulgarian Autumn Math Competition, Problem 12.4

Tags: number theory , set

Veni writes down finitely many real numbers (possibly one), squares them, and then subtracts 1 from each of them and gets the same set of numbers as in the beginning. What were the starting numbers?

2015 Dutch Mathematical Olympiad, 1

Tags: combinatorics , maximum , set

We make groups of numbers. Each group consists of [i]five[/i] distinct numbers. A number may occur in multiple groups. For any two groups, there are exactly four numbers that occur in both groups. (a) Determine whether it is possible to make $2015$ groups. (b) If all groups together must contain exactly [i]six [/i] distinct numbers, what is the greatest number of groups that you can make? (c) If all groups together must contain exactly [i]seven [/i] distinct numbers, what is the greatest number of groups that you can make?

2011 Philippine MO, 1

Tags: combinatorics , set

Find all nonempty finite sets $X$ of real numbers such that for all $x\in X$, $x+|x| \in X$.

2023 OMpD, 3

Tags: graph theory , combinatorics , hamiltonian cycle , power set , induction , set

Let $m$ and $n$ be positive integers integers such that $2m + 1 < n$, and let $S$ be the set of the $2^n$ subsets of $\{1,2,\ldots,n\}$. Prove that we can place the elements of $S$ on a circle, so that for any two adjacent elements $A$ and $B$, the set $A \Delta B$ has exactly $2m + 1$ elements. [b]Note[/b]: $A \Delta B = (A \cup B) - (A \cap B)$ is the set of elements that are exclusively in $A$ or exclusively in $B$.

2015 Czech-Polish-Slovak Match, 2

Tags: combinatorics , set

A family of sets $F$ is called perfect if the following condition holds: For every triple of sets $X_1, X_2, X_3\in F$, at least one of the sets $$ (X_1\setminus X_2)\cap X_3,$$ $$(X_2\setminus X_1)\cap X_3$$ is empty. Show that if $F$ is a perfect family consisting of some subsets of a given finite set $U$, then $\left\lvert F\right\rvert\le\left\lvert U\right\rvert+1$. [i]Proposed by Michał Pilipczuk[/i]

2023 Germany Team Selection Test, 3

Tags: sum , elements of set , combinatorics , set

Let $A$ be a non-empty set of integers with the following property: For each $a \in A$, there exist not necessarily distinct integers $b,c \in A$ so that $a=b+c$. (a) Proof that there are examples of sets $A$ fulfilling above property that do not contain $0$ as element. (b) Proof that there exist $a_1,\ldots,a_r \in A$ with $r \ge 1$ and $a_1+\cdots+a_r=0$. (c) Proof that there exist pairwise distinct $a_1,\ldots,a_r$ with $r \ge 1$ and $a_1+\cdots+a_r=0$.

2007 Rioplatense Mathematical Olympiad, Level 3, 6

Tags: combinatorics , set

Let $n > 2$ be a natural number. A subset $A$ of $R$ is said $n$-[i]small [/i]if there exist $n$ real numbers $t_1 , t_2 , ..., t_n$ such that the sets $t_1 + A , t_2 + A ,... , t_n + A$ are different . Show that $R$ can not be represented as a union of $ n - 1$ $n$-[i]small [/i] sets . Notation : if $r \in R$ and $B \subset R$ , then $r + B = \{ r + b | b \in B\}$ .

2016 Poland - Second Round, 4

Tags: set , perfect square , number theory

Let $k$ be a positive integer. Show that exists positive integer $n$, such that sets $A = \{ 1^2, 2^2, 3^2, ...\}$ and $B = \{1^2 + n, 2^2 + n, 3^2 + n, ... \}$ have exactly $k$ common elements.

2016 India PRMO, 14

Tags: minimum , set , subset

Find the minimum value of $m$ such that any $m$-element subset of the set of integers $\{1,2,...,2016\}$ contains at least two distinct numbers $a$ and $b$ which satisfy $|a - b|\le 3$.

1987 All Soviet Union Mathematical Olympiad, 459

Tags: set , number theory , combinatorics

The $T_0$ set consists of all the numbers, representable as $(2k)!, k = 0, 1, 2, ... , n, ...$. The $T_m$ set is obtained from $T_{m-1}$ by adding all the finite sums of different numbers, that belong to $T_{m-1}$. Prove that there is a natural number, that doesn't belong to $T_{1987}$.

2011 VTRMC, Problem 4

Tags: number theory , set

Let $m,n$ be positive integers and let $[a]$ denote the residue class$\pmod{mn}$ of the integer $a$ (thus $\{[r]|r\text{ is an integer}\}$ has exactly $mn$ elements). Suppose the set $\{[ar]|r\text{ is an integer}\}$ has exactly $m$ elements. Prove that there is a positive integer $q$ such that $q$ is coprime to $mn$ and $[nq]=[a]$.

2019 Thailand TST, 2

Tags: algebra , rational number , set

Given any set $S$ of positive integers, show that at least one of the following two assertions holds: (1) There exist distinct finite subsets $F$ and $G$ of $S$ such that $\sum_{x\in F}1/x=\sum_{x\in G}1/x$; (2) There exists a positive rational number $r<1$ such that $\sum_{x\in F}1/x\neq r$ for all finite subsets $F$ of $S$.

2021 EGMO, 1

Tags: combinatorics , set

The number 2021 is fantabulous. For any positive integer $m$, if any element of the set $\{m, 2m+1, 3m\}$ is fantabulous, then all the elements are fantabulous. Does it follow that the number $2021^{2021}$ is fantabulous?

2017 Bosnia And Herzegovina - Regional Olympiad, 3

Tags: arithmetic progression , number theory , set

Let $S$ be a set of $6$ positive real numbers such that $\left(a,b \in S \right) \left(a>b \right) \Rightarrow a+b \in S$ or $a-b \in S$ Prove that if we sort these numbers in ascending order, then they form an arithmetic progression

2015 Romania Team Selection Tests, 3

Tags: arithmetic sequence , product , set , algebra

Given a positive real number $t$ , determine the sets $A$ of real numbers containing $t$ , for which there exists a set $B$ of real numbers depending on $A$ , $|B| \geq 4$ , such that the elements of the set $AB =\{ ab \mid a\in A , b \in B \}$ form a finite arithmetic progression .

2011 Bosnia And Herzegovina - Regional Olympiad, 4

Tags: combinatorics , set

Let $n$ be a positive integer and set $S=\{n,n+1,n+2,...,5n\}$ $a)$ If set $S$ is divided into two disjoint sets , prove that there exist three numbers $x$, $y$ and $z$(possibly equal) which belong to same subset of $S$ and $x+y=z$ $b)$ Does $a)$ hold for set $S=\{n,n+1,n+2,...,5n-1\}$

2016 Bosnia And Herzegovina - Regional Olympiad, 2

Tags: combinatorics , combinatorial number theory , coprime , set

Find all elements $n \in A = \{2,3,...,2016\} \subset \mathbb{N}$ such that: every number $m \in A$ smaller than $n$, and coprime with $n$, must be a prime number

2016 USAJMO, 4

Tags: set

Find, with proof, the least integer $N$ such that if any $2016$ elements are removed from the set ${1, 2,...,N}$, one can still find $2016$ distinct numbers among the remaining elements with sum $N$.

2000 Saint Petersburg Mathematical Olympiad, 11.7

Tags: algebra , irrational number , set

It is known that for irrational numbers $\alpha$, $\beta$, $\gamma$, $\delta$ and for any positive integer $n$ the following is true: $$[n\alpha]+[n\beta]=[n\gamma]+[n\delta]$$ Does this mean that sets $\{\alpha,\beta\}$ and $\{\gamma,\delta\}$ are equal? (As usual $[x]$ means the greatest integer not greater than $x$).