Ir ao conteúdo principal

Combinatória: notas de aula (PTOM/POTI)

Ricardo Machado

Seção 2.1 O Pincípio da Casa dos Pombos I

Subseção 2.1.1 Introdução

O princípio da casa dos pombos também é conhecido em alguns países (na Rússia, por exemplo) como Princípio de Dirichlet pois, foi o matemático Lejeune Dirichlet o primeiro matemático a usar este método para resolver problemas não triviais. Outros matemáticos que se destacaram por usarem essa ideia para resolver diversos problemas foram os húngaros Erdős e Szekeres.
Vamos abordar este princípio da seguinte maneira:
"Se em \(n\) caixas são postos \(n+1\) pombos, então pelo menos uma caixa terá mais de um pombo."
Alguns Exemplos:
  • Em um grupo de 13 pessoas, pelo menos duas delas têm o mesmo signo.
  • Em um grupo de 5 cartas de baralho, pelo menos duas são do mesmo naipe.
  • Na cidade de Recife, existem pelo menos duas pessoas com o mesmo número de fios de cabelo.
Agora vamos ver como algo tão simples pode resolver problemas aparentemente difíceis:

Exemplo 2.1.1.

Escolhem-se 5 pontos ao acaso sobre a superfície de um quadrado de lado 2. Mostre que pelo menos dois deste pontos estão em um distância menor que ou igual a \(\sqrt{2}\text{.}\)
Solução.
Divida o quadrado em quatro quadrados menores como na figura ao lado. Como temos cinco pontos e quatro quadrados, teremos pelo menos dois pontos no mesmo quadradinho. Como a maior distância entre dois pontos do mesmo quadradinho não supera a medida de sua diagonal, o resultado segue de imediato.

Subseção 2.1.2 Passo de Mágica?

Para o aluno iniciante a solução do problema anterior pode ter parecido um pouco mágica. Vamos mostrar que não é bem assim, que existe um método na solução de alguns problemas simples que usam a ideia da casa dos pombos.
A primeira coisa que devemos aprender a reconhecer é quando um problema se trata de um problema sobre casa dos pombos. Isso pode ser ganho com experiência, mas vamos dar um empurrãozinho para você. Um problema de PCP tem quase sempre a seguinte cara:
  • Dado um conjunto de \(n\) objetos, prove que podemos escolher \(k\) deles satisfazendo uma propriedade.
Bem, depois de identificar que o enunciado do problema nos traz a ideia de usar PCP, devemos nos concentrar em responder as seguintes perguntas:
  1. Quem são os pombos?
  2. Quantas são as casas?
  3. Quem são as casas?
Quase sempre as duas primeiras perguntas são as mais fáceis de serem respondidas. Para responder a terceira pergunta devemos pensar no conceito dual de espaço amostral. Por um lado, o espaço amostral é o conjunto das possíveis posições dos pombos. Por outro, é a união de todas as casas.
Para finalizar, devemos separar o espaço amostral no número de casas já descoberto. Nessa hora é importante lembrar que as casas devem refletir a propriedade desejada. Como acabamos de ver, usar o princípio da casa dos pombos não é difícil. O difícil está em achar o que serão nossos "pombos" e "caixas".

Subseção 2.1.3 Exemplos Resolvidos

Exemplo 2.1.2.

Prove que dados sete inteiros positivos, existem dois cuja soma ou a diferença é um múltiplo de 10.
Solução.
Vamos montar seis caixas \(C_0, C_1, \dots, C_5\) onde um inteiro está na caixa \(C_i\) se é congruente a \(i\) ou \(-i\) módulo 10. Sabemos que existirão dois inteiros na mesma caixa. Dessa forma, se eles forem incongruentes módulo 10, basta somá-los. Caso contrário, faça a sua diferença.

Exemplo 2.1.3.

Dados 5 pontos no plano com coordenadas inteiras, prove que pelo menos um dos dez pontos médio gerados por eles também possui coordenadas inteiras.
Solução.
Podemos separar os pontos de coordenadas inteiras (que é representado por \(\mathbb{Z}\times\mathbb{Z}\)) em quatro grupos \(G_1, G_2, G_3, G_4\) como a seguir:
  • \(G_1 = \{(x,y) \in \mathbb{Z}\times\mathbb{Z} \mid x, y\) são ambos pares\(\}\text{.}\)
  • \(G_2 = \{(x,y) \in \mathbb{Z}\times\mathbb{Z} \mid x, y\) são ambos ímpares\(\}\text{.}\)
  • \(G_3 = \{(x,y) \in \mathbb{Z}\times\mathbb{Z} \mid x\) é par e \(y\) é ímpar\(\}\text{.}\)
  • \(G_4 = \{(x,y) \in \mathbb{Z}\times\mathbb{Z} \mid x\) é ímpar e \(y\) é par\(\}\text{.}\)
Observe que pontos que pertencem ao mesmo grupo possuem pontos médios com coordenadas inteiras. Como temos 5 pontos, o princípio da casa dos pombos nos garante que há pelo menos dois pontos no mesmo grupo.

Exemplo 2.1.4.

Mostre que entre nove números que não possuem divisores primos maiores que cinco, existem dois cujo produto é um quadrado.
Solução.
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\) inteiros não negativos.
Defina um conjunto com 9 números arbitrários que satisfaçam 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*}

Exemplo 2.1.5.

(IMO 1972) 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.
Solução.
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.

Exemplo 2.1.6.

Nove pontos são postos sobre a superfície de um tetraedro regular com 1cm de aresta. Prove que dentre esses pontos é possível achar dois com distância (espacial) não maior que 0.5cm.
Solução.
Vamos particionar a superfície do tetraedro em 16 triângulos equiláteros congruentes, dividindo cada face em quatro partes usando suas bases médias. Agora vamos criar 8 regiões pintando esses triângulos de acordo com a seguinte regra: os triângulos que possuem um mesmo vértice do tetraedro serão pintados da mesma cor; dessa forma já usamos quatro cores diferentes para 12 triângulos e os outros quatro vamos pintar usando as demais cores.
De acordo com o Princípio da Casa dos Pombos, pelo menos dois dos nove pontos estarão na mesma região. Fica apenas faltando constatar que a distância máxima entre dois pontos da mesma região é no máximo 0.5cm.

Subseção 2.1.4 Outra Versão do Princípio da Casa dos Pombos

Para uma versão mais geral do princípio da casa dos pombos, vamos usar a função teto, dada por:
\begin{equation*} \lceil \rceil : \mathbb{R} \rightarrow \mathbb{Z} \end{equation*}
\begin{equation*} \lceil x \rceil = \min\{z \in \mathbb{Z} \mid z \ge x\} \end{equation*}
Ou seja, é o menor inteiro que é maior ou igual a \(x\text{.}\) Observe que \(\lceil x \rceil < x+1\) para qualquer \(x \in \mathbb{R}\text{.}\)
\(\lceil \frac{1}{2} \rceil = 1\text{,}\) \(\lceil 3.1 \rceil = 4\text{,}\) \(\lceil -\frac{1}{2} \rceil = 0\text{.}\)

Exemplo 2.1.8.

Nove pontos são colocados no interior de um triângulo de área \(4\text{cm}^2\) 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\text{cm}^2\text{.}\)
Solução.
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{.}\)
Figura 2.1.9. Triângulo subdividido.
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{.}\)

Exercícios 2.1.5 Problemas

1.

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?
Resposta.
49
Solução.
Pelo PCP basta encontrar o menor número inteiro \(n\text{,}\) tal que
\begin{equation*} \left\lceil \frac{n}{12}\right\rceil> 4\text{.} \end{equation*}
Como \(4\times 12=48\text{,}\) o valor de \(n\) é 5.

2.

Cinquenta e um pontos são postos no interior de um quadrado de lado 1 metro. Prove que existe um conjunto de três desses pontos que podem ser cobertos por um quadrado de lado 20 centímetros.
Solução.
Particione o quadrado de \(100\text{cm}^2\) em 25 quadrados menores de \(20\text{cm}^2\text{.}\) Como \(\lceil \frac{51}{25} \rceil = 3\) (pois \(51 = 25\cdot 2 +1\)) pelo PCP, pelo menos 1 quadrado de \(20\text{cm}^2\) contém 3 pontos.

3.

Em cada casa de um tabuleiro \(3\times 3\) é colocado um dos números \(-1, 0, 1\text{.}\) Prove que, dentre as oito somas ao longo de uma mesma linha, coluna ou diagonal, existem duas iguais.
Solução.
O valor máximo possível para uma soma é 3 (se houver três números 1) e o mínimo possível é -3. No total, as somas possíveis pertencem ao conjunto \(\{-3, -2, -1, 0, 1, 2, 3\}\text{,}\) ou seja, são 7 valores possíveis. Como no total são 8 somas (3 linhas + 3 colunas + 2 diagonais), pelo Princípio da Casa dos Pombos, pelo menos duas somas são iguais.

4.

Prove que de qualquer conjunto de dez inteiros podemos escolher um subconjunto cuja soma é um múltiplo de 10.
Solução.
Seja \(A = \{a_1, a_2, \dots, a_{10}\}\) um conjunto com 10 inteiros. Defina as somas parciais:
\begin{align*} S_1 \amp= a_1\\ S_2 \amp= a_1 + a_2\\ \vdots\\ S_{10} \amp= a_1 + a_2 + \dots + a_{10} \end{align*}
Se algum \(S_i \equiv 0 \pmod{10}\) (Ou o resto da divisão dealgum \(S_i\) por 10 for igual a zero), o problema acabou.
Caso contrário, os restos dessas 10 somas na divisão por 10 estão entre 1 e 9. Como são 10 somas e 9 restos possíveis, pelo PCP, pelo menos duas somas deixam o mesmo resto, ou seja, \(S_i \equiv S_j \pmod{10}\) com \(i > j\text{.}\) Subtraindo, temos \(S_i - S_j = a_{j+1} + \dots + a_i \equiv 0 \pmod{10}\text{.}\)

5.

Prove que existe uma potência de 3 terminada nos dígitos 001 (na base decimal).
Solução.
Considere as 1001 potências de 3:
\begin{equation*} 3^1, 3^2, \dots, 3^{1001}\text{.} \end{equation*}
Existem 1000 restos possíveis na divisão por 1000 (de 0 a 999). Pelo PCP, existem duas potências com o mesmo resto, ou seja, \(3^i \equiv 3^j \pmod{1000}\) com \(i > j\text{.}\)
Portanto, \(3^i - 3^j \equiv 0 \pmod{1000}\text{,}\) o que implica
\begin{equation*} 3^j(3^{i-j} - 1) \equiv 0 \pmod{1000}\text{.} \end{equation*}
Como o MDC de 3 e 1000 é 1, \(3^j\) não é divisível por 1000, logo
\begin{equation*} 3^{i-j} - 1 \equiv 0 \pmod{1000}\text{,} \end{equation*}
ou seja,
\begin{equation*} 3^{i-j} \equiv 1 \pmod{1000}\text{.} \end{equation*}
Isso significa que essa potência termina em 001.

6.

(Longlist IMO 1977 - Romênia) Dados 37 pontos no espaço com coordenadas inteiras, prove que pelo menos um dos triângulos formado por três destes pontos possui o baricentro com coordenadas inteiras.
Solução.
O baricentro \(G\) é dado por \(\left(\frac{x_1+x_2+x_3}{3}, \frac{y_1+y_2+y_3}{3}, \frac{z_1+z_2+z_3}{3}\right)\text{.}\) Temos 37 pontos, como \(\lceil\frac{37}{3}\rceil = 13\text{,}\) há pelo menos 13 pontos com o mesmo resto na divisão por 3 na primeira coordenada. Ou seja, quaisquer 3 desses, a soma será múltiplo de 3, na primeira coordenada.
Olhando para a 2ª coordenada, dos 13 pontos temos pelo menos \(\lceil\frac{13}{3}\rceil = 5\) com a 2ª coordenada com mesmo resto na divisão por 3. Sejam \(P_1, P_2, P_3, P_4, P_5\) esses 5 pontos. Quaisquer 3 desses pontos geram um triângulo cujo baricentro possui as 2 primeiras coordenadas inteiras.
Agora, precisamos mostrar que dos 5 inteiros que estão na 3ª coordenada dos pontos \(P_1, \dots, P_5\text{,}\) sempre há 3 cuja soma é um múltiplo de 3.
  1. 1º caso: os 3 restos possíveis na divisão por 3 (0, 1 e 2) aparecem. Neste caso, basta usar esses 3 pontos (\(0+1+2=3\)).
  2. 2º caso: Um dos restos não aparece. Então, temos 5 números e 2 restos possíveis. Como \(\lceil\frac{5}{2}\rceil = 3\text{,}\) pelo menos 3 possuem o mesmo resto. Logo, usando esses três pontos, o baricentro terá coordenadas inteiras.

7.

Em cada casa de um tabuleiro \(10\times 10\) é posto um inteiro de modo que a diferença positiva entre dois os inteiros de duas casas vizinhas (lado em comum) é no máximo 5. Prove que dois destes inteiros devem ser iguais.
Solução.
Seja \(a\) o menor valor do tabuleiro.
  • De \(a\) para um vizinho o valor máximo é \(a+5\text{;}\)
  • A distância máxima entre dois quadrados do tabuleiro pode ser dada quando um dos quadrados está no canto inferior esquerdo e o outro no canto superior direito. Logo, a distância máxima é \(9+9=18\text{.}\)
Portanto, o valor máximo possível é \(a+18\cdot 5 = a+90.\) Assim, os números do tabuleiro podem variar de \(a\) até \(a+90\text{.}\) No total são \(91\) números possíveis e são \(100\) quadrados. Pelo PCP, pelo menos dois quadrados vão ter o mesmo número.

8.

Trinta e três torres são postas em um tabuleiro 8x8. Prove que podemos escolher cinco delas sem que nenhuma ataque a outra.
Solução.
Ordene as linhas de forma decrescente pela quantidade de torres: \(L_1, L_2, \dots, L_8\text{.}\) A linha com mais torres possui pelo menos \(\lceil\frac{33}{8}\rceil = 5\text{.}\)
Considere apenas as outras linhas (são 7), e pelo menos \(33-8=25\) torres. \(\lceil\frac{25}{7}\rceil = 4\) é o número mínimo de torres na linha \(L_2\text{.}\)
Considere apenas as linhas \(L_3, L_4, \dots, L_8\text{.}\) São 6 linhas e pelo menos \(25-8=17\) torres. \(\lceil\frac{17}{6}\rceil = 3\) é o mínimo de torres na linha \(L_3\text{.}\)
Para \(L_4, L_5, L_6, L_7, L_8\) são 5 linhas e pelo menos 12 torres. \(\lceil\frac{12}{5}\rceil = 3\) na linha \(L_4\text{.}\)
Para \(L_5, L_6, L_7, L_8\) são 4 linhas e pelo menos 4 torres. Então pelo menos 1 linha possui 1 torre.
Olhando apenas para as linhas \(L_1, L_2, L_3, L_4, L_5\text{,}\) vamos selecionar 5 torres que não se atacam. Selecione a única torre da linha \(L_5\text{.}\) Na linha \(L_4\) selecione a única torre que não está na coluna da torre de \(L_5\text{.}\) Seguindo assim, selecionamos as 5 torres que não se atacam.

9.

(Longlist IMO 1979 Bulgária) Colocamos \(4n+1\) reis em um tabuleiro infinito. Prove que podemos escolher \(n+1\) deles de modo que não existam dois que se ataquem.
Solução.
Um rei na casa \((x, y)\) pode atacar as casas com coordenadas que diferem no máximo por 1. Ou seja, se outro rei está na casa \((a, b)\text{,}\) um pode atacar o outro se \(|x-a| \le 1\) e \(|y-b| \le 1\text{.}\) Além disso, se dois reis estão em casas com mesma paridade, eles não podem atacar um ao outro, pois \(|x-a| > 1\) ou \(|y-b| > 1\text{.}\)
Considere as casas divididas em 4 grupos: Casa 1 (PAR, PAR); Casa 2 (PAR, ÍMPAR); Casa 3 (ÍMPAR, PAR); Casa 4 (ÍMPAR, ÍMPAR). Como temos \(\lceil\frac{4n+1}{4}\rceil = n+1\text{,}\) pelo PCP, pelo menos \(n+1\) reis estão na mesma classe (casa), logo não se atacam.

10.

Prove que de qualquer subconjunto de \(n+1\) elementos do conjunto \(\{1, 2, \dots, 2n\}\) é possível escolher dois que sejam primos entre si.
Solução.
Observe que o MDC de dois números consecutivos é igual a 1: \(mdc(a, a+1) = mdc(a, (a+1)-a) = mdc(a, 1) = 1\text{.}\) Dos \(2n\) números consecutivos serão selecionados \(n+1\text{.}\) Se selecionarmos 2 consecutivos eles serão primos entre si.
Só existem duas maneiras de selecionar \(n\) números dentre \(2n\) sem selecionar dois consecutivos. Selecione todos os pares ou todos os ímpares. Ao selecionar o \((n+1)\)-ésimo elemento ele terá paridade diferente dos demais \(n\) elementos e ficará entre dois números previamente selecionados. Logo, teremos 3 números consecutivos. Quaisquer 2 consecutivos, desses 3, serão primos entre si.

11.

Quarenta estudantes participaram de uma olimpíada de matemática. A prova consistia de cinco problemas ao todo. Sabe-se que cada problema foi resolvido corretamente por pelo menos 23 participantes. Prove que deve existir dois participantes tais que todo problema foi resolvido por pelo menos um deles dois.
Solução.
Existem \(23 \times 5 = 115\) soluções corretas. Como \(\frac{115}{40} \approx 2.875\text{,}\) pelo PCP, pelo menos 1 estudante acertou pelo menos 3 problemas. Chamaremos ele de A.
Digamos que A não resolveu dois problemas. Então, cada um deles foi resolvido por pelo menos 22 estudantes. São 44 soluções corretas e 39 estudantes. Como \(\lceil\frac{44}{39}\rceil = 2\text{,}\) pelo PCP, pelo menos 1 estudante acertou pelo menos esses dois problemas. Chame ele de B. Assim, todo problema da prova foi resolvido por A ou B.

12.

Prove que todo número natural tem um múltiplo que se escreve, na base 10, apenas com os algarismos 0 e 1.
Solução.
Seja \(n\) um número natural qualquer. Considere os números \(1, 11, 111, 1111, \dots, 111\dots1\) (com \(n+1\) dígitos). São mais números que restos possíveis na divisão por \(n\text{.}\) Pelo PCP, pelo menos 2 possuem o mesmo resto: digamos \(11\dots1\) (com \(i\) dígitos) e \(11\dots1\) (com \(j\) dígitos, \(i > j\)). A diferença entre eles é \(11\dots100\dots0 \equiv 0 \pmod{n}\text{,}\) que é um múltiplo desejado.

13.

Mostre que se escolhemos 800 pontos de um cubo de aresta 10, pelo menos um dos segmentos determinados por esses pontos tem comprimento menor que 2.
Solução.
Divida as arestas em segmentos de tamanho \(10/9\text{.}\) Assim, cada aresta tem 9 segmentos e podemos subdividir o cubo em \(9 \times 9 \times 9 = 729\) cubos menores. Como são 800 pontos e 729 cubos, pelo PCP, pelo menos 1 cubo vai possuir pelo menos 2 pontos. A distância máxima dentro de um cubo desses é a sua diagonal: \(\sqrt{\left(\frac{10}{9}\right)^2 + \left(\frac{10}{9}\right)^2 + \left(\frac{10}{9}\right)^2} = \sqrt{3 \cdot \left(\frac{10}{9}\right)^2} = \frac{10\sqrt{3}}{9} \approx 1,92 < 2\text{.}\)

14.

Um mestre de xadrez, preparando-se para um torneio, joga, durante onze semanas, pelo menos uma partida por dia mas não mais que doze partidas por semana. Prove que existe um conjunto de dias consecutivos durante os quais ele joga exatamente 20 partidas.
Solução.
11 semanas são 77 dias. Seja \(S_i\) a soma do número de jogos do dia 1 até o dia \(i\text{.}\) Temos \(1 \le S_1 < S_2 < \dots < S_{77} \le 132\) (pois o total de jogos \(\le 12 \times 11 = 132\)). Defina \(T_i = S_i + 20\text{.}\) Assim, \(21 \le T_1 < T_2 < \dots < T_{77} \le 152\text{.}\)
São 154 valores (os \(S_i\) e os \(T_i\)) e 152 números possíveis. Pelo PCP, pelo menos 2 valores precisam ser iguais. Como \(S_i\) e \(T_j\) são estritamente crescentes, os dois valores que são iguais precisam ser \(T_j = S_i\) para algum \(i\) e algum \(j\text{.}\) Logo, \(S_j + 20 = S_i \Rightarrow S_i - S_j = 20\text{.}\) Entre os dias \(j+1\) e \(i\) foram jogadas 20 partidas.

15.

Escolha, dentre os elementos do conjunto \(\{1, 2, \dots, 200\}\text{,}\) 101 números ao acaso. Mostre que, entre os números escolhidos, há dois números tais que um deles divide o outro.
Solução.
Reescreva os elementos do conjunto da seguinte maneira: \(\{2^{k_1} \cdot b_1, 2^{k_2} \cdot b_2, \dots, 2^{k_{200}} \cdot b_{200}\}\text{,}\) de maneira que \(k_i\) seja a maior potência de 2 possível e \(b_i\) seja ímpar. Como são 200 números (100 pares e 100 ímpares), no máximo 100 \(b_i\)'s serão distintos. No conjunto, como serão escolhidos 101 números, pelo menos dois \(b_i\)'s serão iguais: \(b_i = b_j\text{.}\) Os números serão da forma \(2^{k_i} \cdot b\) e \(2^{k_j} \cdot b\text{.}\) Se \(k_j > k_i\text{,}\) então o menor número divide o maior.
<Anterior^TopPróximo>
Feito com PreTeXt
Powered by Runestone