Escolhem-se ao acaso dois quaisquer dos nove pontos acima

Se \(k+1\) pombos forem colocados em \(k\) casas, então existe pelo menos uma casa contendo dois ou mais pombos.

Mostre que, em um grupo de 367 pessoas, pelo menos duas fazem o aniversário no mesmo dia.

Chame de \(\mathcal{P}\) o conjunto das pessoas e \(\mathcal{C}\) o conjunto dos dias do ano. Desta forma como temos mais elementos em \(\mathcal{P}\) do que em \(\mathcal{C}\text{,}\) pelo princípio da casa dos pombos, pelo menos duas pessoas fazem aniversário no mesmo dia.

Mostre que entre nove números que não possuem divisores primos maiores que cinco, existem dois cujo produto é um quadrado.

Inicialmente observe que, qualquer número inteiro que não possui divisor primo maior que cinco, se escreve na forma \(2^a3^b5^c\text{,}\) com \(a, b\) e \(c \in \mathbb{N}\text{.}\)

Defina um conjunto com 9 números arbitrários, que satisfaça as hipóteses do enunciado:

\begin{equation*} \mathcal{P} = \{ 2^{a_1}3^{b_1}5^{c_1}, 2^{a_2}3^{b_2}5^{c_2}, \ldots, 2^{a_9}3^{b_9}5^{c_9} \}. \end{equation*}

Como os expoentes \(a_i, b_i\) e \(c_i\) só podem ser pares ou ímpares, seja \(\mathcal{C}\) um conjunto que represente todas as paridades possíveis para os expoentes de 2, 3 e 5 em \(2^a3^b5^c\text{.}\) Este conjunto possui 8 elementos, pois temos duas possibilidades para a paridade de cada um dos 3 expoentes.

Como o conjunto \(\mathcal{P}\) é formado por nove elementos, pelo princípio da casa dos pombos, teremos dois elementos em \(\mathcal{P}\text{,}\) cujos expoentes possuem a mesma paridade, digamos que \(2^{a_i}3^{b_i}5^{c_i}\) e \(2^{a_j}3^{b_j}5^{c_j}\text{.}\)

O produto entre eles é da forma \(2^{a_i+a_j}3^{b_i+b_j}5^{c_i+c_j}=2^{2x}3^{2y}5^{2z}\text{,}\) com \(x, y, z \in \mathbb{N}\text{,}\) que é um quadrado, pois pode ser escrito na forma

\begin{equation*} (2^{x}3^{y}5^{z})^2\text{.} \end{equation*}

Prove que, de qualquer conjunto de dez números naturais distintos de dois dígitos, podemos escolher dois subconjuntos A e B (disjuntos) cuja a soma dos elementos é a mesma em ambos.

Seja \(S\) um conjunto com 10 números naturais distintos de dois dígitos. A soma de todos os elementos de \(S\) pode ser no máximo 945, no caso em que \(S=\{90, 91, \ldots, 99\}\text{.}\)

Considere o conjunto das partes de \(S\text{,}\) ou seja, o conjunto formado por todos os subconjuntos de \(S\text{.}\) Este conjunto possui \(2^{10}\) elementos, sendo um deles o conjunto vazio, pois para formar um subconjunto de \(S\text{,}\) precisamos decidir se cada elemento de \(S\) vai pertencer ou não a este subconjunto.

Defina \(\mathcal{C} = \{ 1, 2, \ldots, 945 \}\) e \(\mathcal{P}\) como o conjunto das partes de \(S\text{,}\) menos o conjunto vazio. Desta forma \(\mathcal{P}\) possui \(2^{10}-1 = 1023\) elementos.

Observe que um elemento de \(\mathcal{P}\) é um subconjunto de \(S\) e que a soma dos elementos de um elemento de \(\mathcal{P}\) será um número que pertence a \(\mathcal{C}\text{.}\) Pelo princípio da casa dos pombos, como temos mais elementos em \(\mathcal{P}\) do que em \(\mathcal{C}\text{,}\) pelo menos dois elementos \(A, B \in \mathcal{P}\) possuem a mesma soma.

Se \(A\) e \(B\) forem disjuntos, acabou. Se não, considere \(A' = A- A\cap B\) e \(B' = B - A \cap B\text{.}\) Logo, os conjuntos \(A'\) e \(B'\) são disjuntos e a soma dos seus elementos é a mesma.

\begin{equation*} \left\lceil \frac{1}{2} \right\rceil = 1, \lceil 3.1 \rceil = 4, \left\lceil -\frac{1}{2} \right\rceil=0. \end{equation*}

Se \(n\) pombos forem colocados em \(k\) casas, então existe pelo menos uma casa contendo pelo menos

\begin{equation*} \left\lceil \frac{n}{k} \right\rceil \end{equation*}

pombos.

Suponha que nenhuma das caixas contém mais que \(\left\lceil \frac{n}{k} \right\rceil-1\) pombos. Então, o número total de pombos é no máximo

\begin{equation*} k\left(\left\lceil \frac{n}{k} \right\rceil-1\right) \lt k\left( \left( \frac{n}{k} +1 \right) -1 \right) = n, \end{equation*}

na qual a desigualdade \(\left\lceil \frac{n}{k} \right\rceil \lt \frac{n}{k} +1 \) foi usada. Esta é uma contradição, pois existem um total de \(n\) pombos.

Nove pontos são colocados no interior de um triângulo de área 4\(cm^2\text{,}\) de forma que não tenha 3 pontos colineares. Mostre que podemos escolher três deles para serem os vértices de um triângulo de área no máximo igual a 1\(cm^2\text{.}\)

Sejam \(A, B\) e \(C\) os vértices do triângulo de área 4\(cm^2\text{.}\) Considere três pontos \(D_1, D_2\) e \(D_3\) na arestas \(BC\text{,}\) de forma que \(ABD_1, AD_1D_2, AD_2D_3\) e \(AD_3C\) formem quatro triângulos, cada um com área de 1\(cm^2\text{.}\)

Desta forma ao colocar os pontos no triâgulo \(ABC\text{,}\) pelo princípio da casa dos pombos, existem pelo menos \(\lceil 9/4 \rceil = 3\) pontos em um dos quatro triângulos: \(ABD_1, AD_1D_2, AD_2D_3\) e \(AD_3C\text{.}\)

Logo os três pontos que estão dentro de um destes 4 triângulos, por não serem colineares, formam um triângulo de área no máximo igual a 1\(cm^2\text{.}\)

Assuma que em um grupo de 6 pessoas, cada par de pessoas consistem em dois amigos ou dois inimigos. Mostre que ou existem 3 amigos mútuos ou 3 inimigos mútuos.

Seja \(A\) uma das 6 pessoas. Sejam \(\mathcal{C}=\{\{\mbox{amigo de }A\}, \{\mbox{inimigo de }A\}\}\) e \(\mathcal{P} = \{B, C, D, E, F\}\) o conjunto com as outras 5 pessoas.

Pela 2ª versão do princípio da casa dos pombos, dividindo as 5 pessoas de \(\mathcal{P}\) nos 2 conjuntos de \(\mathcal{C}\text{,}\) um desses conjuntos possui pelo menos \(\lceil 5/2 \rceil = 3\) elementos. Então, ou existem 3 ou mais que são amigos de \(A\text{,}\) ou 3 ou mais que são inimigos de \(A\text{.}\)

Suponha sem perda de generalidade que \(B, C\) e \(D\) sejam amigos de \(A\text{.}\) Se quaisquer duas destas 3 pessoas são amigas, então estas duas pessoas e \(A\) formam um conjunto de 3 amigos mútuos.

Qual é o número mínimo de pessoas que deve haver em um grupo para que possamos garantir que nele haja pelo menos 5 pessoas nascidas no mesmo mês?

A comissão organizadora de um congresso dividiu os 75 professores presentes em 8 grupos, de acordo com a disciplina ministrada pelo professor. Sabendo que cada um deles ministra uma única disciplina, mostre que haverá pelo menos um grupo com no mı́nimo 10 professores.

Escolhem-se ao acaso 5 pontos sobre a superfície de um quadrado de lado 2. Mostre que pelo menos um dos segmentos que eles determinam tem comprimento menor ou igual a \(\sqrt{2}\text{.}\)

Prove que todo número natural tem um múltiplo que se escreve, na base 10, apenas com os algarismos 0 e 1.

Prove que em qualquer conjunto de 52 inteiros existe um par de inteiros cuja soma ou cuja diferença é divisível por 100.