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] apenas com os algarismos [tex3]0[/tex3] e [tex3]1.[/tex3]

[cajuADMIN]

Olá italoemanuell,

Vou provar que um número [tex3]n[/tex3] tem um múltiplo que se escreve apenas com algarismos [tex3]0[/tex3] e [tex3]1[/tex3] na base [tex3]10[/tex3].

Começamos pegando uma lista de [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]

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

• [tex3]1=Q_1\cdot n+r_1[/tex3]
  [tex3]11=Q_2\cdot n+r_2[/tex3]
  [tex3]111=Q_3\cdot n+r_3[/tex3]
  [tex3]1111=Q_4\cdot n+r_4[/tex3]
  [tex3]\ldots[/tex3]
  [tex3]11111\ldots 1=Q_{n+1}\cdot n+r_{n+1}[/tex3]

Lembremos que, ao dividir um número por [tex3]n[/tex3], só podemos ter [tex3]n[/tex3] diferentes restos (de [tex3]0[/tex3] até [tex3]n-1).[/tex3]

Ou seja, como temos [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] ésimo e o [tex3]k-[/tex3] ésimo resto ([tex3]p\lt k[/tex3]) da listagem acima:

• [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]

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] e [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]

Este é o número múltiplo de [tex3]n[/tex3] que estávamos procurando!