Question 22: Let n and N be positive integers, and let \mathcal{F} be…

Let $n$ and $N$ be positive integers, and let $\mathcal{F}$ be an arbitrary nonempty family of subsets of the universe $\{1, \ldots, n\}$. Suppose each element $x \in \{1, \ldots, n\}$ in the universe receives an integer weight $w(x)$, each of which is chosen independently and uniformly at random from $\{1, \ldots, N\}$. The weight of a set $S$ in $\mathcal{F}$ is defined as

$w(S) = \sum_{x \in S} w(x)$

We want to explore the probability of the following "good" event: there is a unique set in $\mathcal{F}$ that has the minimum weight among all sets of $\mathcal{F}$.

Based on the above data, answer the given subquestions.

We introduce some notation:

• Let $\mathcal{P}_i \subseteq \mathcal{F}$ denote all those sets in $\mathcal{F}$ that contain $i$, and
• let $\mathcal{Q}_i \subseteq \mathcal{F}$ denote all those sets in $\mathcal{F}$ that do not contain $i$.

Notice that $\mathcal{Q}_i = \mathcal{F} \setminus \mathcal{P}_i$. For example, if $\mathcal{F} = \{\{1\}, \{1, 2\}, \{2, 3\}\}$, then:

• $\mathcal{P}_1 = \{\{1\}, \{1, 2\}\}$ and $\mathcal{Q}_1 = \{\{2, 3\}\}$, and
• $\mathcal{P}_2 = \{\{1, 2\}, \{2, 3\}\}$ and $\mathcal{Q}_2 = \{\{1\}\}$, and
• $\mathcal{P}_3 = \{\{2, 3\}\}$ and $\mathcal{Q}_3 = \{\{1\}, \{1, 2\}\}$.

Let $\mathcal{E}_i$ be the event:

$\min\{w(S) : \mathcal{P}_i\} = \min\{w(S) : S \in \mathcal{Q}_i\}.$

We can conclude that the good event occurs if: