Where does the golden-ratio constant in cross-intersecting families come from?

last_checkpoint·Oct 20, 2025(edited)

The constant

(3-\sqrt5)/2

seems too specific to come from a crude pigeonhole argument. Is there a construction whose two family sizes naturally balance there? Problem: Let

\alpha < \frac{3 - \sqrt{5}}{2}

be a positive real number. Prove that there exist positive integers

n

and

p > \alpha \cdot 2^{n}

for which one can select

2p

pairwise distinct subsets

S_{1}, \ldots, S_{p}, T_{1}, \ldots, T_{p}

of the set

\{1, 2, \ldots, n\}

such that

S_{i} \cap T_{j} \neq \varnothing

for all

1 \leq i, j \leq p

. Source: IMO 2007 Shortlist · MNET-06PH

Open MNET-06PH in the question bank →

6 replies

pixelated_toast·Oct 21, 2025(edited)

Partition [n] into k blocks of size m. Let S be the family meeting every block. Let T be the family containing an entire block but failing to meet at least one block. The families are disjoint, and every S-set meets every T-set.

last_checkpoint·Oct 21, 2025(edited)

I get

|\mathcal S|=(2^m-1)^k

. Counting T seems to need inclusion-exclusion over all k blocks.

pixelated_toast·Oct 21, 2025(edited)

Use complements twice. The number containing a whole block is

2^{km}-(2^m-1)^k

. The number both meeting every block and containing one whole block is

(2^m-1)^k-(2^m-2)^k

. Subtract them.

snorlax_afk·Oct 21, 2025(edited)

Hence

|\mathcal T|=2^{km}-2(2^m-1)^k+(2^m-2)^k

. Choose

k=\lfloor c2^m\rfloor

. The two densities tend to

e^{-c}

and

(1-e^{-c})^2

last_checkpoint·Oct 22, 2025(edited)

Balancing t with

(1-t)^2

gives

t=(3-\sqrt5)/2

. So choose

c=-\log t

pixelated_toast·Oct 22, 2025(edited)

Exactly. Both densities converge to t, so for any fixed α<t, sufficiently large m makes both exceed α. Taking p as the smaller family size gives the required 2p distinct sets.