Dado o conjunto
, 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
(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
, 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:
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:
Portanto o maior subconjunto B tem 11 elementos.
Resposta
11