Um problema legauss de combinatória

E aí galerinha do LeGauss.

Vou postar hoje um problema que eu achei muito legal, que foi retirado do livro Putnam and Beyond de Razvan Gelca e Titu Andreescu publicado pela Springer.
Na verdade o livro recomenda resolver esse problema usando contradição, mas achei que pensar em uma prova direta seria bem mais legal (e realmente foi).

Créditos também para o Tiago que ajudou muito nessa prova, na verdade a gente fez essa solução juntos, eu só estou postando por um acaso do destino.
Então vamos ao que interessa.


Seja uma família de subconjuntos com elementos de algum conjunto . Mostre que se a interseção de quaisquer (não necessariamente distintos) conjuntos em é não vazia, então a interseção de todos os conjuntos em é não vazia.

Alguns lemas que nos ajudarão (se duvidar da validade deles não hesite em tentar prová-los, não é difícil):

Lema 1:


Lema 2:


Primeiro, sem perda de generalidade, chamaremos de

Agora, fixado um subconjunto , calcularemos quantas escolhas de famílias distintas, contém .

Perceba que como cada escolha do tipo que estamos considerando já contém , precisamos então escolher somente mais subconjuntos dentre os restantes.

Ou seja, a quantidade de escolhas que contém é dada por:


Sejam as interseções (não vazias!) de cada uma das nossas escolhas.
Repare que, como possui apenas elementos, se existirem, pelo menos, escolhas distintas (e consequentemente interseções não vazias) existirá um elemento em, no mínimo, interseções diferentes. E isso terminará nossa prova.

Se você não achou o final do raciocínio muito claro, ele se chama o Princípio da Casa dos Pombos, você pode ler mais sobre ele aqui.

Precisamos provar então que:


Para isso utilizaremos o princípio da indução finita sobre .

Nossa base será (repare que não faz sentido).

Base da indução:

Hipótese de indução:

Passo de indução:

Precisamos mostrar que:

Note que:

pelo lema 1. Agora pela hipótese de indução:


Como para


Sabemos agora que


pelo lema 2.
Logo

Espero que tenham gostado! ;^)