Olympiad problems

2016 VJIMC, 2

Tags: set theory

Let $X$ be a set and let $\mathcal{P}(X)$ be the set of all subsets of $X$. Let $\mu: \mathcal{P}(X) \to \mathcal{P}(X)$ be a map with the property that $\mu(A \cup B) = \mu(A) \cup \mu(B)$ whenever $A$ and $B$ are disjoint subsets of $X$. Prove that there exists $F \subset X$ such that $\mu(F) = F$.

2009 Balkan MO Shortlist, C2

Tags: combinatorics , linear algebra , set theory

Let $A_1, A_2, \ldots , A_m$ be subsets of the set $\{ 1,2, \ldots , n \}$, such that the cardinal of each subset $A_i$, such $1 \le i \le m$ is not divisible by $30$, while the cardinal of each of the subsets $A_i \cap A_j$ for $1 \le i,j \le m$, $i \neq j$ is divisible by $30$. Prove \begin{align*} 2m - \left \lfloor \frac{m}{30} \right \rfloor \le 3n \end{align*}

1989 Balkan MO, 4

Tags: set theory , combinatorics

The elements of the set $F$ are some subsets of $\left\{1,2,\ldots ,n\right\}$ and satisfy the conditions: i) if $A$ belongs to $F$, then $A$ has three elements; ii)if $A$ and $B$ are distinct elements of $F$ , then $A$ and $B$ have at most one common element. Let $f(n)$ be the greatest possible number of elements of $F$. Prove that $\frac{n^{2}-4n}{6}\leq f(n) \leq \frac{n^{2}-n}{6}$

2024 Junior Balkan Team Selection Tests - Romania, P4

Tags: combinatorics , set theory

Let $n\geqslant 3$ be a positive integer and $N=\{1,2,\ldots,n\}$ and let $k>0$ be a real number. Let's associate each non-empty of $N{}$ with a point in the plane, such that any two distinct subsets correspond to different points. If the absolute value of the difference between the arithmetic means of the elements of two distinct non-empty subsets of $N{}$ is at most $k{}$ we connect the points associated with these subsets with a segment. Determine the minimum value of $k{}$ such that the points associated with any two distinct non-empty subsets of $N{}$ are connected by a segment or a broken line. [i]Cristi Săvescu[/i]

2000 VJIMC, Problem 1

Tags: set theory , infinity , real analysis , set

Is there a countable set $Y$ and an uncountable family $\mathcal F$ of its subsets such that for every two distinct $A,B\in\mathcal F$, their intersection $A\cap B$ is finite?

2022 Vietnam TST, 6

Tags: set theory , important numbers , combinatorics , coloring

Given a set $A=\{1;2;...;4044\}$. They color $2022$ numbers of them by white and the rest of them by black. With each $i\in A$, called the [b][i]important number[/i][/b] of $i$ be the number of all white numbers smaller than $i$ and black numbers larger than $i$. With every natural number $m$, find all positive integers $k$ that exist a way to color the numbers that can get $k$ important numbers equal to $m$.

2001 Miklós Schweitzer, 1

Tags: function , set theory , real analysis

Let $f\colon 2^S\rightarrow \mathbb R$ be a function defined on the subsets of a finite set $S$. Prove that if $f(A)=F(S\backslash A)$ and $\max \{ f(A), f(B)\}\geq f(A\cup B)$ for all subsets $A, B$ of $S$, then $f$ assumes at most $|S|$ distinct values.

2017 China Team Selection Test, 3

Tags: combinatorics , set theory , quadratic residue

Find the numbers of ordered array $(x_1,...,x_{100})$ that satisfies the following conditions: ($i$)$x_1,...,x_{100}\in\{1,2,..,2017\}$; ($ii$)$2017|x_1+...+x_{100}$; ($iii$)$2017|x_1^2+...+x_{100}^2$.

2002 District Olympiad, 4

Tags: set theory , counting , algebra , closedness

For any natural number $ n\ge 2, $ define $ m(n) $ to be the minimum number of elements of a set $ S $ that simultaneously satisfy: $ \text{(i)}\quad \{ 1,n\} \subset S\subset \{ 1,2,\ldots ,n\} $ $ \text{(ii)}\quad $ any element of $ S, $ distinct from $ 1, $ is equal to the sum of two (not necessarily distinct) elements from $ S. $ [b]a)[/b] Prove that $ m(n)\ge 1+\left\lfloor \log_2 n \right\rfloor ,\quad\forall n\in\mathbb{N}_{\ge 2} . $ [b]b)[/b] Prove that there are infinitely many natural numbers $ n\ge 2 $ such that $ m(n)=m(n+1). $ $ \lfloor\rfloor $ denotes the usual integer part.

2012 IFYM, Sozopol, 5

Tags: combinatorics , set theory

We denote with $p_n(k)$ the number of permutations of the numbers $1,2,...,n$ that have exactly $k$ fixed points. a) Prove that $\sum_{k=0}^n kp_n (k)=n!$. b) If $s$ is an arbitrary natural number, then: $\sum_{k=0}^n k^s p_n (k)=n!\sum_{i=1}^m R(s,i)$, where with $R(s,i)$ we denote the number of partitions of the set $\{1,2,...,s\}$ into $i$ non-empty non-intersecting subsets and $m=min(s,n)$.