Olimpíadas ⇒ Análise Combinatória: Princípio da Casa dos Pombos Tópico resolvido

[italoemanuell]

Prove que todo número natural tem um múltiplo que se escreve, na base [tex3]10,[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]10,[/tex3]

apenas com os algarismos [tex3]0[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]0[/tex3]

e [tex3]1.[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]1.[/tex3]

[caju]

Olá italoemanuell,

Vou provar que um número [tex3]n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n[/tex3]

tem um múltiplo que se escreve apenas com algarismos [tex3]0[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]0[/tex3]

e [tex3]1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]1[/tex3]

na base [tex3]10[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]10[/tex3]

.

Começamos pegando uma lista de [tex3]n+1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n+1[/tex3]

números da seguinte forma:

• [tex3]\begin{array}{c}
  1\\
  11\\
  111\\
  1111\\
  \ldots\\
  \underbrace{11111\ldots 1}_{\text{ }n+1 \\\text{ algarismos}}\end{array}[/tex3]

  Código: Selecionar tudoSHIFT+Click na eq = ZOOM

  [tex3]\begin{array}{c}
1\\
11\\
111\\
1111\\
\ldots\\
\underbrace{11111\ldots 1}_{\text{ }n+1 \\\text{ algarismos}}\end{array}[/tex3]

Agora vamos dividir (utilizando o algoritmo de Euclides) cada um destes números por [tex3]n.[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n.[/tex3]

• [tex3]1=Q_1\cdot n+r_1[/tex3]

  Código: Selecionar tudoSHIFT+Click na eq = ZOOM

  [tex3]1=Q_1\cdot n+r_1[/tex3]

  
  [tex3]11=Q_2\cdot n+r_2[/tex3]

  Código: Selecionar tudoSHIFT+Click na eq = ZOOM

  [tex3]11=Q_2\cdot n+r_2[/tex3]

  
  [tex3]111=Q_3\cdot n+r_3[/tex3]

  Código: Selecionar tudoSHIFT+Click na eq = ZOOM

  [tex3]111=Q_3\cdot n+r_3[/tex3]

  
  [tex3]1111=Q_4\cdot n+r_4[/tex3]

  Código: Selecionar tudoSHIFT+Click na eq = ZOOM

  [tex3]1111=Q_4\cdot n+r_4[/tex3]

  
  [tex3]\ldots[/tex3]

  Código: Selecionar tudoSHIFT+Click na eq = ZOOM

  [tex3]\ldots[/tex3]

  
  [tex3]11111\ldots 1=Q_{n+1}\cdot n+r_{n+1}[/tex3]

  Código: Selecionar tudoSHIFT+Click na eq = ZOOM

  [tex3]11111\ldots 1=Q_{n+1}\cdot n+r_{n+1}[/tex3]

Lembremos que, ao dividir um número por [tex3]n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n[/tex3]

, só podemos ter [tex3]n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n[/tex3]

diferentes restos (de [tex3]0[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]0[/tex3]

até [tex3]n-1).[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n-1).[/tex3]

Ou seja, como temos [tex3]n+1[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n+1[/tex3]

restos na listagem acima, pelo princípio da casa dos pombos, no mínimo dois restos serão iguais.

Digamos que, sem perda de generalidade, os restos iguais são o [tex3]p-[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]p-[/tex3]

ésimo e o [tex3]k-[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]k-[/tex3]

ésimo resto ([tex3]p\lt k[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]p\lt k[/tex3]

) da listagem acima:

• [tex3]\underbrace{1111\ldots1}_{\text{p algarismos}}=Q_p\cdot n+r_p[/tex3]

  Código: Selecionar tudoSHIFT+Click na eq = ZOOM

  [tex3]\underbrace{1111\ldots1}_{\text{p algarismos}}=Q_p\cdot n+r_p[/tex3]

  
  
  [tex3]\underbrace{111111\ldots1}_{\text{k algarismos}}=Q_k\cdot n+r_k[/tex3]

  Código: Selecionar tudoSHIFT+Click na eq = ZOOM

  [tex3]\underbrace{111111\ldots1}_{\text{k algarismos}}=Q_k\cdot n+r_k[/tex3]

Agora, fazemos a segunda equação menos a primeira. Note que do lado esquerdo da equação teremos um número somente com [tex3]0[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]0[/tex3]

e [tex3]1.[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]1.[/tex3]

• [tex3]\underbrace{1111\ldots1}_{\text{k-p algarismos}}\overbrace{000\ldots0}^{\text{p algarismos}}=(Q_k-Q_p)\cdot n+\underbrace{r_k-r_p}_{\text{ zero, pois s\tilde{a}o iguais}}[/tex3]

  Código: Selecionar tudoSHIFT+Click na eq = ZOOM

  [tex3]\underbrace{1111\ldots1}_{\text{k-p algarismos}}\overbrace{000\ldots0}^{\text{p algarismos}}=(Q_k-Q_p)\cdot n+\underbrace{r_k-r_p}_{\text{ zero, pois s\tilde{a}o iguais}}[/tex3]

Este é o número múltiplo de [tex3]n[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]n[/tex3]

que estávamos procurando!