[C/C++] 프로젝트 오일러 #100 Arranged Probability(수학)

프로젝트 오일러 100번째 문제네요.

 

Project Euler #100: Arranged Probability 문제는 확률과 이항 계수를 기반으로 한 수학적 사고를 요구하는 문제입니다. 이 문제의 주요 목표는 특수한 조건을 만족하는 정수 쌍을 찾는 것입니다. 문제를 이해하기 위해 배경과 개념을 먼저 살펴보겠습니다.

문제는 다음과 같이 설정됩니다. 특정 “파란색”과 “총 디스크”의 개수가 주어졌을 때, 한 번 무작위로 디스크를 두 개 뽑는 경우, 둘 다 파란색일 확률이 정확히 1/2가 되는 조건을 만족하도록 하는 디스크의 배치를 찾는 것이 목적입니다.

우선 기본적인 수식으로 표현해 봅시다.
• 파란색 디스크의 개수를 b, 총 디스크의 개수를 n이라고 하겠습니다.
• 두 개의 디스크를 뽑는 확률에서 둘 다 파란색일 확률은 다음과 같습니다:
\[ \frac{b(b-1)}{n(n-1)} = \frac{1}{2} \]

이 식을 정리하면 다음 관계식으로 변환됩니다:
\[ 2b(b-1) = n(n-1) \]

이제 우리는 이 관계를 만족하는 b와 n을 찾아야 합니다. 단, n은 b보다 커야 하며, \( n > 10^{12} \) 인 최소의 값을 찾아야 합니다.

이 문제의 핵심은 정수해를 찾는 것입니다. 두 개의 이차항으로 이루어진 식을 풀어야 하므로, 일반적인 방법으로는 매우 어려운 문제입니다. 따라서 이 문제는 펠 방정식과 밀접한 관련이 있습니다. 펠 방정식은 다음과 같은 형태를 갖습니다:

 

\[ x^2 - Dy^2 = 1 \]

우리의 문제에서는 약간 변형된 형태의 펠 방정식으로 변환이 가능합니다. 여기서부터 수학적 도구와 알고리즘을 활용해 해를 찾아야 합니다.

간단한 예를 들어봅시다. \( n = 21 \) 이고 \( b = 15 \)일 때를 가정합니다:
• 총 디스크는 21개이고, 그중 파란색 디스크는 15개입니다.
• 둘 다 파란색일 확률을 계산하면:
\[ \frac{15 \times 14}{21 \times 20} = \frac{1}{2} \]

이 조건이 성립하므로, \(  (b, n) = (15, 21)  \) 은 하나의 유효한 해입니다.

이제 더 큰 n 을 탐색하며 이 관계를 만족하는 정수 쌍을 찾아야 합니다. \( n > 10^{12} \) 인 해를 찾으려면 위 식의 정수해를 효율적으로 탐색해야 합니다.

 

project euler #100

제가 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #100 - Arranged Probability
//        - by Aubrey Choi
//        - created at 2015-04-03
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

int main()
{
    for( uint64_t m = 1000001 ; ; m += 2 )
    {
        for( uint64_t n = (1000000000000LL/m/2)*2+1 ; n < m ; n += 2 )
        {
            uint64_t s = m*n;
            uint64_t t = (m*m-n*n)/2;
            if( t < 1000000000000LL ) break;
            if( s-t == 1 )
            {
                uint64_t r = (m*m+n*n+2)/4;
                printf("ans = %ju %ju %ju\n", r, s, t);
                return 0;
            }
        }
    }
}

 

이 코드와 관련된 알고리즘 및 수학적 기법은 펠 방정식(Pell’s equation)과 정수론에 기반을 둡니다. 문제는 특정 조건을 만족하는 정수해를 찾는 것으로, 코드에서는 효율적으로 m과 n을 반복 탐색하면서 해를 찾아냅니다.

사용된 알고리즘 및 수학적 기법

1. 펠 방정식 변형

문제의 조건을 다시 정리하면, 파란 디스크 개수 b와 총 디스크 개수 n이 다음 방정식을 만족해야 합니다:
\[ 2b(b-1) = n(n-1) \]

이 식은 대칭적이며, 변형을 통해 특정 정수 조건을 만족하는 쌍을 찾는 문제로 바뀝니다. 이 문제는 펠 방정식과 밀접한 관련이 있습니다. 일반적으로 펠 방정식의 해를 점화식으로 확장해 정수해를 구합니다.

코드에서는 (m, n) 쌍을 사용해 \( n > 10^{12} \) 인 최소 n을 찾아가는 과정입니다. 여기서 m과 n은 정수론적 구조를 만족하도록 선택됩니다.

2. 정수론적 탐색

코드는 m과 n을 두 개의 홀수로 설정하고, 이 두 값의 조합으로 문제를 해결합니다. 이 선택은 다음 수학적 관계에서 비롯됩니다:
• m과 n의 조합을 통해 \(  s = m \cdot n \) 및 \(  t = (m^2 - n^2)/2 \) 를 정의.
• 이 관계는 m, n을 선택함으로써 펠 방정식의 형태로부터 새로운 해를 생성합니다.
• 조건 \(  s - t = 1  \) 을 만족하면, 이는 \(  r = (m^2 + n^2 + 2) / 4  \) 로 변환되어 총 디스크 n을 계산합니다.

코드 분석

1. 외부 루프 - m 증가 탐색

for( uint64_t m = 1000001 ; ; m += 2 )

• m은 탐색을 시작하는 변수로, 1000001에서 시작하며 홀수로 설정됩니다. 펠 방정식과 관련된 해를 찾기 위해 m과 n이 모두 홀수로 제한됩니다.

2. 내부 루프 - n 감소 탐색

for( uint64_t n = (1000000000000LL/m/2)*2+1 ; n < m ; n += 2 )

• n 은 m 보다 작은 홀수입니다.
• 초기값: 
\[ n = \left\lfloor \frac{10^{12}}{m \cdot 2} \right\rfloor \cdot 2 + 1 \]

이는 n을 효율적으로 탐색할 수 있도록 최적화한 초기값입니다.

3. 조건 계산

uint64_t s = m * n;
uint64_t t = (m * m - n * n) / 2;
if (t < 1000000000000LL) break;
if (s - t == 1)

• \(  s = m \cdot n  \), \(  t = (m^2 - n^2)/2 \) 를 계산합니다.
• t 가 너무 작으면 더 이상의 계산이 필요 없으므로 내부 루프를 종료합니다.
• \( s - t = 1 \) : 문제의 주요 조건을 확인합니다.

4. 해를 출력

uint64_t r = (m * m + n * n + 2) / 4;
printf("ans = %ju %ju %ju\n", r, s, t);
return 0;

이 코드는 펠 방정식에서 유도된 관계식을 기반으로 정수론적 점화식을 사용해 해를 탐색합니다. m 과 n 의 조합을 효율적으로 설정해 불필요한 계산을 최소화하며, \( n > 10^{12} \) 에 도달할 때까지 계산을 진행합니다.