Olimpíadas ⇒ Maior [tex3]k[/tex3] e menor [tex3]m[/tex3]

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

[csmarceloMOD]

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

[FelipeMartinMOD]

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

[goncalves3718]

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

[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