Olympiad problems

1996 Italy TST, 2

2. Let $A_1,A_2,...,A_n$be distinct subsets of an n-element set $ X$ ($n \geq 2$). Show that there exists an element $x$ of $X$ such that the sets $A_1\setminus \{x\}$ ,:......., $A_n\setminus \{x\}$ are all distinct.

2008 Iran Team Selection Test, 7

Let $ S$ be a set with $ n$ elements, and $ F$ be a family of subsets of $ S$ with $ 2^{n\minus{}1}$ elements, such that for each $ A,B,C\in F$, $ A\cap B\cap C$ is not empty. Prove that the intersection of all of the elements of $ F$ is not empty.

induction boolean lattice method combinatorics floor function floor and ceiling functions mathematical induction

1988 USAMO, 3

A function $f(S)$ assigns to each nine-element subset of $S$ of the set $\{1,2,\ldots, 20\}$ a whole number from $1$ to $20$. Prove that regardless of how the function $f$ is chosen, there will be a ten-element subset $T\subset\{1,2,\ldots, 20\}$ such that $f(T - \{k\})\neq k$ for all $k\in T$.

function boolean lattice method pigeonhole principle ceiling function algebra combinatorics floor and ceiling functions graph modeling

2012 Stars of Mathematics, 4

Consider a set $X$ with $|X| = n\geq 1$ elements. A family $\mathcal{F}$ of distinct subsets of $X$ is said to have property $\mathcal{P}$ if there exist $A,B \in \mathcal{F}$ so that $A\subset B$ and $|B\setminus A| = 1$. i) Determine the least value $m$, so that any family $\mathcal{F}$ with $|\mathcal{F}| > m$ has property $\mathcal{P}$. ii) Describe all families $\mathcal{F}$ with $|\mathcal{F}| = m$, and not having property $\mathcal{P}$. ([i]Dan Schwarz[/i])

boolean lattice method combinatorics bijection modular arithmetic pigeonhole principle