1193 - 분수찾기

1/1

1/2 2/1

3/1 2/2 1/3 ...

여기서 구간을 나눌 수 있다. 구간을 군으로 생각하면 아래와 같다.

n군은 n/1 (또는 1/n)부터 시작하여 1/n (또는 n/1)로 끝난다. (n군의 구간 길이는 n)

설명하기 앞서,

우리는 여기서 어떤 규칙을 발견할 수 있다.

위에서부터 n번째 군의 각 분수의 분자/분모 합은 모두 n+1 로 일정하다.

(예를 들면 3/1과 2/2과 1/3은 모두 3+1=2+2=1+3 = 4 이다.)

이 부분은 나중에 다시 언급하겠다.

군수열의 군을 An 이라 할 때 An = n * (n+1) / 2 이다.

주어진 X가 속하는 군은 An ≤ X < An+1 이므로 An ≤ X 만 구하면 된다.

n에 대한 방정식으로 바꿔말하면

n * (n+1) / 2 ≤ X

n2 + n - 2X ≤ 0 이다. n은 항상 양수이고, 이를 근의 공식으로 구하면

n = ( -1 + √(1 + 8X) ) / 2

여기서 n은 0부터 시작했으므로 X 는 " (n + 1) / 1" 의 형태(또는 반대)로 시작하는 분수이다.

(즉, 여기서 n은 군을 의미하고, 일종의 경계선이라 생각하면 편하다.)

이제 우리는 A_n 을 알고 n을 알기에 답을 충분히 유추할 수 있다.
(예를 들면, 7 의 경우에는 3군(n)에 속하고 (3/1 부터 시작하는..) 3군의 경계는 6 (A_n )이다.)

그럼 이제 이전에 발견했던 규칙(n군의 각 분수는 분자/분모 합이 일정하다.)을 이용하면 분자/분모를 유추할 수 있다.

PS. (또는 ~~) 의 표현은 n 이 짝수라면 1/n, 홀수라면 n/1으로 생각하면 된다.