Dado o conjunto A=1,2,3, ldots, 2015, forma-se um subconjunto B , com a maior quantidade possivel 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
© 11
(D) 12
(E) 13

Passo 1

O exercício pede o tamanho máximo de um subconjunto B de A={1,2,3,…,2015} tal que para quaisquer x,y em B valha x|y ou y|x. Isso é achar a maior cadeia (chain) no poset de divisibilidade em A. Vamos usar fatoração prima e propriedades de cadeias por divisibilidade.

Passo 2

Em uma cadeia de divisibilidade n₁|n₂|…|n_k, cada passo de n_i para n_{i+1} multiplica por algum primo. Se n_k tem fatoração nk=2^a3^b5^ccdots, então k–1 ≤ a+b+c+… (pois cada multiplicação aumenta um desses expoentes em pelo menos 1). Logo k ≤ 1 + (a+b+c+…). Precisamos escolher n_k ≤ 2015 que maximize a+b+c+…

Passo 3

Para maximizar a+b+c+… sob a restrição n_k ≤ 2015, devemos usar o menor primo repetidamente, ou seja, 2. Vamos ver até qual potência de 2 cabe em 2015:
2^10 = 1024, 2^11 = 2048 > 2015
Assim o maior expoente possível é a=10 e a soma de expoentes é 10. Logo o comprimento máximo da cadeia é k = 1 + 10 = 11.

Passo 4

Uma cadeia de tamanho 11 que cabe em A é por exemplo:
1, 2, 2^2=4, 2^3=8, 2^4=16, 2^5=32, 2^6=64, 2^7=128, 2^8=256, 2^9=512, 2^10=1024
Portanto o maior subconjunto B tem 11 elementos.

Resposta

11

Exercícios relacionados