Questão 19 (Nível 3) da OBMEP 2015

Question

Dado o conjunto A = \{1, 2, 3, \ldots, 2015\}, forma-se um subconjunto B, com a maior quantidade possível de elementos, tal que todo elemento de B é múltiplo ou divisor de qualquer outro elemento de B. Quantos elementos há no conjunto B?

A
9
B
10
C
11
D
12
E
13

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 19 (Nível 3) da OBMEP 2015

Nível 3 · Matemática: Divisibilidade, MMC e MDC

Dado o conjunto A = \{1, 2, 3, \ldots, 2015\}, forma-se um subconjunto B, com a maior quantidade possível de elementos, tal que todo elemento de B é múltiplo ou divisor de qualquer outro elemento de B. Quantos elementos há no conjunto B?

A
9
B
10
C
11
D
12
E
13

Escolha uma alternativa para conferir o gabarito.

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

Existem vários subconjuntos que satisfazem às condições do enunciado; todos eles com 11 elementos. Por exemplo: \text{B1} = \{ 1, 2, 2^2, 2^3, 2^4, 2^5, 2^6, 2^7, 2^8, 2^9, 2^{10} \}, \text{B2} = \{1, 3, 2.3, 2^2.3, 2^3.3, 2^4.3, 2^5.3, 2^6.3, 2^7.3, 2^8.3, 2^9.3 \} e \text{B3} = \{ 1, 2, 2^2, 2^3, 2^4, 2^5, 2^6, 2^7, 2^8, 2^9, 2^9.3 \}. A solução anteriormente divulgada está incorreta; ela contempla apenas o primeiro exemplo.

Não é possível construir um subconjunto de A nas condições descritas no enunciado, contendo 12 ou mais elementos. De fato, suponhamos que isto fosse possível, e seja B um subconjunto de A, com k \ge 12 elementos. Seja n o maior elemento de B. Então, n deve ser múltiplo dos demais elementos de B. Logo n deve possuir k divisores positivos (ele próprio e os demais k-1 elementos do conjunto). O menor número n que possui k divisores positivos é 2^{k-1}. Entretanto, 2^{k-1} \ge 2^{11} = 2048 > 2015, pois k \ge 12. Logo, n > 2015 e, portanto, n não pode pertencer a B, já que B é subconjunto de A. Esta contradição surge da suposição de que B tem mais do que 11 elementos. Assim, os subconjuntos de A com a maior quantidade possível de elementos, que satisfazem as condições do enunciado, possuem 11 elementos.

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

Se todo par de elementos de B é tal que um divide o outro, podemos ordenar B como b_1<b_2<\dots<b_k com b_1\mid b_2\mid\dots\mid b_k. Cada termo é múltiplo do anterior e diferente dele, então é pelo menos o dobro: b_{i+1}\ge 2b_i.

Para ter o maior número de elementos, o melhor é começar de b_1=1 e dobrar sempre. Assim, b_k\ge 2^{k-1}.

Como b_k\le 2015, precisamos de 2^{k-1}\le 2015.

2^{10}=1024\le 2015, então k-1=10 é possível.
2^{11}=2048>2015, então k-1=11 não é possível.

Logo k-1\le 10, ou seja, k\le 11.

Exemplo com 11 elementos: B=\{1,2,4,8,16,32,64,128,256,512,1024\}. Cada elemento divide o seguinte, e todos estão em A.

Portanto o maior B possível tem 11 elementos.

Alternativa C.

Pegadinha: A alternativa B engana quem lista 2^1 até 2^{10} e esquece de incluir o 1, que é 2^0.

Por que as outras alternativas estão erradas

ASubestima: ficaria só até 2^8=256, deixando de usar potências de 2 que ainda cabem em A.
BConta só os expoentes de 1 a 10 e esquece o elemento 1 (2^0).
DExigiria 2^{11}=2048, que ultrapassa 2015.
EExigiria 2^{12}=4096, muito maior que 2015.

Assunto: Divisibilidade, MMC e MDC.

Reportar erro na resolução

Ver como caiu na prova

Questão 19 no caderno Nível 3 da OBMEP 2015

Fonte: OBMEP 2015 · Nível 3. Prova oficial ↗