Olympiad problems

2020 China Northern MO, BP5

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

2021 Science ON grade VI, 3

Tags: pigeonhole principle , combinatorics , set

Consider positive integers $a<b$ and the set $C\subset\{a,a+1,a+2,\dots ,b-2,b-1,b\}$. Suppose $C$ has more than $\frac{b-a+1}{2}$ elements. Prove that there are two elements $x,y\in C$ that satisfy $x+y=a+b$. [i] (From "Radu Păun" contest, Radu Miculescu)[/i]

2024 Romanian Master of Mathematics, 3

Tags: geometry , combinatorics , linear algebra , combinatorial geometry , set

Given a positive integer $n$, a collection $\mathcal{S}$ of $n-2$ unordered triples of integers in $\{1,2,\ldots,n\}$ is [i]$n$-admissible[/i] if for each $1 \leq k \leq n - 2$ and each choice of $k$ distinct $A_1, A_2, \ldots, A_k \in \mathcal{S}$ we have $$ \left|A_1 \cup A_2 \cup \cdots A_k \right| \geq k+2.$$ Is it true that for all $n > 3$ and for each $n$-admissible collection $\mathcal{S}$, there exist pairwise distinct points $P_1, \ldots , P_n$ in the plane such that the angles of the triangle $P_iP_jP_k$ are all less than $61^{\circ}$ for any triple $\{i, j, k\}$ in $\mathcal{S}$? [i]Ivan Frolov, Russia[/i]

2019 India PRMO, 30

Tags: sum , set

Let $E$ denote the set of all natural numbers $n$ such that $3 < n < 100$ and the set $\{ 1, 2, 3, \ldots , n\}$ can be partitioned in to $3$ subsets with equal sums. Find the number of elements of $E$.

2020 Iran MO (3rd Round), 4

Tags: combinatorics , subset , set

What is the maximum number of subsets of size $5$, taken from the set $A=\{1,2,3,...,20\}$ such that any $2$ of them share exactly $1$ element.

1979 VTRMC, 2

Tags: set

Let $S$ be a set which is closed under the binary operation $\circ$, with the following properties: (i) there is an element $e \in S$ such that $a \circ e = e \circ a = a$, for each $a \in S$. (ii) $(a \circ b) \circ (c \circ d)=(a \circ c) \circ (b \circ d)$, for all $a,b, c,d \in S$. Prove or disprove: (a) $\circ$ is associative on S (b) $\circ$ is commutative on S

1983 Austrian-Polish Competition, 4

Tags: number theory , positive integer , partition , set

The set $N$ has been partitioned into two sets A and $B$. Show that for every $n \in N$ there exist distinct integers $a, b > n$ such that $a, b, a + b$ either all belong to $A$ or all belong to $B$.

2017 Thailand TSTST, 1

Tags: combinatorics , table , coloring , number theory , algebra , set

1.1 Let $f(A)$ denote the difference between the maximum value and the minimum value of a set $A$. Find the sum of $f(A)$ as $A$ ranges over the subsets of $\{1, 2, \dots, n\}$. 1.2 All cells of an $8 × 8$ board are initially white. A move consists of flipping the color (white to black or vice versa) of cells in a $1\times 3$ or $3\times 1$ rectangle. Determine whether there is a finite sequence of moves resulting in the state where all $64$ cells are black. 1.3 Prove that for all positive integers $m$, there exists a positive integer $n$ such that the set $\{n, n + 1, n + 2, \dots , 3n\}$ contains exactly $m$ perfect squares.

2021-IMOC, N5

Tags: number theory , greatest common divisor , set

Find all sets $S$ of positive integers that satisfy all of the following. $1.$ If $a,b$ are two not necessarily distinct elements in $S$, then $\gcd(a,b)$, $ab$ are also in $S$. $2.$ If $m,n$ are two positive integers with $n\nmid m$, then there exists an element $s$ in $S$ such that $m^2\mid s$ and $n^2\nmid s$. $3.$ For any odd prime $p$, the set formed by moduloing all elements in $S$ by $p$ has size exactly $\frac{p+1}2$.

2015 Bosnia And Herzegovina - Regional Olympiad, 4

Tags: combinatorics , set

Alice and Mary were searching attic and found scale and box with weights. When they sorted weights by mass, they found out there exist $5$ different groups of weights. Playing with the scale and weights, they discovered that if they put any two weights on the left side of scale, they can find other two weights and put on to the right side of scale so scale is in balance. Find the minimal number of weights in the box

1998 Korea Junior Math Olympiad, 8

Tags: set , combinatorics , existence

$T$ is a set of all the positive integers of the form $2^k 3^l$, where $k, l$ are some non-negetive integers. Show that there exists $1998$ different elements of $T$ that satisfy the following condition. [b]Condition[/b] The sum of the $1998$ elements is again an element of $T$.

2023 China Team Selection Test, P14

Tags: inequalities , set

For any nonempty, finite set $B$ and real $x$, define $$d_B(x) = \min_{b\in B} |x-b|$$ (1) Given positive integer $m$. Find the smallest real number $\lambda$ (possibly depending on $m$) such that for any positive integer $n$ and any reals $x_1,\cdots,x_n \in [0,1]$, there exists an $m$-element set $B$ of real numbers satisfying $$d_B(x_1)+\cdots+d_B(x_n) \le \lambda n$$ (2) Given positive integer $m$ and positive real $\epsilon$. Prove that there exists a positive integer $n$ and nonnegative reals $x_1,\cdots,x_n$, satisfying for any $m$-element set $B$ of real numbers, we have $$d_B(x_1)+\cdots+d_B(x_n) > (1-\epsilon)(x_1+\cdots+x_n)$$

1987 China Team Selection Test, 1

Tags: combinatorics , number theoretic functions , set

a.) For all positive integer $k$ find the smallest positive integer $f(k)$ such that $5$ sets $s_1,s_2, \ldots , s_5$ exist satisfying: [b]i.[/b] each has $k$ elements; [b]ii.[/b] $s_i$ and $s_{i+1}$ are disjoint for $i=1,2,...,5$ ($s_6=s_1$) [b]iii.[/b] the union of the $5$ sets has exactly $f(k)$ elements. b.) Generalisation: Consider $n \geq 3$ sets instead of $5$.

KoMaL A Problems 2017/2018, A. 720

Tags: number theory , prime divisor , set

We call a positive integer [i]lively[/i] if it has a prime divisor greater than $10^{10^{100}}$. Prove that if $S$ is an infinite set of lively positive integers, then it has an infinite subset $T$ with the property that the sum of the elements in any finite nonempty subset of $T$ is a lively number.

2016 Indonesia TST, 1

Tags: number theory , abstract algebra , set

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

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

2020 Canadian Mathematical Olympiad Qualification, 2

Tags: subset , combinatorics , partition , set

Given a set $S$, of integers, an [i]optimal partition[/i] of S into sets T, U is a partition which minimizes the value $|t - u|$, where $t$ and $u$ are the sum of the elements of $T$ and U respectively. Let $P$ be a set of distinct positive integers such that the sum of the elements of $P$ is $2k$ for a positive integer $k$, and no subset of $P$ sums to $k$. Either show that there exists such a $P$ with at least $2020$ different optimal partitions, or show that such a $P$ does not exist.

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

1991 French Mathematical Olympiad, Problem 4

Tags: number theory , set

Let $p$ be a nonnegative integer and let $n=2^p$. Consider all subsets $A$ of the set $\{1,2,\ldots,n\}$ with the property that, whenever $x\in A$, $2x\notin A$. Find the maximum number of elements that such a set $A$ can have.

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

2013 Balkan MO Shortlist, N7

Tags: number theory , greatest common divisor , difference , set

Two distinct positive integers are called [i]close [/i] if their greatest common divisor equals their difference. Show that for any $n$, there exists a set $S$ of $n$ elements such that any two elements of $S$ are close.

2020 LIMIT Category 2, 8

Tags: limit , probability , set

Let $S$ be a finite set of size $s\geq 1$ defined with a uniform probability $\mathbb{P}$( i.e. for any subset $X\subset S$ of size $x$, $\mathbb{P}(x)=\frac{x}{s}$). Suppose $A$ and $B$ are subsets of $S$. They are said to be independent iff $\mathbb{P}(A)\mathbb{P}(B)=\mathbb{P}(A\cap B)$. Which if these is sufficient for independence? (A)$|A\cup B|=|A|+|B|$ (B)$|A\cap B|=|A|+|B|$ (C)$|A\cup B|=|A|\cdot |B|$ (D)$|A\cap B|=|A|\cdot |B|$

2018 IMO Shortlist, A3

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

2018 JBMO Shortlist, C1

Tags: combinatorics , subset , set

A set $S$ is called [i]neighbouring [/i] if it has the following two properties: a) $S$ has exactly four elements b) for every element $x$ of $S$, at least one of the numbers $x - 1$ or $x+1$ belongs to $S$. Find the number of all [i]neighbouring [/i] subsets of the set $\{1,2,... ,n\}$.

2013 Junior Balkan Team Selection Tests - Moldova, 2

Tags: number theory , set

Determine the elements of the sets $A = \{x \in N | x \ne 4a + 7b, a, b \in N\}$, $B = \{x \in N | x\ne 3a + 11b, a, b \in N\}$.