책 이야기

A를 잔여 특성 p를 갖는 근을 적분하는(radically integral) 적분된 로컬 필드를 가로지르는 아핀 평면(affine plane)이라 하자.

정규화 된 하르 척도(Haar measure)를 사용하여 A의 개방형 선 부분을 U라 (고려)한다.

U를 A에 직교 커널로 임베딩하는 자코비안(Jacobian)의 최대 가능한 판별식으로 f(m,p)를 정의한다.

f(20230401,57)을 구하시오. 굵은 글씨로 표현된 단어의 첫 글자를 연결하여 답하시오.

--------------------------------------------------------------------------

수학 배경이 없으면 알지도 못하는 단어들이 많이 나오는 문제여서 보류했다가 나중에 풀어보는데, 앞에서 나온 어려운 문제는 이해할 필요가 없고(문제를 한글로 바꾸는 것도 매끄럽게 못할 지경이다) 마지막 줄만 읽어보면 되는 것이었다.

즉, 영어로 된 문제에서 굵은 글씨로 표현된 단어의 첫 글자를 연결해서 답을 하면 된다. 답이 3단어여서 띄어쓰기, 기호 추가 등을 통해 제대로 된 단어를 만들었는데 그럴 필요 없이 그냥 글자를 쭉 연결해서 1개 단어 형태로 답하면 된다.

제목은 대단한 제안이지만 쉬어가기 문제였다.

항아리에 일곱 가지 무지개 색의 공이 각각 10개씩, 총 70개의 공이 항아리에 있다.

랜덤하게 20개의 공을 선택할 경우 몇 가지의 색이 있겠는가?

소숫점 9자리까지 답을 구하시오(a.bcdefghij형태).

--------------------------------------------------------------------------

처음에는 조합(combination)을 이용해서 나오는 각 경우의 수에 대한 색상 종류를 구해서 전체 평균을 구하는 형태로 접근했는데, 가능한 조합인 ₇₀C₂₀의 값이 161,884,603,662,658,000이어서 코딩을 정확하게 한 것은 자신있지만 시간 내에 답을 구하리라는 장담을 할 수 없는 상황이었다.

그래서 다른 형태의 접근이 필요한 상황이었는데, 구글의 도움을 받아 해결할 수 있었다. 특정 색이 있지 않을 확률은 70개 중 60개에서 20개의 공을 꺼내는 경우이므로(₆₀C₂₀/₇₀C₂₀), 특정 색이 있을 확률은 정반대가(1-₆₀C₂₀/₇₀C₂₀) 되며, 7개 공 각각에 대해 구하면(7*(1-₆₀C₂₀/₇₀C₂₀)) 된다.

이렇게 접근하는 논리를 생각해 내는 것이 쉽지 않은 문제이지, 이 논리를 구현하는 것은 정말 간단하다.

이차원 평면에 다음 랜덤 숫자 생성기를 이용하여 좌표의 배열인 P_n을 생성하자:
S₀=290797
S_n+1=S_n² mod 50515093

P_n=(S_2n,S_2n+1)

P₀,⋯,P_k-1 중 임의의 (서로 다른) 두 좌표의 최단 거리를 d(k)라고 하면, d(14)=546446.466846479이다.

소숫점 9자리까지 나오도록 반올림하여  d(2000000)을 구하시오.

--------------------------------------------------------------------------

번호가 높은 문제여서 해결한 사람이 많지 않지만, 5% 난이도 문제여서 그렇게까지 까다롭지는 않다.

초기값과 값을 구하는 공식, 해당 값을 이용한 좌표를 구하는 공식이 있으므로 요구하는 대로 값을 계산하면 된다.

다만, 예시를 보고 정확하게 프로그램을 작성하지 않아 한가지 실수가 있었는데, mod함수를 사용해서 연속된 두 좌표의 거리 중 가장 짧은 것을 계산한 것이었다. n개 좌표가 있으면 n-1번 계산했는데, 하필이면 예시가 12번째, 13번째 사이가 최단거리인 경우여서 잘못된 프로그램으로도 예시의 답이 나와서 잘못된 부분을 찾는데 애먹었다.

하지만, 곰곰히 생각해 보면, 문제에서는 임의의 두 좌표에 대한 거리를 묻고 있으므로 생성가능한 모든 조합에 대해 거리를 계산해야 되어서 시간이 매우 많이 필요하다. 복잡도가 O(n)에서 O(n²)이 되면서 시간이 기하급수로 늘어나는 문제가 있었다.

몇시간이 걸려도 해결되지 않아 코드를 일부 개선해봤지만 시간이 더 걸리는 등 알고리즘에 대한 근본적인 해결책이 필요했다. 관련 내용을 검색해보다 복잡도를 낮출 아이디어를 구했다. 2백만개의 좌표가 mod 함수에 의해 구해져서 들쑥날쑥이어서 모든 좌표 간의 거리를 계산했는데, 원점을 기준으로 정렬하면 앞뒤 좌표간의 거리만 계산해도 해결 가능하게 되어 복잡도가 줄어든다.

전체 실행시간을 보면, Pn 좌표를 생성하는데 3.6초, 원점 기준으로 정렬하는데 6초, 좌표 간 거리를 계산하는데 10초가 걸려 20초 만에 답을 구할 수 있었다.

169와 961은 모두 소수의 제곱이다. 169를 반대로 하면 961이 된다.

다음 조건을 만족하면 reversible prime square(가역 소수 제곱)이라 부른다:

1. 회문(palindrome)이 아니며,
2. 소수의 제곱이며,
3. 반대로 한 것도 소수의 제곱이다.

169와 961은 회문이 아니며, 소수의 제곱을 반대로 한 것이다.

처음 50개 reversible prime square의 합계를 구하시오.

--------------------------------------------------------------------------

프로그램은 어렵지 않게 구성 가능한데, reversible prime square를 만족하는 숫자를 50개 찾는 것이 쉽지 않았다.

50개가 나올때까지 매번 소수를 추가로 만드는 경우 시간이 많이 소요될 것으로 보여서, 일정한 갯수의 소수와 소수의 제곱수 리스트를 먼저 만들어 놓고, 회문이 아니고, 순서를 반대로 한 것도 소수의 제곱수 리스트에 있는 것들을 따로 모으도록 구현했다.

100자리 중 2개, 1000자리 중 2개 등 생각보다 위 조건을 만족하는 숫자가 많이 나오지 않아서, 처음 소수를 만드는 갯수를 계속 키워가며 구해야 했다. 천만의 제곱까지 구해도 50개가 되지 않는다.

문제에서 요구한 조건을 만족하는 reversible prime square가 모두 홀수 자릿수의 숫자인 것은 의아했다. 확실한 이유가 생각되면 짝수 자릿수의 prime square는 검증과정을 생략하도록 해서 성능을 높을 수도 있을 것 같은데, 짝수 자릿수의 숫자가 없는 이유가 명확하게 떠오르지는 않아서 일단 모든 숫자를 대상으로 검증하게 했다.

일단 답은 구했지만 시간이 많이 걸렸다. 검색 끝에 찾은 몇가지 추가 조건은, △끝자리에 올 수 있는 수가 홀수이며 이 중 5의 배수인 5 제외, 1, 3, 7, 9의 제곱수는 1, 9이므로, 첫자리와 끝자리는 1, 9만 올 수 있으며, △첫자리에 1,9만 올 수 있으므로 제곱근은 1,3이 되고 이 경우 3자리 제곱은 5자리, 4자리 제곱은 7자리와 같이 홀수 자릿수로만 나오게 된다. 앞에서 얘기한 홀수 자릿수로만 reversible prime square가 나오는 이유를 알게 되었다.

그리고, 처음에는 소수의 제곱수 목록을 구해서(조건2) 그것을 대상으로 회문과 반대수를 구했는데(조건1,3), 제곱수를 구할 때 추가로 발견한 2가지 조건과 회문까지 판별해서 목록을 만들고(조건1,2), 반대수가 제곱수인 소수이면 정답 목록에 추가하는 방식으로 바꿔서 검증대상을 줄여봤다.

추가로 발견한 2가지 조건으로 검증대상이 500만개 이상에서 40만개 이하로 줄어 실행시간도 많이 개선되었지만, 검증대상 거의 마지막에 가서야 50개를 찾을 수 있어 실행시간은 여전히 필요했다.

작아지지 않는 정수의 수열인 a_n은 다음 과정을 통해 양의 실수 θ에서 만들어 낼 수 있다.

    b₁=θ

    b_n=└b_n-1┘(b_n-1-└_bn-1┘+1) , n>=2일 때

    a_n=└b_n┘

└ ┘은 버림을 나타낸다.

예를 들어, θ=2.956938891377988...는 피보나치 수열(2, 3, 5, 8, 13, 21, 34, 55, 89, ...)를 생성한다.

양의 정수의 수열인 a_n을 연결하면, τ로 표기하는 a₁에서 시작해서 소숫점 아래의 연속된 요소를 결합한 a₁.a₂a₃a₄...모양의 실수가 된다.

예를 들어, θ=2.956938891377988...에서 나오는 피보나치 순열을 연결하면 τ=2.3581321345589...가 되며, θ 값에 대해 θ와 τ는 다르다.

a₁=2에서 시작해서 수열을 결합했을 때 τ=θ가 되는 유일한 값 θ를 찾으시오. 답안은 반올림하여 소숫점 24자리까지 구하시오.

--------------------------------------------------------------------------

처음에는 고민을 많이 하고 접근했는데, 생각보다 어렵지 않게 해결 가능했다.

처음에는 θ=2로 시작해서, 공식을 소숫점 25자리까지 반복 적용해서 나온 숫자(τ)를 다시 θ로 설정하는 작업을 τ=θ가 나올때까지 반복하면 되는데 몇 번 반복하지 않고 답을 구할 수 있었다.