= Solution
Let $\mathcal Q$ be the set of valid quintuples and choose $(A_1,\ldots,A_5)$ uniformly from $\mathcal Q$. Then
$$
H(A_1,\ldots,A_5)=\log|\mathcal Q|.
$$
Apply <Shearer's inequality> to the ten pairs $\{i,j\}\subseteq[5]$. Every index occurs in four pairs, so
$$
4H(A_1,\ldots,A_5)\leq\sum_{1\leq i<j\leq5}H(A_i,A_j).
$$
Put $U_{ij}=A_i\cup A_j$. Since $U_{ij}\in\mathcal A$, it has cardinality $k$. For each element of $U_{ij}$, its membership bits in $(A_i,A_j)$ are one of $(1,0),(0,1),(1,1)$; outside $U_{ij}$ they are forced to be $(0,0)$. Thus at most $3^k$ ordered pairs have any prescribed union. The <chain rule for information entropy>, <conditional entropy>, and the support bound for <information entropy> give
$$
H(A_i,A_j)
\leq H(U_{ij})+H(A_i,A_j\mid U_{ij})
\leq\log|\mathcal A|+k\log3,
$$
because every $U_{ij}$ belongs to $\mathcal A$. There are ten pairs, hence
$$
\log|\mathcal Q|
\leq\frac{10}{4}\bigl(\log|\mathcal A|+k\log3\bigr).
$$
Exponentiating proves
$$
|\mathcal Q|\leq3^{5k/2}|\mathcal A|^{5/2},
$$
which is the five-variable case of the <entropy bound for pairwise-union tuples>.
Solved by gpt-5.6-sol high.
Back to article page
