Question

Para enteros positivos

N

y

k,

se dice que

N

es $k$ -nice si existe un entero positivo

a

tal que

a^k

tiene exactamente

N

divisores positivos. Halla el número de enteros positivos menores que

1000

que no son ni

7

-nice ni

8

-nice.

For positive integers

N

and

k,

define

N

to be $k$ -nice if there exists a positive integer

a

such that

a^k

has exactly

N

positive divisors. Find the number of positive integers less than

1000

that are neither

7

-nice nor

8

-nice.

Respuesta

Respuesta: 749

Conceptos:conteo de factores aritmética modular inclusión-exclusión

Nivel de dificultad: 2990

Pista pequeña:

Si

a = p_1^{m_1} \cdots p_t^{m_t},

entonces

a^k

tiene

(km_1 + 1) \cdots (km_t + 1)

divisores, que es

1

más que un múltiplo de

k

If

a = p_1^{m_1} \cdots p_t^{m_t},

then

a^k

has

(km_1 + 1) \cdots (km_t + 1)

divisors, which is

1

more than a multiple of

k

Pista grande:

Todo

N \equiv 1 \pmod{k}

también funciona (toma

a = p^m

). Cuenta los residuos

1

módulo

7

y módulo

8

por debajo de

1000

por inclusión-exclusión.

Every

N \equiv 1 \pmod{k}

works too (take

a = p^m

). Count residues

1

mod

7

and mod

8

below

1000

by inclusion-exclusion.

Solución:

Si

a = p_1^{m_1} \cdots p_t^{m_t},

entonces

a^k

tiene

(km_1 + 1)(km_2 + 1)

\cdots (km_t + 1)

divisores positivos, y cada factor es

\equiv 1 \pmod{k},

así que el producto también. Recíprocamente, si

N = km + 1,

entonces

a = p^m

da

a^k = p^{km}

con exactamente

N

divisores. Así que

N

es

k

-nice exactamente cuando

N \equiv 1 \pmod{k}.

Entre

1, 2, \ldots, 999

hay

143

enteros

\equiv 1 \pmod{7}

(a saber

1, 8, \ldots, 995

) y

125

enteros

\equiv 1 \pmod{8}

(a saber

1, 9, \ldots, 993

). Como

\operatorname{lcm}(7, 8) = 56,

hay

18

enteros

\equiv 1 \pmod{56}

(a saber

1, 57, \ldots, 953

). Por inclusión-exclusión,

143 + 125 - 18 = 250

de ellos son

7

-nice u

8

-nice.

Por tanto

999 - 250 = 749

enteros positivos menores que

1000

no son ninguno de los dos.

If

a = p_1^{m_1} \cdots p_t^{m_t},

then

a^k

has

(km_1 + 1)(km_2 + 1)

\cdots (km_t + 1)

positive divisors, and each factor is

\equiv 1 \pmod{k},

so the product is too. Conversely, if

N = km + 1,

then

a = p^m

gives

a^k = p^{km}

with exactly

N

divisors. So

N

is

k

-nice exactly when

N \equiv 1 \pmod{k}.

Among

1, 2, \ldots, 999

there are

143

integers

\equiv 1 \pmod{7}

(namely

1, 8, \ldots, 995

) and

125

integers

\equiv 1 \pmod{8}

(namely

1, 9, \ldots, 993

). Since

\operatorname{lcm}(7, 8) = 56,

there are

18

integers

\equiv 1 \pmod{56}

(namely

1, 57, \ldots, 953

). By inclusion-exclusion,

143 + 125 - 18 = 250

of them are

7

-nice or

8

-nice.

Hence

999 - 250 = 749

positive integers less than

1000

are neither.

2016 AIME II Problema 11

Respuesta: 749

Nivel de dificultad: 2990

Pista pequeña:

Pista grande:

Solución:

El Problema 11 en otros años