Olympiad problems

1964 Putnam, B2

Let $S$ be a set of $n>0$ elements, and let $A_1 , A_2 , \ldots A_k$ be a family of distinct subsets such that any two have a non-empty intersection. Assume that no other subset of $S$ intersects all of the $A_i.$ Prove that $ k=2^{n-1}.$

2016 IFYM, Sozopol, 7

Tags: number theory , set theory

Let $S$ be a set of integers which has the following properties: 1) There exists $x,y\in S$ such that $(x,y)=(x-2,y-2)=1$; 2) For $\forall$ $x,y\in S, x^2-y\in S$. Prove that $S\equiv \mathbb{Z}$ .

2023 Turkey Team Selection Test, 4

Tags: set theory , combinatorics

Let $k$ be a positive integer and $S$ be a set of sets which have $k$ elements. For every $A,B \in S$ and $A\neq B$ we have $A \Delta B \in S$. Find all values of $k$ when $|S|=1023$ and $|S|=2023$. Note:$A \Delta B = (A \setminus B) \cup (B \setminus A)$

2000 Tuymaada Olympiad, 1

Tags: analytic geometry , topology , set theory , combinatorics

Can the plane be coloured in 2000 colours so that any nondegenerate circle contains points of all 2000 colors?

2006 Singapore MO Open, 4

Tags: combinatorics , set , set theory , double counting

Let $n$ be positive integer. Let $S_1,S_2,\cdots,S_k$ be a collection of $2n$-element subsets of $\{1,2,3,4,...,4n-1,4n\}$ so that $S_{i}\cap S_{j}$ contains at most $n$ elements for all $1\leq i<j\leq k$. Show that $$k\leq 6^{(n+1)/2}$$

2010 IFYM, Sozopol, 4

Tags: set theory , combinatorics

The sets $A_1,A_2,...,A_n$ are finite. With $d$ we denote the number of elements in $\bigcup_{i=1}^n A_i$ which are in odd number of the sets $A_i$. Prove that the number: $D(k)=d-\sum_{i=1}^n|A_i|+2\sum_{i<j}|A_i\cap A_j |+...+(-1)^k2^{k-1}\sum_{i_1<i_2<...<i_k}|A_{i_1}\cap A_{i_2}\cap ...\cap A_{i_k}|$ is divisible by $2^k$.

KoMaL A Problems 2020/2021, A. 797

Tags: combinatorics , set theory

We call a system of non-empty sets $H$ [i]entwined[/i], if for every disjoint pair of sets $A$ and $B$ in $H$ there exists $b\in B$ such that $A\cup\{b\}$ is in $H$ or there exists $a\in A$ such that $B\cup\{a\}$ is in $H.$ Let $H$ be an entwined system of sets containing all of $\{1\},\{2\},\ldots,\{n\}.$ Prove that if $n>k(k+1)/2,$ then $H$ contains a set with at least $k+1$ elements, and this is sharp for every $k,$ i.e. if $n=k(k+1),$ it is possible that every set in $H$ has at most $k$ elements.

2020 Macedonian Nationаl Olympiad, 4

Tags: combinatorics , set theory

Let $S$ be a nonempty finite set, and $\mathcal {F}$ be a collection of subsets of $S$ such that the following conditions are met: (i) $\mathcal {F}$ $\setminus$ {$S$} $\neq$ $\emptyset$ ; (ii) if $F_1, F_2 \in \mathcal {F}$, then $F_1 \cap F_2 \in \mathcal {F}$ and $F_1 \cup F_2 \in \mathcal {F}$. Prove that there exists $a \in S$ which belongs to at most half of the elements of $\mathcal {F}$.

2015 IFYM, Sozopol, 8

Tags: set theory , discrete geometry

The points $A_1,A_...,A_n$ lie on a circle with radius 1. The points $B_1,B_2,…,B_n$ are such that $B_i B_j<A_i A_j$ for $i\neq j$. Is it always true that the points $B_1,B_2,...,B_n$ lie on a circle with radius lesser than 1?

2023 Hong Kong Team Selection Test, Problem 3

Tags: algebra , set theory

Let $n\ge 4$ be a positive integer. Consider any set $A$ formed by $n$ distinct real numbers such that the following condition holds: for every $a\in A$, there exist distinct elements $x, y, z \in A$ such that $\left| x-a \right|, \left| y-a \right|, \left| z-a \right| \ge 1$. For each $n$, find the greatest real number $M$ such that $\sum_{a\in A}^{}\left| a \right|\ge M$.

2003 Gheorghe Vranceanu, 4

Tags: set equation , equation , set theory , algebra

Having three sets $ A,B\subset C, $ solve the set equation $ (X\cup (C\setminus A))\cap ((C\setminus X)\cup A)=B. $

1989 Putnam, B4

Tags: infinity , set theory

Can a countably infinite set have an uncountable collection of non-empty subsets such that the intersection of any two of them is finite?

2017 Polish MO Finals, 4

Tags: set theory , combinatorics

Prove that the set of positive integers $\mathbb Z^+$ can be represented as a sum of five pairwise distinct subsets with the following property: each $5$-tuple of numbers of form $(n,2n,3n,4n,5n)$, where $n\in\mathbb Z^+$, contains exactly one number from each of these five subsets.

2022 IFYM, Sozopol, 8

Tags: set theory

A subset of the set $A={1,2,\dots ,n}$ is called [i]connected[/i], if it consists of one number or a certain amount of consecutive numbers. Find the greatest $k$ (defined as a function of $n$) for which there exists $k$ different subsets $A_1,A_2,…,A_k$ of $A$ the intersection of each two of which is a [i]connected[/i] set.

2020 Harvest Math Invitational Team Round Problems, HMI Team #2

Tags: hmmt , set theory

2. Let $A$ be a set of $2020$ distinct real numbers. Call a number [i]scarily epic[/i] if it can be expressed as the product of two (not necessarily distinct) numbers from $A$. What is the minimum possible number of distinct [i]scarily epic[/i] numbers? [i]Proposed by Monkey_king1[/i]

2009 Serbia National Math Olympiad, 3

Tags: combinatorics , set systems , set theory , graph theory , inclusion-exclusion , set

Determine the largest positive integer $n$ for which there exist pairwise different sets $\mathbb{S}_1 , ..., \mathbb{S}_n$ with the following properties: $1$) $|\mathbb{S}_i \cup \mathbb{S}_j | \leq 2004$ for any two indices $1 \leq i, j\leq n$, and $2$) $\mathbb{S}_i \cup \mathbb{S}_j \cup \mathbb{S}_k = \{ 1,2,...,2008 \}$ for any $1 \leq i < j < k \leq n$ [i]Proposed by Ivan Matic[/i]

2010 IMC, 4

Tags: function , abstract algebra , quadratic , set theory , number theory

Let $a,b$ be two integers and suppose that $n$ is a positive integer for which the set $\mathbb{Z} \backslash \{ax^n + by^n \mid x,y \in \mathbb{Z}\}$ is finite. Prove that $n=1$.

2008 Miklós Schweitzer, 5

Tags: asymptotics , set theory , real analysis

Let $A$ be an infinite subset of the set of natural numbers, and denote by $\tau_A(n)$ the number of divisors of $n$ in $A$. Construct a set $A$ for which $$\sum_{n\le x}\tau_A(n)=x+O(\log\log x)$$ and show that there is no set for which the error term is $o(\log\log x)$ in the above formula. (translated by Miklós Maróti)

2011 Laurențiu Duican, 2

Tags: function , set theory

Consider a finite set $ A, $ and two functions $ f,g: A\longrightarrow A. $ Prove that: $$ |\{ x\in A| g(f(x))\neq x \} | =|\{ x\in A| f(g(x))\neq x \} | $$ [i]Cristinel Mortici[/i]

2020 Bangladesh Mathematical Olympiad National, Problem 9

Tags: set theory , algebra

Bristy wants to build a special set $A$. She starts with $A=\{0, 42\}$. At any step, she can add an integer $x$ to the set $A$ if it is a root of a polynomial which uses the already existing integers in $A$ as coefficients. She keeps doing this, adding more and more numbers to $A$. After she eventually runs out of numbers to add to $A$, how many numbers will be in $A$?

2007 Miklós Schweitzer, 6

Tags: set theory

For which subsets $A\subset \mathbb R$ is it true that whenever $0\leq x_0 < x_1 < \cdots < x_n\leq 1$, $n=1,2, \ldots$, then there exist $y_j\in A$ numbers, such that $y_{j+1}-y_j>x_{j+1}-x_j$ for all $0\leq j < n$. (translated by Miklós Maróti)

2016 IMC, 4

Tags: set theory , set

Let $n\ge k$ be positive integers, and let $\mathcal{F}$ be a family of finite sets with the following properties: (i) $\mathcal{F}$ contains at least $\binom{n}{k}+1$ distinct sets containing exactly $k$ elements; (ii) for any two sets $A, B\in \mathcal{F}$, their union $A\cup B$ also belongs to $\mathcal{F}$. Prove that $\mathcal{F}$ contains at least three sets with at least $n$ elements. (Proposed by Fedor Petrov, St. Petersburg State University)

2012 All-Russian Olympiad, 4

Tags: graph theory , combinatorics , set theory

In a city's bus route system, any two routes share exactly one stop, and every route includes at least four stops. Prove that the stops can be classified into two groups such that each route includes stops from each group.

2012 India Regional Mathematical Olympiad, 6

Tags: subset , set theory , combinatorics , combinatorics of set

Let $S$ be the set $\{1, 2, ..., 10\}$. Let $A$ be a subset of $S$. We arrange the elements of $A$ in increasing order, that is, $A = \{a_1, a_2, ...., a_k\}$ with $a_1 < a_2 < ... < a_k$. Define [i]WSUM [/i] for this subset as $3(a_1 + a_3 +..) + 2(a_2 + a_4 +...)$ where the first term contains the odd numbered terms and the second the even numbered terms. (For example, if $A = \{2, 5, 7, 8\}$, [i]WSUM [/i] is $3(2 + 7) + 2(5 + 8)$.) Find the sum of [i]WSUMs[/i] over all the subsets of S. (Assume that WSUM for the null set is $0$.)

2001 VJIMC, Problem 4

Tags: set theory

Let $A,B,C$ be nonempty sets in $\mathbb R^n$. Suppose that $A$ is bounded, $C$ is closed and convex, and $A+B\subseteq A+C$. Prove that $B\subseteq C$. Recall that $E+F=\{e+f:e\in E,f\in F\}$ and $D\subseteq\mathbb R^n$ is convex iff $tx+(1-t)y\in D$ for all $x,y\in D$ and any $t\in[0,1]$.