Problem:
For how many ordered pairs of positive integers (x,y), with y<x≤100, are both yx and y+1x+1 integers?
Solution:
Suppose that y+1x+1=m holds for some integer m>1, so that
x=my+(m−1)(*)
Because y is a factor of x, it must also be a factor of m−1. Hence there is a positive integer k with m−1=ky. Substitute m=ky+1 into (*) to find that
x=(ky+1)y+ky=ky(y+1)+y
It follows from x≤100 that
k≤y(y+1)100−y
There are ⌊y(y+1)100−y⌋ positive integers k that satisfy this inequality. For each positive integer y, equation shows that there is a one-one correspondence between such k and ordered pairs (x,y) with the desired property. Hence the number of pairs is
y=1∑99⌊y(y+1)100−y⌋=y=1∑9⌊y(y+1)100−y⌋=⌊299⌋+⌊698⌋+⌊1297⌋+⌊2096⌋+⌊3095⌋+⌊4294⌋+⌊5693⌋+⌊7292⌋+⌊9091⌋=49+16+8+4+3+2+1+1+1=85.
The problems on this page are the property of the MAA's American Mathematics Competitions