AIME 1995 · 第 8 题

Solution 1

Since $y|x$, $y+1|x+1$, then $\text{gcd}\,(y,x)=y$ (the bars indicate divisibility) and $\text{gcd}\,(y+1,x+1)=y+1$. By the Euclidean algorithm, these can be rewritten respectively as $\text{gcd}\,(y,x-y)=y$ and $\text{gcd}\, (y+1,x-y)=y+1$, which implies that both $y,y+1 | x-y$. Also, as $\text{gcd}\,(y,y+1) = 1$, it follows that $y(y+1)|x-y$. [1]

Thus, for a given value of $y$, we need the number of multiples of $y(y+1)$ from $0$ to $100-y$ (as $x \le 100$, but not including 0 becaue x cannot be equal to y). It follows that there are $\left\lfloor\frac{100-y}{y(y+1)} \right\rfloor$ satisfactory positive integers for all integers $y \le 100$. The answer is

$$\sum_{y=1}^{99} \left\lfloor\frac{100-y}{y(y+1)} \right\rfloor = 49 + 16 + 8 + 4 + 3 + 2 + 1 + 1 + 1 = \boxed{085}.$$ ^ Another way of stating this is to note that if $\frac{x}{y}$ and $\frac{x+1}{y+1}$ are integers, then $\frac{x}{y} - 1 = \frac{x-y}{y}$ and $\frac{x+1}{y+1} - 1 = \frac{x-y}{y+1}$ must be integers. Since $y$ and $y+1$ cannot share common prime factors, it follows that $\frac{x-y}{y(y+1)}$ must also be an integer.

Solution 2

We know that $x \equiv 0 \mod y$ and $x+1 \equiv 0 \mod y+1$.

Write $x$ as $ky$ for some integer $k$. Then, $ky+1 \equiv 0\mod y+1$. We can add $k$ to each side in order to factor out a $y+1$. So, $ky+k+1 \equiv k \mod y+1$ or $k(y+1)+1 \equiv k \mod y+1$. We know that $k(y+1) \equiv 0 \mod y+1$. We finally achieve the congruence $1-k \equiv 0 \mod y+1$.

We can now write $k$ as $(y+1)a+1$. Plugging this back in, if we have a value for $y$, then $x = ky = ((y+1)a+1)y = y(y+1)a+y$. We only have to check values of $y$ when $y(y+1)<100$. This yields the equations $x = 2a+1, 6a+2, 12a+3, 20a+4, 30a+5, 42a+6, 56a+7, 72a+8, 90a+9$.

Finding all possible values of $a$ such that $y, we get$49 + 16 + 8 + 4 + 3 + 2 + 1 + 1 + 1 = \boxed{085}.$

Solution 3 (Rigorous, but straightforward)

We use casework:

For $y=1$, we have $3,5,\cdots ,99$, or $49$ cases.

For $y=2$, we have $8,14,\cdots ,98$, or $16$ cases.

For $y=3$, we have $15,27,\cdots ,99$, or $8$ cases.

For $y=4$, we have $24,44\cdots ,84$, or $4$ cases.

For $y=5$, we have $35,65,95$, or $3$ cases.

For $y=6$, we have $48,90$, or $2$ cases.

For $y=7$, we have $63$, or $1$ case.

For $y=8$, we have $80$, or $1$ case.

For $y=9$, we have $99$, or $1$ case.

Adding, we get our final result of $\boxed{085}.$

Note: In general, all of the solutions for all $y$ are $y+by(y+1)$, for any $b$ such that $y+by(y+1)=x<100$

~SirAppel

Also, note that $n+1$ just starts with $(y+1)^2$, and adds $y(y+1)$ until it is greater than $100$.

~Yiyj1