Sejam [tex3]A[/tex3]
a) Encontre o maior inteiro [tex3]k[/tex3]
possível para o qual existem conjuntos [tex3]A, B ⊂ \mathbb{N}[/tex3]
tais que [tex3]|A| = |B| = k[/tex3]
e [tex3]A + B = \{0, 1, 2, · · · , 2016\}[/tex3]
.
b) Encontre o menor inteiro [tex3]m[/tex3]
possível para o qual existem conjuntos [tex3]A, B ⊂ \mathbb{N}[/tex3]
tais que [tex3]|A| = |B| = m[/tex3]
e [tex3]A + B = \{0, 1, 2, · · · , 2016\}[/tex3]
.
e [tex3]B[/tex3]
dois conjuntos finitos e não vazios. Seja [tex3]A + B[/tex3]
o conjunto definido por [tex3]\{a + b | a ∈ A, b ∈ B\}[/tex3]
.Olimpíadas ⇒ Maior [tex3]k[/tex3] e menor [tex3]m[/tex3]
Moderador: [ Moderadores TTB ]
-
- Mensagens: 2196
- Registrado em: Sáb 04 Jul, 2020 10:47
- Última visita: 27-03-24
Jan 2021
14
17:59
Re: Maior [tex3]k[/tex3] e menor [tex3]m[/tex3]
csmarcelo, cardinalidade de A. No caso, número de elementos de A.
φως εσύ και καρδιά μου εγώ πόσο σ' αγαπώ.
-
- Mensagens: 816
- Registrado em: Qui 26 Dez, 2019 15:26
- Última visita: 11-04-23
Jan 2021
14
20:24
Re: Maior [tex3]k[/tex3] e menor [tex3]m[/tex3]
Isso mesmo! No caso os conjuntos [tex3]A[/tex3]
e [tex3]B[/tex3]
devem ter a mesma quantidade de elementos...
Jan 2022
14
18:45
Re: Maior [tex3]k[/tex3] e menor [tex3]m[/tex3]
obs: como A + B tem 0, acho que o problema está considerando N com 0
o item A é fácil pq [tex3]k-1 + k-1 \le max A + max B \le 2016[/tex3]
para o item b vamos provar o seguinte lema.
lema: |A + B| >= |A| + |B| - 1.
A = {a_1, ..., a_x}
B = {b_1, ..., b_y}, suponha que eles estejam em ordem i.e. b_1 < b_2 < ...< b_y
para provar isso podemos fazer
a_1 + b_1 < a_1 + b_2 < ... < a_1 + b_y
b_y + a_1 < b_y + a_2 < ... < b_y + a_x
onde ali em cima eu exibi y + x - 1 resultados diferentes, o jeito para ver que essas somas são diferentes é por tamanho mesmo.
2017 >= m + m - 1
1009 >= m
agora a questão é se tem uma construção com m = 1009, o caso de igualdade para o caso geral, se n me engano é quando eles estão em P.A., eu n me lembro ao certo, teria que demonstrar novamente mas de qualquer forma a construção nesse caso pode ser feita da seguinte forma.
A = {0, 1, 2, ..., 1008}
B = {0, 1, 2, ..., 1008}
tbm é claro que a soma desses conjuntos é {0, 1, ..., 2016} pq 1008 + 1008 = 2016 e eu posso fixar um número de algum dos conjuntos e usar o do outro, tipo {0, 1, ..., 1008} eu obtenho fixando o 0 e variando o outro em B e {1009, ..., 2016} eu obtenho fixando o 1008 e variando o outro
o item A é fácil pq [tex3]k-1 + k-1 \le max A + max B \le 2016[/tex3]
para o item b vamos provar o seguinte lema.
lema: |A + B| >= |A| + |B| - 1.
A = {a_1, ..., a_x}
B = {b_1, ..., b_y}, suponha que eles estejam em ordem i.e. b_1 < b_2 < ...< b_y
para provar isso podemos fazer
a_1 + b_1 < a_1 + b_2 < ... < a_1 + b_y
b_y + a_1 < b_y + a_2 < ... < b_y + a_x
onde ali em cima eu exibi y + x - 1 resultados diferentes, o jeito para ver que essas somas são diferentes é por tamanho mesmo.
2017 >= m + m - 1
1009 >= m
agora a questão é se tem uma construção com m = 1009, o caso de igualdade para o caso geral, se n me engano é quando eles estão em P.A., eu n me lembro ao certo, teria que demonstrar novamente mas de qualquer forma a construção nesse caso pode ser feita da seguinte forma.
A = {0, 1, 2, ..., 1008}
B = {0, 1, 2, ..., 1008}
tbm é claro que a soma desses conjuntos é {0, 1, ..., 2016} pq 1008 + 1008 = 2016 e eu posso fixar um número de algum dos conjuntos e usar o do outro, tipo {0, 1, ..., 1008} eu obtenho fixando o 0 e variando o outro em B e {1009, ..., 2016} eu obtenho fixando o 1008 e variando o outro
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 1 Respostas
- 2657 Exibições
-
Última msg por petras
-
- 4 Respostas
- 3660 Exibições
-
Última msg por Fibonacci13
-
- 0 Respostas
- 653 Exibições
-
Última msg por elidecoline
-
- 3 Respostas
- 780 Exibições
-
Última msg por Jigsaw
-
- 2 Respostas
- 321 Exibições
-
Última msg por geobson