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) |. \]
Problem
Source: Romanian TST 3 2007, Problem 1
Tags: function, inequalities, algebra, domain, combinatorics proposed, combinatorics
Aryabhatta
23.05.2007 21:35
Valentin Vornicu wrote: 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 partitions). Find \[\max_{f \in \mathcal{F}}| \textrm{Im}(f) |. \] Sorry, your terminology is confusing. Is $\mathcal{P}(S)$ the power set of $S$? i.e the set of all subsets of $S$? If $\mathcal{P}(S)$ is the set of partitions of $S$ and If $X \subseteq S$ then $X \not\in \mathcal{P}(S)$, so talking about $f(X)$ would not make sense.
pohoatza
23.05.2007 21:46
$P(S)$ is indeed the set of subsets of $S$, and yes, you are right, it is a typo in the enuntiation, $X, Y \in P(S)$, instead of $X, Y \in S$.
JBL
23.05.2007 21:48
${\mathcal P}(S)$ is the powerset of $S$, i.e. the set of its subsets, but he does mean $X, Y \subseteq S$ (which is equivalent to $X, Y \in{\mathcal P}(S)$), not what pohoatza said.
If $S$ has $n$ elements, then we can always achieve $n+1$ values, as follows: choose any chain $\emptyset = X_{0}\subset X_{1}\subset \ldots \subset X_{n}= S$. Then define $f(Y) = \max_{i}(X_{i}\subseteq Y)$. Then for any $Y, Z$,
\begin{eqnarray*}f(Y \cap Z) &=& \max_{i}(X_{i}\subseteq(Y\cap Z)) \\ &=& \max_{i}(X_{i}\subseteq Y\textrm{ and }X_{i}\subseteq Z) \\ &=& \min\{\max_{i}(X_{i}\subseteq Y),\max_{i}(X_{i}\subseteq Z)\}\\ &=& \min\{f(Y), f(Z)\}, \end{eqnarray*}
as desired.
pohoatza
23.05.2007 21:59
Yes JBL, I meant $X,Y \in P(S)$, anyway your answer is correct.
JBL
23.05.2007 22:23
Here is the proof we cannot do better:
Let $|S| = n$, and consider the values on the $n-1$-element subsets of $S$, $X_{1}, X_{2}, \ldots, X_{n}$. Choose any set $X \subset S$, $|X| = n-i$, and without loss of generality let $X_{1}, X_{2}, \ldots, X_{i}$ be the $n-1$-element supersets of $X$ in $S$. Also without loss of generality, assume $f(X_{1}) \leq f(X_{2}) \leq\ldots\leq f(X_{i})$. Then
\[f(X) = f(X_{i}\cap(X_{i-1}\cap\ldots(X_{2}\cap X_{1}))) = f(X_{i-1}\cap\ldots(X_{2}\cap X_{1})) = \ldots = f(X_{2}\cap X_{1}) = f(X_{1}), \]
where the leftmost equality follows from the equality of the sets involved while the other inequalities follow from right to left by the given property of $f$. Thus, the values of $f$ on all sets other than $S$ itself are among these $n$ values, so $f$ can take at most $n+1$ different values.
gubin
19.06.2007 11:20
i think the value for the question is positive infinte. As i haven't find the way send my prove, so pls wait me..
JBL
22.06.2007 19:17
The domain of $f$ is finite, so I'm not sure how you expect to make its range infinite. In any event, I have already posted a complete proof.
gubin
26.07.2007 14:35
ok, i am sure the value is n+1.