Página 1 de 2
Casas dos Pombos (Princípio de Derichlet)
Enviado: 28 Fev 2019, 20:36
por ALANSILVA
Escolha, dentre os elementos do conjunto {[tex3]1,2,...,200[/tex3]
}, [tex3]101[/tex3]
números ao acaso. Mostre que, entre os números escolhidos, há dois números tais que um deles divide o outro.
Re: Casas dos Pombos (Princípio de Derichlet)
Enviado: 01 Mar 2019, 12:36
por MateusQqMD
A ideia é usar que qualquer natural [tex3]n[/tex3]
pode ser escrito sob a forma [tex3]n = 2^k \cdot d[/tex3]
, com [tex3]k[/tex3]
inteiro não negativo e [tex3]d[/tex3]
inteiro ímpar.
Para essa questão, por exemplo, [tex3]1 = 2^0 \cdot 1,\,\, 2 = 2^1 \cdot 1,\,\, 3 = 2^0 \cdot 3,\,\, ..,\,\, 199 = 2^0 \cdot 199,\,\, 200 = 2^3 \cdot 25[/tex3]
Note, agora, que há [tex3]100[/tex3]
valores possíveis para [tex3]d[/tex3]
, [tex3]\{ 1, \,\, 3, \,\, 5, \,\, 7, \,\, ..., \,\, 199 \}[/tex3]
, ou seja, escolhendo 101 números do conjunto [tex3]\{1, \,\,2, \,\,...,\,\,200\}[/tex3]
, teremos pelo menos dois deles com o mesmo d. Sejam esses números [tex3]n_1 = 2^{k_1} \cdot d[/tex3]
e [tex3]n_2 = 2^{k_2} \cdot d[/tex3]
. Se [tex3]k_1 < k_2[/tex3]
então implica que [tex3]n_1 | n_2 [/tex3]
; se [tex3]k_1 > k_2[/tex3]
então implica que [tex3]n_2 | n_1[/tex3]
.
Re: Casas dos Pombos (Princípio de Derichlet)
Enviado: 01 Mar 2019, 14:59
por Valdir
MateusQqMD escreveu: ↑01 Mar 2019, 12:36
A ideia é usar que qualquer natural [tex3]n[/tex3]
pode ser escrito sob a forma [tex3]n = 2^k \cdot d[/tex3]
, com [tex3]k[/tex3]
inteiro não negativo e [tex3]d[/tex3]
inteiro ímpar.
Para essa questão, por exemplo, [tex3]1 = 2^0 \cdot 1,\,\, 2 = 2^1 \cdot 1,\,\, 3 = 2^0 \cdot 3,\,\, ..,\,\, 199 = 2^0 \cdot 199,\,\, 200 = 2^3 \cdot 25[/tex3]
Note, agora, que há [tex3]100[/tex3]
valores possíveis para [tex3]d[/tex3]
, [tex3]\{ 1, \,\, 3, \,\, 5, \,\, 7, \,\, ..., \,\, 199 \}[/tex3]
, ou seja, escolhendo 101 números do conjunto [tex3]\{1, \,\,2, \,\,...,\,\,200\}[/tex3]
, teremos
pelo menos dois deles com o mesmo
d. Sejam esses números [tex3]n_1 = 2^{k_1} \cdot d[/tex3]
e [tex3]n_2 = 2^{k_2} \cdot d[/tex3]
. Se [tex3]k_1 < k_2[/tex3]
então implica que [tex3]n_1 | n_2 [/tex3]
; se [tex3]k_1 > k_2[/tex3]
então implica que [tex3]n_2 | n_1[/tex3]
.
Entendi a lógica, mas não entendi essa notação: [tex3]n_1 | n_2 [/tex3]
Eu não entendi o que essa "|" significa.
Re: Casas dos Pombos (Princípio de Derichlet)
Enviado: 01 Mar 2019, 15:52
por ALANSILVA
Olá Matheus
Se [tex3]k_{1}<k_{2}[/tex3]
então [tex3]n_{2}[/tex3]
divide [tex3]n_{1}[/tex3]
ou estou errado?
Re: Casas dos Pombos (Princípio de Derichlet)
Enviado: 01 Mar 2019, 15:54
por ALANSILVA
Valdir o traço | é divisão
Re: Casas dos Pombos (Princípio de Derichlet)
Enviado: 01 Mar 2019, 16:15
por Valdir
ALANSILVA escreveu: ↑01 Mar 2019, 15:54
Valdir o traço | é divisão
Entendi, mas em português fica como ? [tex3]n_2 | n_1[/tex3]
[tex3]n_2 [/tex3]
divide [tex3]n_1[/tex3]
Lê-se assim?
Re: Casas dos Pombos (Princípio de Derichlet)
Enviado: 01 Mar 2019, 17:31
por MateusQqMD
ALANSILVA escreveu: ↑01 Mar 2019, 15:52
Olá Matheus
Se [tex3]k_{1}<k_{2}[/tex3]
então [tex3]n_{2}[/tex3]
divide [tex3]n_{1}[/tex3]
ou estou errado?
Oi, Alan
Tome como exemplo [tex3]k_1[/tex3]
= 5 e [tex3]k_2 = 3[/tex3]
Logo,
[tex3]n_1 = 2^5 \cdot d[/tex3]
[tex3]n_2 = 2^3\cdot d[/tex3]
Portanto, [tex3]n_2[/tex3]
divide [tex3]n_1[/tex3]
, [tex3]\frac{2^5 \cdot d}{2^3\cdot d} = 4[/tex3]
Re: Casas dos Pombos (Princípio de Derichlet)
Enviado: 01 Mar 2019, 17:31
por MateusQqMD
Valdir escreveu: ↑01 Mar 2019, 16:15
ALANSILVA escreveu: ↑01 Mar 2019, 15:54
Valdir o traço | é divisão
Entendi, mas em português fica como ? [tex3]n_2 | n_1[/tex3]
[tex3]n_2 [/tex3]
divide [tex3]n_1[/tex3]
Lê-se assim?
Isso mesmo,
Valdir
Re: Casas dos Pombos (Princípio de Derichlet)
Enviado: 01 Mar 2019, 23:06
por ALANSILVA
MateusQqMD, boa noite
Onde posso encontrar a forma do número natural [tex3]n=2^k.d[/tex3]
, sendo [tex3]d[/tex3]
um inteiro?
Re: Casas dos Pombos (Princípio de Derichlet)
Enviado: 02 Mar 2019, 00:56
por MateusQqMD
ALANSILVA escreveu: ↑01 Mar 2019, 23:06
MateusQqMD, boa noite
Onde posso encontrar a forma do número natural [tex3]n=2^k.d[/tex3]
, sendo [tex3]d[/tex3]
um inteiro?
não tenho nada aqui