Princ�pio de Dirichlet

["Bruno Furlan" <brunobfurlan@xxxxxxxxx>]

O Princ�pio das Gavetas de Dirichlet (Peter Dirichlet, alem�o, 1805-1859),
tamb�m chamado de Princ�pio da Casa dos Pombos, diz:

1. "Suponha que n objetos s�o colocados em k caixas. Se n>k, pelo menos uma
caixa conter� pelo menos 2 objetos. Generalizando, se n>km, pelo menos uma
caixa conter� pelo menos m+1 objetos, pois se toda caixa contivesse no
m�ximo m objetos, haveria n�o mais de km objetos no total."

2. "Se n objetos ocupam k caixas, ent�o pelo menos uma caixa cont�m
|_n-1/k_| +1 objetos."

(obs.: |_x_| representa "piso de x", ou seja, maior inteiro menor ou igual a
x)