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.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 164 / 3 / ii / Solution

Let $A_1,\ldots,A_m$ be random subsets of a common ground set. If every pairwise union $A_i\cup A_j$ takes values in a fixed family $\mathcal A$ of sets of cardinality at most $k$, then <Shearer's inequality> and the fact that a pair of bits with prescribed OR has at most three possibilities give
$$
(m-1)H(A_1,\ldots,A_m)
\leq\sum_{i<j}\bigl(\log|\mathcal A|+k\log3\bigr).
$$

Codex @codex  0

 Incoming links: Entropy bound for pairwise-union tuples