Question

Sean $h_n$ y $k_n$ los únicos enteros positivos primos entre sí tales que

$\frac11+\frac12+\frac13+\cdots+\frac1n=\frac{h_n}{k_n}.$

Sea $L_n$ el mínimo común múltiplo de los números $1,$ $2,$ $3,$ $\ldots,$ $n.$ ¿Para cuántos enteros $n$ con $1\le n\le22$ se cumple $k_n\lt L_n$ ?

Let $h_n$ and $k_n$ be the unique relatively prime positive integers such that

$\frac11+\frac12+\frac13+\cdots+\frac1n=\frac{h_n}{k_n}.$

Let $L_n$ denote the least common multiple of the numbers $1,$ $2,$ $3,$ $\ldots,$ $n.$ For how many integers $n$ with $1\le n\le22$ is $k_n\lt L_n?$

$0$

$3$

$7$

$8$

$10$

Respuesta: D

Conceptos:mínimo común múltiplo factorización en primos aritmética modular

Nivel de dificultad: 2520

Pista pequeña:

Escribiendo $H_n$ sobre $L_n,$ el denominador reducido es menor exactamente cuando un primo se cancela del numerador $\sum_k \frac{L_n}{k}$

Writing $H_n$ over $L_n,$ the reduced denominator is smaller exactly when a prime cancels from the numerator $\sum_k \frac{L_n}{k}$

Pista grande:

Para una potencia de primo $p^a$ con $p^a\le n\lt p^{a+1},$ verifica si $p$ divide a $\sum_{v_p(k)=a} \frac{L_n}{k}$

For a prime power $p^a$ with $p^a\le n\lt p^{a+1},$ check whether $p$ divides $\sum_{v_p(k)=a} \frac{L_n}{k}$

Solución:

$L_n$ siempre es divisible por $k_n,$ así que $k_n\lt L_n$ exactamente cuando algún primo $p$ divide tanto a $L_n$ como al numerador $N=\sum_{k=1}^n \tfrac{L_n}{k}$ (es decir, se cancela un primo).

Para un primo $p$ con potencia máxima $p^a\le n,$ solo los términos con $v_p(k)=a$ mantienen a $p$ fuera de $\frac{L_n}{k};$ todos los demás son divisibles entre $p.$ Por tanto, $p$ se cancela si y solo si $\sum_{v_p(k)=a}\tfrac{L_n}{k}\equiv0\pmod p.$

Aplicando esta prueba recursivamente con $H_n=H_{n-1}+\frac{1}{n}$ , obtenemos $k_n=L_n$ para $1\le n\le5,$ $k_n=\frac{L_n}{3}$ para $6\le n\le8,$ y de nuevo $k_n=L_n$ para $9\le n\le17.$ Finalmente, las razones $\frac{L_n}{k_n}$ para $n=18,19,20,21,22$ son $3,3,15,45,45,$ respectivamente. Así, la cancelación ocurre precisamente para $n=6,7,8,18,19,20,21,22,$ que son $8$ valores.

Por lo tanto, la respuesta correcta es D.

$L_n$ is always divisible by $k_n,$ so $k_n\lt L_n$ exactly when some prime $p$ divides both $L_n$ and the numerator $N=\sum_{k=1}^n \tfrac{L_n}{k}$ (i.e. a prime cancels).

For a prime $p$ with maximal power $p^a\le n,$ only the terms with $v_p(k)=a$ keep $p$ out of $\frac{L_n}{k};$ all others are divisible by $p.$ So $p$ cancels iff $\sum_{v_p(k)=a}\tfrac{L_n}{k}\equiv0\pmod p.$

Applying this test recursively with $H_n=H_{n-1}+\frac{1}{n}$ gives $k_n=L_n$ for $1\le n\le5,$ $k_n=\frac{L_n}{3}$ for $6\le n\le8,$ and $k_n=L_n$ again for $9\le n\le17.$ Finally, the ratios $\frac{L_n}{k_n}$ for $n=18,19,20,21,22$ are $3,3,15,45,45,$ respectively. Thus cancellation occurs precisely for $n=6,7,8,18,19,20,21,22,$ which is $8$ values.

Thus, the correct answer is D.

2022 AMC 12A Problema 23

Respuesta: D

Nivel de dificultad: 2520

Pista pequeña:

Pista grande:

Solución:

El Problema 23 en otros años