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

Categories: Combinatorics, IMO, Olympiad Tags: ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: