OlimpíadasMaior [tex3]k[/tex3] e menor [tex3]m[/tex3]

Aqui devem ser postados problemas Olímpicos. Informe a olimpíada e o ano no título do tópico. Exemplo: (OBM - 2008).

Moderador: [ Moderadores TTB ]

Autor do Tópico
goncalves3718
3 - Destaque
Mensagens: 816
Registrado em: Qui 26 Dez, 2019 15:26
Última visita: 11-04-23
Jan 2021 14 16:56

Maior [tex3]k[/tex3] e menor [tex3]m[/tex3]

Mensagem não lida por goncalves3718 »

Sejam [tex3]A[/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] .

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




Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 5114
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 17-04-23
Jan 2021 14 17:52

Re: Maior [tex3]k[/tex3] e menor [tex3]m[/tex3]

Mensagem não lida por csmarcelo »

O que seria [tex3]|A|[/tex3] ?




FelipeMartin
4 - Sabe Tudo
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]

Mensagem não lida por FelipeMartin »

csmarcelo, cardinalidade de A. No caso, número de elementos de A.


φως εσύ και καρδιά μου εγώ πόσο σ' αγαπώ.

Autor do Tópico
goncalves3718
3 - Destaque
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]

Mensagem não lida por goncalves3718 »

Isso mesmo! No caso os conjuntos [tex3]A[/tex3] e [tex3]B[/tex3] devem ter a mesma quantidade de elementos...



Avatar do usuário
leozitz
2 - Nerd
Mensagens: 331
Registrado em: Qui 06 Jan, 2022 16:26
Última visita: 26-02-24
Jan 2022 14 18:45

Re: Maior [tex3]k[/tex3] e menor [tex3]m[/tex3]

Mensagem não lida por leozitz »

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




Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Olimpíadas”