Princípio do Pombal

Por absurdo,

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

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 $P$ o conjunto dos vários números de páginas possíveis, ordenados de forma crescente.

Como $p_k$ é menor que o número de livros (pelo enunciado) e $p_i$ toma apenas valores em $\N_1$,

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

QED

Mostre que, se $a_i$ é uma sucessão de números naturais e $n \in \N_2$, então para algum valor de $k \in \N$ e para algum valor de $m \in \N$, a soma $a_k + a_{k+1} + a_{k+2} + \dots + a_{k+m}$ é divisível por $n$.

Importante:

• Sejam $j_1 > j_2$ dois números tais que $j_1\%n = j_2\%n$, então $(j_1 - j_2)\%n = 0$.
  (Também é válido para $j_1\leq j_2$, mas nesse caso $j_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 $1$

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

Como os termos da sucessão pertencem todos a $\N_1$, para $j>i$ tem-se $s_j > s_i$, logo de $s_0$ a $s_n$ teremos $n+1$ valores diferentes.
Se fizermos o resto da divisão inteira por $n$ para todos os valores da soma, como esse resto tem de pertencer a $\{0,\dots,n-1\}$ ($n$ valores possíveis) e temos $n+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 $n$.

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.

QED

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

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

Suponhamos que os 151 alunos têm números $n_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, $n_1+1, n_2+1,\dots ,n_{151}+1$. Estes também todos diferentes entre si.

Os $302$ $(151+151)$ números estão compreendidos entre $ist199001$ e $ist199301$ ($301$ números), pois se um aluno tiver $n_i=$ ist199300, o seu número consecutivo será ist199301 $(n_i+1)$.

Pela Segunda Forma do Princípio de Pombal, seja

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

QED

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

Um cesto contém $20$ T-SHIRTS de várias cores: $4$ brancas, $7$ verdes e $9$ azuis. Qual é o menor número de T-SHIRTS a retirar aleatoriamente do cesto de modo a obter (a) $4$ e (b) $5$ T-SHIRTS da mesma cor.

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

(a)-4

Como cada cor está associada a pelo menos $4$ T-SHIRTS (pelo enunciado), podemos aplicar diretamente a Terceira Forma do Princípio de Pombal.
Sendo $k$ o número mínimo de T_SHIRTS a retirar, como existem $3$ cores possíveis e queremos pelo menos $4$ T-SHIRTS de cores iguais, pela Terceira Forma do Princípio de Pombal $4 = \lceil\frac{k}{3}\rceil$, ou seja, $k=10$.
(Para $k=11$ e $k=12$ a equação também era válida, mas queremos o menor $k$ 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 é $4$, o que significa que é impossível retirar $5$ T-SHIRTS brancas do cesto.
Para ter a certeza que retiramos $5$ T-SHIRTS iguais do cesto é necessário retirar todas as $4$ T-SHIRTS brancas.

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

Resposta será $k+4=13$

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

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