Question

Um experimento realizado com 150 pessoas solicitava que cada participante recebesse como identificação um dos números entre 1 e 150. Em seguida, eles eram conduzidos a uma sala onde 150 lâmpadas, cada uma delas numeradas de 1 a 150 e com seu respectivo interruptor. Inicialmente, todas as lâmpadas estavam acesas. Então, foi solicitado que, a partir do participante número 1, cada pessoa deveria inverter o estado de todas as lâmpadas cuja numeração fosse um divisor do número recebido pelo participante antes de entrar na sala. Quantas lâmpadas ficaram apagadas no fim do experimento?

Gabarito: 104.

Gentileza explicar passo a passo como você chegou ao resultado, detalhando o seu raciocínio para resolução da questão. Obrigado.

Answer 1

No fim do experimento, ficaram apagadas 104 lâmpadas.

_____

Observe que a lâmpada número $n$ ficou apagada se o número de múltiplos de $n$ no intervalo $[1,\,150]$ for ímpar.

Podemos executar a resolução desta questão usando força bruta. Mas aqui será apresentada uma sequência de números inteiros cujo um de seus termos é o número de lâmpadas procurado.

Para isso, vamos precisar da definição de piso de um número real.

Definição (Piso). O piso de um número real $x$, denotado por $\lfloor x\rfloor,$ é o maior número inteiro que é menor ou igual a $x,$ ou seja,

$\Large\text{ \lfloor x\rfloor=\max\{m\in\mathbb{Z}: m\leq x\}. }$

Exemplos:

• $\lfloor 2\rfloor=2.$

• $\lfloor3{,}4\rfloor=3.$

• $\lfloor-2{,}6\rfloor=-3.$

Sejam $k$ e $n$ dois números inteiros positivos com $k\leq n$. Pode-se demonstrar que o número de múltiplos de $k$ no intervalo $[1,\,n]$ é dado por

$\Large\left\lfloor\dfrac{n}{k}\right\rfloor.$

Assim sendo, o problema em questão se resume a encontrar o número de elementos do conjunto $\left\{\left\lfloor\dfrac{150}{k} \right\rfloor: 1\leq k\leq 150\right\}$ que são ímpares.

A sequência de números inteiros que informa a quantidade de elementos do conjunto $\left\{\left\lfloor\dfrac{n}{k} \right\rfloor; 1\leq k\leq n\right\}$ que são ímpares é a seguinte:

$\Largea_n=\left\lfloor\dfrac{n}{1}\right\rfloor -\left\lfloor \dfrac{n}{2}\right\rfloor+\left\lfloor\dfrac{n}{3} \right\rfloor - \left\lfloor \dfrac{n}{4} \right\rfloor + \ldots$

Essa soma é finita e tal sequência é aquela identificada pelo código A059851 na OIES (The On-Line Encyclopedia of Integer Sequences).

Consequentemente, a resposta para esse problema é dada pelo 150º termo dessa sequência, ou seja, por:

$\Largea_{150}=\left\lfloor\dfrac{150}{1}\right\rfloor -\left\lfloor \dfrac{150}{2}\right\rfloor+\left\lfloor\dfrac{150}{3} \right\rfloor - \left\lfloor \dfrac{150}{4} \right\rfloor + \ldots$

Entretanto, não há fórmulas muito simples de calcular esses termos. Algumas delas são:

$\Large\text{ a_n=\displaystyle\sum_{k=1}^n d(k)-2\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor} d(k), }$

em que $d(k)$ é o número de divisores positivos de $k,$

e

$\Largea_n=\displaystyle\sum_{k=1}^n \left(\left\lfloor\frac{n}{k}\right\rfloor\mod 2\right).$

Usando a primeira fórmula para calcular o termo $a_{150},$ temos:

$\Large\begin{aligned}a_{150}&=\displaystyle\sum_{k=1}^{150}d(k)-2\sum_{k=1}^{\left\lfloor\frac{150}{2}\right\rfloor}d(k)\\\\&=\sum_{k=1}^{150}d(k)-2\sum_{k=1}^{75}d(k)\\\\&=780-2\cdot338\\\\&=780-676\\\\&=104.\end{aligned}$

Veja que não é uma tarefa simples calcular  $\displaystyle\sum_{k=1}^nd(k)$para valores elevados de $n.$ Os valores obtidos acima foram tirados da tabelas da sequência A006218 da OEIS.

Poderíamos recorrer também diretamente à tabela de valores da sequência A059851. Segue uma reprodução de tal tabela para alguns valores de $n.$

$\Large\begin{array}{c|c}n&a_n\\1&1\\2&1\\3&3\\4&2\\5&4\\6&4\\7&6\\8&4\\9&7\\10&7\\\vdots&\vdots\\150&\boxed{104}\end{array}$

Veja que o 150º termo é o 104, ou seja, há 104 números ímpares no conjunto $\left\{\left\lfloor\dfrac{150}{k} \right\rfloor: 1\leq k\leq 150\right\}.$

Portanto, ficaram 104 lâmpadas apagadas no fim do experimento.

Espero ter ajudado!

Para ver mais conteúdo sobre teoria dos números, acesse:

• brainly.com.br/tarefa/50053443;
• brainly.com.br/tarefa/50055130.