[이산구조] 유리수의 집합에서 순서에 따른 값 구하기

안녕하세요, Einere입니다.

오늘은 셀 수 있는 집합인 유리수 집합에서,

순서에 따른 해당 유리수의 값을 구하는 식을 유도해보도록 하겠습니다.

즉 n번째 유리수의 값을 구하는 공식을 구하는 것입니다.

우선 유리수는 a/b꼴로 나타낼 수 있습니다.

따라서 위와 같이 a와 b의 값에 따른 표를 만들 수 있습니다.

그리고 이 수들을 대각선 방향으로 그룹을 지어 줍니다.

위와 같이 그룹을 지었을때,

1번 그룹은 1/1, 2번 그룹은 1/2 2/1, 3번 그룹은 1/3 2/2 3/1 순서대로 원소를 가지고 있다고 할 수 있습니다.

여기서 순서가 중요한 이유는 n번째 숫자가 몇번째 그룹에서 몇번째 순서(index)인지 알아야 하기 때문입니다.

위와 같이 그룹을 지었다면 1번째 숫자는 1번 그룹의 1번인 1/1, 8번째 숫자는 4번째 그룹의 2번인 2/3이 됩니다.

여기서 숫자들 사이의 관계를 보면, 그룹 내에서 순번이 증가할수록 분자는 커지고 분모는 작아지는것을 알 수 있습니다.

그리고 각 그룹의 초항들의 값을 보면 , 분자인 a는 1로 고정이며 분모인 b의 값은 1 2 3 4... 와 같이 1씩 증가합니다.

즉 그룹의 초항의 값은 1/b라고 할 수 있습니다.

그룹의 원소의 개수도 1개 2개 3개 ... 이런 식으로 1씩 증가하며, 이를 통해 x번째 그룹의 원소는 x개라고 할 수 있습니다.

그리고 n번째 숫자와 x번째 그룹의 관계를 보자면, 각 그룹의 초항은 1번째, 2번째, 4번째, 7번째... 숫자임을 알 수 있습니다.

여기서 수열을 배우신 분이라면 뭔가 느낌이 오실 것입니다.

바로 이 관계는 각 항의 차이(공차)가 등차수열을 이루는 계차수열이라는 것 입니다.

n : 1   2   4   7   11

    1   2   3   4

위와 같은 관계를 가집니다.

여기서 공차를 보시면 그룹의 순서(index)와 같은 값을 가지는 것을 알 수 있습니다.

1번그룹의 초항은 1번째 값, 2번 그룹의 초항은 2번째 값, 3번 그룹의 초항은 4번째 값, 4번 그룹의초항은 7번째 값... 이런 식입니다.

즉 n과 x의 관계가 계차수열을 이룹니다.

이제 이 성질들을 이용해서 n이 주어졌을때 a/b를 구하는 공식을 유도하겠습니다.

우선 n번째 숫자를 N이라고 합니다.

그리고 을 숫자 N의 순번이라고 합니다.

그룹의 순서를 x라고 합니다.

x그룹의 초항의 분모값을 라고 합니다.

이제 각 그룹의 초항인 의 순서인 와 x의 관계가 계차수열이고, 계차수열의 일반항은 입니다.

이므로 가 됩니다.

N은 x그룹의 원소이므로, x는 n이하의 최대값이 됩니다.

즉, 이 됩니다.

에 의해 이 됩니다.

근의 공식에 의해 이 되며

x는 n 이하의 최대값이므로 가 됩니다.

이제 x를 구했으니 x그룹의 초항은 입니다.

그리고 N의 그룹 내 순번은 입니다. (순번-그룹의 초항의 순번+1)

와 그룹 내 순번의 관계에 의해서 이 됩니다. 

(단 여기서 약분을 하면 안됩니다.)

(또한 마지막 항에서 뜬금없이 분모분자를 2로 나누어준 이유는, 2로 나누어주어야 올바른 값이 되기 때문입니다.)

즉 n을 알면 x를 알 수 있고, 이 둘을 알면 N의 값인 a/b를 알 수 있습니다.