다음 수식에서 x, y, n은 양의 정수이다.
1/x+1/y=1/n
n이 4일 때, 다음의 3개 답안만 있다:
1/5+1/20=1/4
1/6+1/12=1/4
1/8+1/8=1/4
서로 다른 해결책이 1,000개를 넘는 가장 작은 값 n은 얼마인가?
주의: 이 문제는 문제 110의 쉬운 버전이므로, 이 문제를 먼저 해결하기를 강력하게 권고함
--------------------------------------------------------------------------
다른 분이 이야기한 아이디어(양변에 nxy를 곱해서 분모 없애기)를 참고해서 해결할 수 있었다.
문제에 나오는 공식의 분모를 없애기 위해 간단히 수학을 적용해서 양변에 xyn을 곱하면 ny+nx=xy가 된다. 그리고, 예시를 보면 짐작 가능하겠지만 n이 x, y보다는 작기 때문에 x를 n+a, y를 n+b로 바꾸면 n(n+b)+n(n+a)=(n+a)(n+b)가 된다. 이를 풀면 n2+nb+n2+na=n2+na+nb+ab가 되고 양변을 정리하면 n2=ab가 된다.
이 특성을 이해하고, 예시를 다시 보면 x의 값이 n=4일 때, n보다 1, 2, 4만큼 큰 것을 알 수 있다. 이것이 4의 약수이기 때문에, 솔루션이 1000개를 넘는 것은 약수가 1000개를 넘는 경우와 같은 것으로 이해되었다. 그래서, 먼저 풀었던 243번 문제에서 적용한 소수의 곱을 대상으로 배수로 키워나가면서 약수가 1000개 이상인 경우를 찾는 방법을 적용했는데, 예상과는 달리 오답이었다.
n2=ab를 다시 생각해보니, n의 약수가 아니라 n2의 약수 중 n이하의 값인 것들을 찾으면 되는 것이었다. 예시로 나온 4가 너무 작은 수이면서 2의 배수여서 다양한 경우가 나오지 않아 잘못된 유추를 하게 되었던 것이다.
약수를 구하는 함수를 n제곱을 입력값으로 해서 n이하의 값만 구하도록 바꾸고 나니 빠른 시간 내에 답을 구할 수 있었다.