Home > Combinatorics, IMO, Olympiad > Another function on Subsets

## Another function on Subsets

Let $\mathcal{F}$ be the set of all the functions $f : \mathcal{P}(S) \longrightarrow \mathbb{R}$ such that for all $X, Y \subseteq S$, we have $f(X \cap Y) = \min (f(X), f(Y))$, where $S$ is a finite set (and $\mathcal{P}(S)$ is the set of its subsets). Find $\max_{f \in \mathcal{F}}| \textrm{Im}(f) |$.
Romanian TST, 2007
Suppose $X_1,...,X_n$ are the $n-1$ elements subsets of $S,\ |S|=n$, such that $f(X_1)\leq f(X_2)\leq ... \leq f(X_n)$ (WLOG).

Then, for any $n-i$ elements ($i \geq 1$) subset $X$ of $S$ we can write $X=\displaystyle \bigcap_{k=1}^i X_{i_k}$, and by the hypothesis $f(X)=f(X_{i_1})$. Therefore, any subset of $S$, different from $S$ takes values among $f(X_1),...,f(X_n)$.

This means that the image of $f$ cannot have more than $n+1$ elements, and we can reach this limit case, by choosing distinct values for $f(X_1),...,f(X_n),f(S)$.