Edit page

Princípio do Pombal

Primeira Forma do Princípio do Pombal

Se nn pombos voam para k<nk<n pombais, num dos kk pombais coabitam pelo menos dois pombos.

Demonstração

Por absurdo,

Suponha-se que em cada pombal habita apenas um pombo. Nesse caso não podem existir mais do que kk pombos, o que é impossível, pois existem n>kn>k pombos.

Provas Exemplo 1

Exemplo 1 - 2.2 da Série 4

Mostre que, se há mais livros numa biblioteca do que páginas em qualquer dos livros, então pelo menos dois livros têm igual número de páginas.


Imaginemos que os livros estão vazios, e temos de associar a cada livro um número de páginas, de acordo com as condições do enunciado.
Seja PP o conjunto dos vários números de páginas possíveis, ordenados de forma crescente.

P={p1,p2,,pk}P=\{p_1,p_2,\dots,p_k\}

Como pkp_k é menor que o número de livros (pelo enunciado) e pip_i toma apenas valores em N1\N_1,

#P<nuˊmero de livros\#P<\text{número de livros}

Pela Primeira Forma do Princípio de Pombal, ao associarmos cada pip_i com um livro vamos, obrigatoriamente, repetir o número de páginas para, pelo menos, 22 livros diferentes, ficando estes com o mesmo número de páginas.

QED

Exemplo 2 - Sucessão de números naturais dos Slides

Mostre que, se aia_i é uma sucessão de números naturais e nN2n \in \N_2, então para algum valor de kNk \in \N e para algum valor de mNm \in \N, a soma ak+ak+1+ak+2++ak+ma_k + a_{k+1} + a_{k+2} + \dots + a_{k+m} é divisível por nn.


Importante:

  • Sejam j1>j2j_1 > j_2 dois números tais que j1%n=j2%nj_1\%n = j_2\%n, então (j1j2)%n=0(j_1 - j_2)\%n = 0.
    (Também é válido para j1j2j_1\leq j_2, mas nesse caso j1j20j_1-j_2\leq0 e para este exercício dá jeito a solução positiva por causa dos números naturais)
  • Este exercício só faz sentido se considerarmos números naturais a partir de 11

Se escolhermos um certo termo da sucessão, aλa_{\lambda}, e considerarmos as seguintes (n+1)(n+1) somas:

s0=aλs1=aλ+aλ+1sn=aλ+aλ+1++aλ+ns_0 = a_{\lambda}\\ s_1 = a_{\lambda} + a_{\lambda+1}\\ \ldots\\ s_n = a_{\lambda} + a_{\lambda+1} + \dots + a_{\lambda+n}

Como os termos da sucessão pertencem todos a N1\N_1, para j>ij>i tem-se sj>sis_j > s_i, logo de s0s_0 a sns_n teremos n+1n+1 valores diferentes.
Se fizermos o resto da divisão inteira por nn para todos os valores da soma, como esse resto tem de pertencer a {0,,n1}\{0,\dots,n-1\} (nn valores possíveis) e temos n+1n+1 somas diferentes, pela Primeira Forma do Princípio de Pombal, haverá pelo menos duas somas com o mesmo resto.

Se têm o mesmo resto, pela Nota Importante do início da prova, a sua diferença será divisível por nn.

Por fim, como as somas consideradas são de termos consecutivos a começar sempre pelo mesmo, a diferença entre quaisquer duas será também uma soma consecutiva de termos.

sjsi=ai+1+λ+ai+2+λ++aj+λ,j>is_j - s_i = a_{i+1+\lambda}+a_{i+2+\lambda}+\dots+a_{j+\lambda}, \quad j>i

QED

Nota

  • O λ\lambda é usado para mostrar que se pode começar em qualquer termo da sucessão, se fizer confusão tomem λ=0\lambda=0, como está nos slides.
  • Na última conclusão, podemos também pensar que sis_i é uma "subsoma" de sjs_j (i<j)(i < j), por isso, quando fazemos sjsis_j-s_i estamos a retirar a sjs_j os termos em comum com sis_i.

Segunda Forma do Princípio do Pombal

Se f é uma aplicação de assinatura f:XY\operatorname{f} : X \rightarrow Y , com XX e YY conjuntos finitos tais que #X>#Y\#X > \#Y , então existem x1,x2Xx_1, x_2 \in X tais que x1x2x_1 \neq x_2 e f(x1)=f(x2)\operatorname{f}(x_1) = \operatorname{f}(x_2).

Demonstração

Seja XX o conjunto de pombos e YY o conjunto de pombais. Atribuímos cada pombo xXx \in X a um pombal f(x)Y\operatorname{f}(x) \in Y. Pela Primeira Forma do Princípio de Pombal, pelo menos dois pombos x1,x2Xx_1, x_2 \in X coabitam no mesmo pombal, i.e. existem x1,x2Xx_1, x_2 \in X tais que x1x2x_1 \neq x_2 e f(x1)=f(x2)\operatorname{f}(x_1) = \operatorname{f}(x_2).

Provas Exemplo 2

Exemplo 1 - Alunos de EMD dos Slides

Prove que se selecionar 151 alunos de EMD de números compreendidos entre ist199001ist199001 e ist199300ist199300, inclusive, pelo menos dois alunos têm números consecutivos.


Suponhamos que os 151 alunos têm números n1,n2,,n151n_1, n_2, \dots, n_{151}, todos diferentes entre si. Por agora não interessa se são consecutivos ou não, o que interessa é que são diferentes.

Agora consideramos os 151 números consecutivos a cada número dos alunos, ou seja, n1+1,n2+1,,n151+1n_1+1, n_2+1,\dots ,n_{151}+1. Estes também todos diferentes entre si.

Os 302302 (151+151)(151+151) números estão compreendidos entre ist199001ist199001 e ist199301ist199301 (301301 números), pois se um aluno tiver ni=n_i= ist199300, o seu número consecutivo será ist199301 (ni+1)(n_i+1).

Pela Segunda Forma do Princípio de Pombal, seja

f:{n1,n1+1,,n151,n151+1}{ist199001,,ist199301}f:XY\operatorname{f} : \{n_1,n_1+1,\dots,n_{151},n_{151}+1\} \rightarrow \{ist199001,\dots,ist199301\}\\ \operatorname{f} : X \rightarrow Y

Como #X>#Y\#X>\#Y, existirão 22 números de aluno iguais no conjunto {n1,n1+1,,n151,n151+1}\{n_1,n_1+1,\dots,n_{151},n_{151}+1\}.
Como dois alunos não podem ter o mesmo número (ninj)(n_i \neq n_j) e portanto também é verdade que ni+1nj+1n_i+1 \neq n_j+1, tem de haver pelo menos um caso onde nj=ni+1n_j = n_i+1, ou seja njn_j é o número a seguir a nin_i.
Conclui-se que pelo menos dois alunos têm números consecutivos.

QED

Terceira Forma do Princípio do Pombal

Se f\operatorname{f} é uma aplicação de assinatura f:XY\operatorname{f} : X \rightarrow Y tal que #X=n\#X = n e #Y=m<n\#Y = m < n, então existem pelo menos k=nmk = \lceil\frac{n}{m}\rceil valores a1,a2,,aka_1, a_2, \dots, a_k de XX tais que f(a1)=f(a2)==f(ak)\operatorname{f} (a_1) = \operatorname{f} (a_2) = \dots = \operatorname{f} (a_k).

Exemplo Ilustrativo

Seja #X=5\#X = 5 e #Y=2\#Y = 2, pela Terceira Forma do Princípio de Pombal existem pelo menos 52=3\lceil\frac{5}{2}\rceil=3 valores a1,a2,a3a_1, a_2, a_3 de XX tais que f(a1)=f(a2)=f(a3)\operatorname{f} (a_1) = \operatorname{f} (a_2) = \operatorname{f} (a_3).

Pombal 3

Nota

k=abk = \lceil\frac{a}{b}\rceil significa que kk é a divisão de aa por bb arredondada por excesso.
Exemplos

13=0.33..=1205=4=4\lceil\frac{1}{3}\rceil =\lceil0.33..\rceil=1\\ \lceil\frac{20}{5}\rceil =\lceil4\rceil=4

Provas Exemplo 3

Exemplo 1 - T-SHIRTS dos Slides

Um cesto contém 2020 T-SHIRTS de várias cores: 44 brancas, 77 verdes e 99 azuis. Qual é o menor número de T-SHIRTS a retirar aleatoriamente do cesto de modo a obter (a) 44 e (b) 55 T-SHIRTS da mesma cor.


Seja X={t1,,t20}X= \{t_1,\dots,t_{20}\} o conjunto de T-SHIRTS e Y={c1,c2,c3}Y=\{c_1,c_2,c_3\} o conjunto de cores.

(a)-4

Como cada cor está associada a pelo menos 44 T-SHIRTS (pelo enunciado), podemos aplicar diretamente a Terceira Forma do Princípio de Pombal.
Sendo kk o número mínimo de T_SHIRTS a retirar, como existem 33 cores possíveis e queremos pelo menos 44 T-SHIRTS de cores iguais, pela Terceira Forma do Princípio de Pombal 4=k34 = \lceil\frac{k}{3}\rceil, ou seja, k=10k=10.
(Para k=11k=11 e k=12k=12 a equação também era válida, mas queremos o menor kk possível)

(b)-5

Neste caso não podemos aplicar diretamente a Terceira Forma do Princípio de Pombal, pois o número de T-SHIRTS brancas é 44, o que significa que é impossível retirar 55 T-SHIRTS brancas do cesto.
Para ter a certeza que retiramos 55 T-SHIRTS iguais do cesto é necessário retirar todas as 44 T-SHIRTS brancas.

Depois de retiradas as 44 brancas já se pode aplicar diretamente a Terceira Forma do Princípio de Pombal.
Das 1616 restantes queremos retirar o mínimo de T-SHIRTS kk tal que pelo menos 55 têm a mesma cor. Como só existem 2 cores no cesto 5=k25 = \lceil\frac{k}{2}\rceil, k=9k=9.
(ATENÇÃO: kk tem de ser menor que o número de T-SHIRTS do cesto, neste caso 1616. Se o resultado for maior ou houve um erro de contas/raciocínio ou o exercício é impossível).

Resposta será k+4=13k+4=13

Para quem ainda não percebeu a razão pela qual tiramos as 44 T-SHIRTS brancas:
Tentem pensar em casos onde se consegue retirar no máximo 55 T-SHIRTS iguais, sem retirar as 44 brancas.
Por exemplo, retirar logo 55 azuis/verdes ou 55 azuis/verdes, 44 verdes/azuis e 33 brancas (total 1212). Em todos esses casos conseguimos pensar em outros onde retiramos o mesmo número de T-SHIRTS sem conseguir retirar as 55 iguais.
Para termos a certeza que em λ\lambda T-SHIRTS temos 55 iguais significa que quando temos λ1\lambda-1 T-SHIRTS a próxima será a 55ª igual para uma dada cor. Sem retirar todas as 44 brancas, a λ\lambda-ésima T-SHIRT pode ser uma branca, que nunca será a 55ª igual.

AVISO: Existem mais alíneas nos slides para quem tiver curiosidade.

Recomendação

Para ficar à vontade com o Princípio do Pombal é necessário fazer várias provas sozinho. Apesar de percebermos algumas provas dos Slides e termos mais ou menos a ideia de como se fazem, sem a prática, a probabilidade de ficar preso em exercícios novos/diferentes continua elevada.