Questão CN 2015-2016

Sejam A = { 1, 2, 3, ..., 4029, 4030 } um subconjunto dos números naturais e B está contido em A, tal que não existem x e y, x#y, pertencentes a B nos quais x divida y. O numero máximo de elementos de B é N. Sendo assim, a soma dos algarismos de N é :

(A) 8
(B) 9
(C) 10 
(D) 11
(E) 12

Podemos ter y=4030 e de em os ter x de tal forma que seja primo com y, pois não o pode dividir. Em suma, procuramos o n° de primos até o número limite do conjunto A (4030). Este será N, o número máximo de elementos de B e é denominado número de Euler.

4030 = 2 × 5 × 13 × 15

N = 4030.(1 - 1/2).(1 - 1/5).(1 - 1/13).(1 - 1/31)
N = 4030. (1/2). (4/5). (12/13). (30/31) = 1440

Portanto, B tem 1440 elementos, cuja soma dos algarismos é 9 ------> (b)

Fiz exatamente isso, a idéia do Phi de Euller, porém errei na multiplicação, muito obrigado Medeiros.

Medeiros escreveu:Podemos ter y=4030 e de em os ter x de tal forma que seja primo com y, pois não o pode dividir. Em suma, procuramos o n° de primos até o número limite do conjunto A (4030). Este será N, o número máximo de elementos de B e é denominado número de Euler.

4030 = 2 × 5 × 13 × 15

N = 4030.(1 - 1/2).(1 - 1/5).(1 - 1/13).(1 - 1/31)
N = 4030. (1/2). (4/5). (12/13). (30/31) = 1440

Portanto,  B tem 1440 elementos, cuja soma dos algarismos é 9 ------> (b)

Acho que ocorreu uma desatenção apenas na fatoração de 4030 : "2 x 5 x 13 x 15", o correto seria 31 ao invés do 15, mas de resto, foi excelente.

Estava pensando agora, o que me garante que o número com mais primos em comum é o 4030 ?

Também me perguntei isso e não soube me responder. Por outro lado, esta é uma questão de prova -- teste no qual se busca aferir a bagagem de conhecimentos do candidato e a capacidade de usa-los logicamente -- e não deve exigir desenvolvimentos longos, muito elaborados e demorados, por isso acho que a resposta deve mesmo ser simples como esta que pensamos; é o que eu faria sem remorso. Você tem o gabarito?

Letra A, mas ainda é o gabarito provisório.

Prezados, estive refletindo sobre a questão e conclui que não são os números primos entre si menores que 4030 que o problema pede, poderemos, como exemplo, ter o número 2020 que não é primo entre si com 4030 porém não possui nenhum divisor entre 1 e 4030.  Dessa maneira, a fórmula de Euller apresentaria uma quantidade de números menor do que o procurado.
Encaminho a solução abaixo para análise dos senhores.



Solução proposta:
Em um intervalo (n/2, n] teremos sempre uma quantidade de números  “n – n/2” que não são divisíveis um pelo outro. Exemplo,  entre (7, 14] temos 7 números que não são divisíveis um pelo outro. No problema proposto, entre (2015, 4030] temos 2015 números que não são divisíveis um pelo outro. Os demais números do conjunto A, menores  ou iguais a 2015, serão excluídos pois serão, obrigatoriamente, divisores dos números que aparecem nesse maior intervalo.  Dessa forma,  temos 2015 elementos no conjunto B , e a soma dos algarismos de N será 2 + 0 +1+ 5 = 8, opção A.
Com relação a utilização do  Ø de Euller para cálculo do número de elementos , Ø=N(1-1/a)(1-1/b)...(1-1/c), ressalta-se que essa fórmula permite o cálculo da quantidade de números primos entre si até um número N, então, ele não abarcaria os pares de números que mesmo não sendo primos entre si ainda assim não podem ser divisíveis um pelo outro. Exemplo: o número 2020 não é contabilizado no Ø de Euller porém, ele deveria entrar no conjunto B pois não divide nenhum número no intervalo de 1 a 4030.
 
Abraços,  Luiz Fernando.

Obrigado, Luiz Fernando.

Entendo que você equacionou o problema de forma correta e, de fato, B inicia-se em (4030÷2)+1.

Então, confirmaste o gabarito.

Acho que nao devemos somar o 1 pois o intervalo é aberto à esquerda, (2015, 4030 l.
Logo teremos 4030 - 2015= 2015, soma dos algarismos 8, que é o gabarito da banca do CN.
Abracos