Putnam 2013, Problem B-3

Let \( \mathcal{P} \) be a nonempty collection of subsets of \( \{1, \ldots, n\} \) such that:
(i) if \( S, S' \in \mathcal{P} \), then \( S \cup S' \in \mathcal{P} \) and \( S \cap S' \in \mathcal{P} \), and
(ii) if \( S \in \mathcal{P} \) and \( S \neq \emptyset \), then there is a subset \( T \subset S \) such that \( T \in \mathcal{P} \) and \( T \) contains exactly one fewer element than \( S \).

Suppose that \( f : \mathcal{P} \to \mathbb{R} \) is a function such that \( f(\emptyset) = 0 \) and
\[
f(S \cup S') = f(S) + f(S') - f(S \cap S')
\]
for all \( S, S' \in \mathcal{P} \).

Must there exist real numbers \( f_1, \ldots, f_n \) such that
\[
f(S) = \sum_{i \in S} f_i
\]
for every \( S \in \mathcal{P} \)?


Solution:
Yes, such numbers must exist. To define them, we make the following observations.

**Lemma 1.** For any $i \in \{1, \ldots, n\}$, if there exists any $S \in P$ containing $i$, then there exist $S,T \in P$ such that $S$ is the disjoint union of $T$ with $\{i\}$.

*Proof.* Let $S$ be an element of $P$ containing $i$ of minimum cardinality. By (ii), there must be a subset $T \subset S$ containing $P$ with exactly one fewer element than $S$. These sets have the desired form. $\square$

**Lemma 2.** Suppose $S_1, S_2, T_1, T_2 \in P$ have the property that for some $i \in \{1, \ldots, n\}$, $S_1$ is the disjoint union of $T_1$ with $\{i\}$ and $S_2$ is the disjoint union of $T_2$ with $\{i\}$. Then

$$f(S_1) - f(T_1) = f(S_2) - f(T_2).$$

*Proof.* By (i) we have

$$f(T_1 \cup T_2 \cup \{i\}) = f(S_1) + f(T_2) - f(T_1 \cap T_2)$$
$$f(T_1 \cup T_2 \cup \{i\}) = f(T_1) + f(S_2) - f(T_1 \cap T_2),$$

from which the claim follows immediately. $\square$

We now define $f_1, \ldots, f_n$ as follows. If $i$ does not appear in any element of $P$, we put $f_i = 0$. Otherwise, by Lemma 1, we can find $S,T \in P$ such that $S$ is the disjoint union of $T$ with $\{i\}$. We then set $f_i = f(S) - f(T)$; by Lemma 2, this does not depend on the choice of $S,T$.

To check that $f(S) = \sum_{i \in S} f_i$ for $S \in P$, note first that $\emptyset \in P$ by repeated application of (ii) and that $f(\emptyset) = 0$ by hypothesis. This provides the base case for an induction on the cardinality of $S$; for any nonempty $S \in P$, we may apply (ii) to find $T \subset S$ such that $S$ is the disjoint union of $T$ and some singleton set $\{j\}$. By construction and the induction hypothesis, we have $f(S) = f(T) + f_j = j + \sum_{i \in T} f_i = \sum_{i \in S} f_i$ as desired.