Olympiad problems

2016 Mathematical Talent Reward Programme, MCQ: P 10

Tags: set , cardinality

Let $A=\{1,2,\cdots ,100\}$. Let $S$ be a subset of power set of $A$ such that any two elements of $S$ has nonzero intersection (Note that elements of $S$ are actually some subsets of $A$). Then the maximum possible cardinality of $S$ is [list=1] [*] $2^{99}$ [*] $2^{99}+1$ [*] $2^{99}+2^{98}$ [*] None of these [/list]

2023 Germany Team Selection Test, 3

Tags: set , sum , elements of set , combinatorics

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

2016 Poland - Second Round, 4

Tags: number theory , set , perfect square

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.

2018 Bosnia And Herzegovina - Regional Olympiad, 1

Tags: number theory , binomial coefficient , set

$a)$ Prove that for all positive integers $n \geq 3$ holds: $$\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n-1}=2^n-2$$ where $\binom{n}{k}$ , with integer $k$ such that $n \geq k \geq 0$, is binomial coefficent $b)$ Let $n \geq 3$ be an odd positive integer. Prove that set $A=\left\{ \binom{n}{1},\binom{n}{2},...,\binom{n}{\frac{n-1}{2}} \right\}$ has odd number of odd numbers

2003 Croatia National Olympiad, Problem 4

Tags: set , algebra

Find the least possible cardinality of a set $A$ of natural numbers, the smallest and greatest of which are $1$ and $100$, and having the property that every element of $A$ except for $1$ equals the sum of two elements of $A$.

2011 IMO Shortlist, 1

Tags: number theory , set

Given any set $A = \{a_1, a_2, a_3, a_4\}$ of four distinct positive integers, we denote the sum $a_1 +a_2 +a_3 +a_4$ by $s_A$. Let $n_A$ denote the number of pairs $(i, j)$ with $1 \leq i < j \leq 4$ for which $a_i +a_j$ divides $s_A$. Find all sets $A$ of four distinct positive integers which achieve the largest possible value of $n_A$. [i]Proposed by Fernando Campos, Mexico[/i]

2010 Contests, 3

Tags: set , set theory , interval , union , intersection

Let $I_1, I_2, I_3$ be three open intervals of $\mathbb{R}$ such that none is contained in another. If $I_1\cap I_2 \cap I_3$ is non-empty, then show that at least one of these intervals is contained in the union of the other two.

2009 Ukraine Team Selection Test, 3

Tags: set , combinatorics , subset

Let $S$ be a set consisting of $n$ elements, $F$ a set of subsets of $S$ consisting of $2^{n-1}$ subsets such that every three such subsets have a non-empty intersection. a) Show that the intersection of all subsets of $F$ is not empty. b) If you replace the number of sets from $2^{n-1}$ with $2^{n-1}-1$, will the previous answer change?

2016 Indonesia TST, 3

Tags: set , extremal combinatorics , combinatorics

Let $\{E_1, E_2, \dots, E_m\}$ be a collection of sets such that $E_i \subseteq X = \{1, 2, \dots, 100\}$, $E_i \neq X$, $i = 1, 2, \dots, m$. It is known that every two elements of $X$ is contained together in exactly one $E_i$ for some $i$. Determine the minimum value of $m$.

2024 Israel TST, P3

Tags: geometry , set , distance , combinatorial geometry , combinatorics

For a set $S$ of at least $3$ points in the plane, let $d_{\text{min}}$ denote the minimal distance between two different points in $S$ and $d_{\text{max}}$ the maximal distance between two different points in $S$. For a real $c>0$, a set $S$ will be called $c$-[i]balanced[/i] if \[\frac{d_{\text{max}}}{d_{\text{min}}}\leq c|S|\] Prove that there exists a real $c>0$ so that for every $c$-balanced set of points $S$, there exists a triangle with vertices in $S$ that contains at least $\sqrt{|S|}$ elements of $S$ in its interior or on its boundary.

2016 Indonesia TST, 1

Tags: set , abstract algebra , number theory

Let $k$ and $n$ be positive integers. Determine the smallest integer $N \ge k$ such that the following holds: If a set of $N$ integers contains a complete residue modulo $k$, then it has a non-empty subset whose sum of elements is divisible by $n$.

2017 Bosnia and Herzegovina Junior BMO TST, 2

Tags: combinatorics , set , subset

Let $A$ be a set $A=\{1,2,3,...,2017\}$. Subset $S$ of set $A$ is [i]good [/i] if for all $x\in A$ sum of remaining elements of set $S$ has same last digit as $x$. Prove that [i]good[/i] subset with $405$ elements is not possible.

2004 Regional Olympiad - Republic of Srpska, 4

Tags: set , combinatorics , subset , division , disjoint

Set $S=\{1,2,...,n\}$ is firstly divided on $m$ disjoint nonempty subsets, and then on $m^2$ disjoint nonempty subsets. Prove that some $m$ elements of set $S$ were after first division in same set, and after the second division were in $m$ different sets

2018 India PRMO, 22

Tags: combinatorics , set , partition , sum , subset

A positive integer $k$ is said to be [i]good [/i] if there exists a partition of $ \{1, 2, 3,..., 20\}$ into disjoint proper subsets such that the sum of the numbers in each subset of the partition is $k$. How many [i]good [/i] numbers are there?

MathLinks Contest 6th, 4.1

Tags: combinatorics , set

Let $F$ be a family of n subsets of a set $K$ with $5$ elements, such that any two subsets in $F$ have a common element. Find the minimal value of $n$ such that no matter how we choose $F$ with the properties above, there exists exactly one element of $K$ which belongs to all the sets in $F$.

2018 IFYM, Sozopol, 1

Tags: algebra , set , inequality

$A = \{a_1, a_2, . . . , a_k\}$ is a set of positive integers for which the sum of some (we can have only one number too) different numbers from the set is equal to a different number i.e. there $2^k - 1$ different sums of different numbers from $A$. Prove that the following inequality holds: $\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_k}<2$

2018 IMAR Test, 3

Tags: set , combinatorics

Let $S$ be a finite set and let $\mathcal{P}(S)$ be its power set, i.e., the set of all subsets of $S$, the empty set and $S$, inclusive. If $\mathcal{A}$ and $\mathcal{B}$ are non-empty subsets of $\mathcal{P}(S),$ let \[\mathcal{A}\vee \mathcal{B}=\{X:X\subseteq A\cup B,A\in\mathcal{A},B\in\mathcal{B}\}.\] Given a non-negative integer $n\leqslant |S|,$ determine the minimal size $\mathcal{A}\vee \mathcal{B}$ may have, where $\mathcal{A}$ and $\mathcal{B}$ are non-empty subsets of $\mathcal{P}(S)$ such that $|\mathcal{A}|+|\mathcal{B}|>2^n$. [i]Amer. Math. Monthly[/i]

2024 Nordic, 4

Tags: set , combinatorics

Alice and Bob are playing a game. First, Alice chooses a partition $\mathcal{C}$ of the positive integers into a (not necessarily finite) set of sets, such that each positive integer is in exactly one of the sets in $\mathcal{C}$. Then Bob does the following operation a finite number of times. Choose a set $S \in \mathcal{C}$ not previously chosen, and let $D$ be the set of all positive integers dividing at least one element in $S$. Then add the set $D \setminus S$ (possibly the empty set) to $\mathcal{C}$. Bob wins if there are two equal sets in $\mathcal{C}$ after he has done all his moves, otherwise, Alice wins. Determine which player has a winning strategy.

2013 Indonesia MO, 8

Tags: set , modular arithmetic , combinatorics

Let $A$ be a set of positive integers. $A$ is called "balanced" if [and only if] the number of 3-element subsets of $A$ whose elements add up to a multiple of $3$ is equal to the number of 3-element subsets of $A$ whose elements add up to not a multiple of $3$. a. Find a 9-element balanced set. b. Prove that no set of $2013$ elements can be balanced.

2022 AMC 10, 14

Tags: set

Suppose that $S$ is a subset of $\{1, 2, 3,...,25\}$ such that the sum of any two (not necessarily distinct) elements of $S$ is never an element of $S$. What is the maximum number of elements $S$ may contain? $\textbf{(A) }12 \qquad \textbf{(B) }13 \qquad \textbf{(C) }14 \qquad \textbf{(D) }15 \qquad \textbf{(E) }16$

2020 China Northern MO, BP5

Tags: combinatorics , set , number theory , relatively prime

It is known that subsets $A_1,A_2, \cdots , A_n$ of set $I=\{1,2,\cdots ,101\}$ satisfy the following condition $$\text{For any } i,j \text{ } (1 \leq i < j \leq n) \text{, there exists } a,b \in A_i \cap A_j \text{ so that } (a,b)=1$$ Determine the maximum positive integer $n$. *$(a,b)$ means $\gcd (a,b)$

2025 Philippine MO, P1

Tags: combinatorics , set , subset , difference

The set $S$ is a subset of $\{1, 2, \dots, 2025\}$ such that no two elements of $S$ differ by $2$ or by $7$. What is the largest number of elements that $S$ can have?

2019 Belarusian National Olympiad, 9.4

Tags: combinatorics , partition , set

The sum of several (not necessarily different) positive integers not exceeding $10$ is equal to $S$. Find all possible values of $S$ such that these numbers can always be partitioned into two groups with the sum of the numbers in each group not exceeding $70$. [i](I. Voronovich)[/i]

2016 Saudi Arabia IMO TST, 3

Tags: combinatorics , set , subset

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

2022 SG Originals, Q2

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

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