Olimpíadas

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]

Mensagem não lidapor **caju** » 14 Out 2007, 12:17 · Mensagem não lida por **caju** » 14 Out 2007, 12:17

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

[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] , 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]
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] 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]
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] que estávamos procurando!

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

Análise Combinatória: Princípio da Casa dos Pombos

Re: Análise Combinatória: Princípio da Casa dos Pombos

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

Análise Combinatória: Princípio da Casa dos Pombos

Re: Análise Combinatória: Princípio da Casa dos Pombos

Entrar | Registrar