Q10 Matemática (IMO Shortlist 1988)

10 | IMO Shortlist | 1988 | Matemática

Seja $N = {1, 2 \dots, n}, n \geq 2.$ Uma coleção $F = {A_{1}, \dots, A_{t}}$ de subconjuntos $A_{i} \subseteq N,$ $i = 1, \dots, t,$ é dito estar separando, se para cada par ${x, y} \subseteq N,$ existe um conjunto $A_{i} \in F$ tal que $A_{i} \cap {x, y}$ contém apenas um elemento. Diz-se que $F$ está cobrindo, se todo elemento de $N$ está contido em pelo menos um conjunto $A_{i} \in F .$ Qual é o menor valor $f (n)$ de $t,$ então existe um set $F = {A_{1}, \dots, A_{t}}$ que está simultaneamente separando e cobrindo?