1995 AIME Problema 8

Question

¿Para cuántos pares ordenados de enteros positivos

(x,y),

con

y<x\leq100,

son enteros tanto

\frac{x}{y}

como

\frac{x+1}{y+1}

?

For how many ordered pairs of positive integers

(x,y),

with

y<x\leq100,

are both

\frac{x}{y}

and

\frac{x+1}{y+1}

integers?

Respuesta

Respuesta: 85

Conceptos:divisibilidad funciones piso y techo conteo de pares

Nivel de dificultad: 2060

Pista pequeña:

Escribe

x=ay

y reduce

x+1

módulo

y+1

Write

x=ay

and reduce

x+1

modulo

y+1

Pista grande:

El cociente

a

debe tener la forma

1+t(y+1)

; cuenta los valores positivos posibles de

t

The quotient

a

must have the form

1+t(y+1)

; count the possible positive values of

t

Solución:

Escribe

x=ay.

Módulo

y+1,

tenemos

y\equiv-1,

así que

x+1

es divisible por

y+1

exactamente cuando

a\equiv1\pmod {y+1}.

Como

x>y,

escribe

a=1+t(y+1)

con

t\geq1.

La cota

x\leq100

se convierte en

t\leq\left\lfloor\frac{100-y}{y(y+1)}\right\rfloor.

Solo contribuyen

1\leq y\leq9,

lo que da

\begin{aligned}49+16+8&+4+3\\&+2+1+1+1\\&=85.\end{aligned}

Write

x=ay.

Modulo

y+1,

we have

y\equiv-1,

so

x+1

is divisible by

y+1

exactly when

a\equiv1\pmod {y+1}.

Since

x>y,

write

a=1+t(y+1)

with

t\geq1.

The bound

x\leq100

becomes

t\leq\left\lfloor\frac{100-y}{y(y+1)}\right\rfloor.

Only

1\leq y\leq9

contribute, giving

\begin{aligned}49+16+8&+4+3\\&+2+1+1+1\\&=85.\end{aligned}