Em física e matemática, é bem comum encontrarmos princípios que parecem óbvios com consequências complicadas. Meu exemplo favorito é a relação conhecida como equação mestra na física estatística que, se lida em português, seria: “o quanto variou é o quanto entrou menos o quanto saiu”. Por mais evidente que isso seja, essa equação toma formas cabulosas em situações não muito complicadas e exige bastante suor para ser resolvida.

Mas o assunto de hoje não é a equação mestra, mas outro princípio, talvez ainda mais simples: o princípio da casa dos pombos, ou princípio do pombal.

Princípio da casa dos pombos: se há mais pombos que casas em um pombal, alguma casa terá mais de um pombo.

Eis uma aplicação desse princípio:

E por mais óbvio que ele pareça, não é nada inútil se lembrar dele como técnica de demonstração de resultados bem interessantes. Um deles, meu favorito, é uma espécie de jogo com sequências. Para ilustrar, imagine uma rua com $n$ casas. Cada casa deve possuir um número, e você pode escolher o número que quiser. Eu afirmo que existe um grupo de casas vizinhas cujos números, somados, resultam em um múltiplo de $n$.

Vejamos um exemplo. Imagine treze casas que possuem os seguintes números: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 e 14. Se houvesse uma casa com o número 13, ela seria sozinha o múltiplo de 13 que quero, isso não me serve de muita coisa. Note que, nessa rua, temos os vizinhos 5, 6, 7 e 8, e 5+6+7+8=26, que é um múltiplo de 13.

Mas podemos pegar sequências mais complicadas, como, por exemplo, um antigo telefone meu: 41921561. Eu tenho certeza absoluta de que existem números vizinhos que, somados, resultam em um múltiplo de oito (que é o tamanho da sequência). Basta caçar um pouco para encontrar que 4+1+9+2=16.

Ou, ainda, tomemos essa permutação de meu RG: 158313734. Cacemos os vizinhos que somados dão um múltiplo de nove, e uma leve busca nos leva a 5+8+3+1+3+7=27. Você certamente pode encontrar combinações mais simples, eu não disse que era única, apenas que existe.

Esse resultado, que é um divertido jogo quando se está profundamente entediado em uma sala de espera ou durante uma viagem de trem, é provado com o princípio do pombal. Para tal, tome sua sequência de tamanho $n$, da forma $a_1,a_2,\ldots a_n$. Pense agora em todas as possíveis sequências com a mesma ordem dessa sua original que começam no $a_1$, ou seja, as sequências:

\[a_1\]

\[a_1,a_2\]

\[a_1,a_2,a_3\]

E assim por diante. Pense agora na soma dos elementos delas. Se alguma dessas somas já dá um múltiplo de $n$, nosso problema está resolvido, então vamos supor o pior dos casos, nenhuma delas é um múltiplo de $n$. Assim, a soma dessas sequências, dividida por $n$, deve dar algum resto, e haverá $n-1$ possibilidades de resto.

Ainda em um exemplo, se minha sequência possuísse quatro elementos, as somas dessas subsequências teriam que ter resto ou 1, ou 2, ou 3. Se o resto fosse zero, seria divisível.

Como você tem $n$ sequências possíveis e apenas $n-1$ restos possíveis, então, pelo princípio do pombal, terá, necessariamente, duas sequências diferentes cuja soma tem o mesmo resto na divisão por $n$. Ora, subtraia uma da outra que você terá uma sequência de vizinhos cuja soma, dividida por $n$, possui resto zero, logo, é divisível!

Para entender melhor, vou aplicar esse raciocínio a uma sequência específica: 1 2 1 3 6. As subsequências possíveis são 1, 1 2, 1 2 1, 1 2 1 3 e 1 2 1 3 6. Suas somas serão, respectivamente, 1, 3, 4, 7 e 13. Note que, dividindo por 5, esses números produzem respectivamente resto 1, 3, 4, 2 e 3. A segunda e a última sequência possuem o mesmo resto! Então tirando a segunda da última teremos os elementos 1 3 6 que, somados, dão 10, um múltiplo de 5.

Não sei se ficou claro, na verdade, acho que ficou confuso, mas vou deixar assim enquanto não encontro maneira melhor de escrever. Provar o princípio do pombal, no entanto, me parece mais difícil que esse resultado que acabei de enunciar, talvez usando algum resultado dessa parte mais fundamental de teoria dos conjuntos, propriedades com bijeções, injeções e sobrejeções, a noção de cardinalidade, teria que pensar um pouco. Por enquanto, fica o resultado das sequências, das casas, e a demonstração dos pombos.