Problem 101

출제 일시 : 2013-01-29 09:27:50

어떤 수열의 첫 k개의 항이 주어졌다고 해도, 그 다음 항을 확신할 수는 없습니다. k개의 항을 만족하는 다항식은 그야말로 무한정 만들어낼 수 있기 때문입니다.

예를 들어, 세제곱 수의 수열을 생각해 봅시다.

un = n3 : 1, 8, 27, 64, 125, 216...

여기서 앞의 숫자 두 항만을 알고 있다고 가정합시다. "단순한 게 장땡"이라는 원칙에 따라, 우리는 이 수열이 공차가 7인 등차수열이라고 가정하고 다음 항이 15일 것이라고 추측할 수 있습니다. 첫 3개항이 주어지더라도, 2차 다항식으로 오해될 여지가 있습니다.

처음 k개의 항이 주어지고, 이 수열을 바탕으로 만들 수 있는 최소차 다항식으로 구할 수 있는 n번째 항을 OP(k, n)이라고 합시다. n≤k일 때는 무조건 정답이 나올 수밖에 없습니다. 하지만 OP(k, k+1)은 첫 오답(first incorrect term : 이하 FIT이라고 통칭합니다)이 될 가능성이 있습니다. 이런 경우 OP(k, k+1)은 bad OP(BOP)라고 부르기로 합니다.

위 정의대로 한다면, 수열의 첫 항만이 주어진 경우에는 OP(1, n) =u1이라고 가정하게 될 것입니다.

그러므로 우리는 다음과 같은 순서로 OP를 구할 수 있습니다.

OP(1, n) = 11, 1, 1, 1, ...
OP(2, n) = 7n61, 8, 15, ...
OP(3, n) = 6n211n+6 1, 8, 27, 58, ...
OP(4, n) = n31, 8, 27, 64, 125, ...

k≥4일 때 BOP가 존재하지 않으리라는 사실은 명백합니다.

BOP에서 나온 FIT을 모두 더하면(예제에서 빨간색으로 표시해 두었습니다), 그 값은 1 + 15 + 58 = 74가 됩니다.

자 그럼 다음 10차 다항함수를 잘 보세요.

un = 1 n + n2 n3 + n4 n5 + n6 n7 + n8 n9 + n10

이 함수의 BOP에서 나온 FIT의 총합은 얼마입니까?



로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.