Se em todo par de elementos ao menos um tem a propriedade P, qual o máximo de elementos que podem não ter P?

No máximo 1.

Seja n o número de elementos sem a propriedade P.
Se n ≥ 2, podemos escolher dois desses elementos sem P, obtendo um par em que nenhum tem P, o que contraria a hipótese.
Logo, n ≤ 1, portanto o máximo é 1.

Exemplo:
Temos 10 lâmpadas; cada uma é funcional ou queimada. Se ao escolher quaisquer duas lâmpadas pelo menos uma é funcional, então o número de lâmpadas queimadas, \(b\), deve obedecer:
\(b\ge2\) ⇒ existem duas queimadas ⇒ contradição. Portanto \(b\le1\).
Com 10 lâmpadas, o máximo de queimadas é 1 (ou seja, pelo menos 9 são funcionais).