[작성자:] snowall

문제 : 모서리 길이가 모두 1인 정사면체와 정팔면체가 있다. 꼭지점과 모서리를 맞추어서 정사면체의 한 면과 정팔면체의 한 면을 붙인다면, 서로 맞붙게 되는 모서리와 꼭지점은 그대로 남아 있는가? 또는 평면이 되기 때문에 사라져 버리는가?

해답/증명/해설은 나중에…

여백보다는 시간이 없어서.

앞으로 읽으나 뒤로 읽으나 같은 숫자인지 판별하는 코드다.

int isPal(int i){

int a,b,c,d,e,f;

a=i%10;

b=(i/10)%10;

c=(i/100)%10;

d=(i/1000)%10;

e=(i/10000)%10;

f=(i/100000)%10;

printf(“%d,%d,%d,%d,%d,%d,%d\n”,i,f,e,d,c,b,a);

if((f==0 && a==e && b==d)||(f==a && b==e && c==d)){

return YES;

}

else{

return NO;

}

}

오일러 프로젝트, 재미있다.

400만 이하의 피보나치 수열 중, 짝수들의 합을 모두 구하라.

1, 2, 3, 5, 8, 13,…

나의 풀이는 접어두었다. 이거 보면 재미가 없어지니까 가급적이면 보지 않고 풀기를 바란다.


http://projecteuler.net/index.php?section=problems&id=2

more..

*전 세계에서 248번째로 풀었다. -_-;

다 풀고나서 내 정답을 확인하기를 바란다. 정답은 일단 가장 끝에다가 가려둔다.

오래간만에 수학 문제를 발견했다.

문제의 원문은

http://projecteuler.net/index.php?section=problems&id=207

에서 찾을 수 있다.

이 문제를 풀기 위해서 고율님의 아이디어 대로 $X=2^t$ 로 치환한다.

그럼 주어진 식은 $X^2-X-k=0$이라는 2차 방정식이 된다. 이 2차 방정식을 풀어보자.

$X=\frac{1}{2} \pm \frac{1}{2}\sqrt{1+4k}$

이 된다.

다시 X를 원래대로 치환하면

$2^t=\frac{1}{2} \pm \frac{1}{2}\sqrt{1+4k}$

이 된다. 그런데 $2^t$는 양수밖에 없으므로

$2^t=\frac{1}{2} + \frac{1}{2}\sqrt{1+4k}$

이 될 것이다. $2^t$가 정수가 되어야 한다는 조건이 있으므로, 우변도 정수가 되어야 한다. 근데 정수가 아닌 유리수인 1/2가 있기 때문에 좀 곤란해 보인다. 이 부분을 증명하고 넘어가자. 일단 1+4k가 어떤 정수의 제곱수가 아니라고 하자. 그렇다면 우변은 무리수가 되므로, 반드시 1+4k는 어떤 정수의 제곱수가 되어야만 한다. 또한, 1+4k가 어떤 정수의 제곱수라면, 1+4k는 홀수이므로 그 제곱근 역시 홀수이다. 홀수의 절반에 1/2을 더하면 정수가 나온다. 따라서 1+4k가 제곱수이기만 하면 된다. 즉, t가 파티션이 될 조건은 1+4k가 제곱수가 될 조건과 같다. 그럼 m보다 작은 k에 대해서 1+4k가 제곱수인지 조사하면 된다. 1+4k의 제곱근을 2n+1이라고 가정하자. 그럼 $1+4k=4n^2+4n+1$ 이므로 $k=n(n+1)$ 이 된다. 이 말은, $k=n(n+1)$조건을 만족하기만 하면 t는 파티션이 된다는 뜻이다. 그럼 m보다 작은 n(n+1)인 숫자들을 찾아내면 된다.

이제, t가 양의 정수(앞으로는 그냥 정수라고 하겠다)인 경우를 생각해 보자.

$2^t=\frac{1}{2} + \frac{1}{2}\sqrt{1+4k}$

여기에 k=n(n+1)을 대입해 보자.

$2^t = 1+ 2n+1 = 2(n+1)$

이렇게 식이 변했다. 앞에 있는 2를 떼어 내고도 t가 정수가 되기 위해서는 n+1 또한 2의 거듭제곱수이면 충분하다.

따라서 t가 perfect partition이 되기 위해서는 어떤 양의 정수 q에 대해서 $n=2^q-1$ 형태면 충분하다.

자, 이제 m에 대해 t가 정수가 되는 k가 몇개나 되는지 따져볼 차례다.

k=n(n+1)이었고, $n=2^q-1$ 형태였으므로, 이걸 다시 k에 대입하면

$k=4^q-2^q$

가 된다.

이제, q에 1부터 하나씩 대입해 가면서 문제에서 주어진 m이 k보다 작은 경우가 몇개나 되는지 보면 된다.

따라서, 다음의 부등식을 만족하는 최대의 q값을 구하면 된다.

$4^q -2^q \leq m$

정리하자면 다음과 같다.

1.n(n+1)이 m보다 작게 되는 양의 정수 n이 몇개인지 조사한다. 이 숫자를 A(m)라고 정의한다.

2.그러한 양의 정수 n중에서 n+1이 2의 거듭제곱수가 되는 경우가 몇개인지 조사한다. 이 숫자를 B(m)라고 한다.

3. P(m)=A(m)/B(m) 이다.

그런데, 반대로 생각해 보자. 어차피 k는 n(n+1)이 되기만 하면 되므로, $n=2^q-1$을 계산해서 q를 1씩 더하고, 그때마다 n이 어떻게 커지는지를 살펴보면 되지 않을까?

어쨌거나 이 문제를 풀게 된 알고리즘은 다음과 같다.

1. n을 계속해서 1씩 키워나간다.

2. n+1이 2의 거듭제곱수가 되면 q를 1만큼 증가시킨다.

3. q/n<1/12345가 되면 멈추고 n*(n+1)을 출력한다.
출력된 값이 m의 최소값이다.

덧붙임.

문제 해결하는 코드를 C로 짰는데 32비트 머신에서 쓸 수 있는 숫자의 자릿수가 너무 작아서 (답이 4294967296을 넘는 것 같음) 풀지 못하였다.

이건 뭐 페르마의 대정리도 아니고…-_-;;;;

결론적으로.

답이 32비트 머신에서 쓸 수 있는 숫자(4294967296)보다 많은 것은 사실이었다. 그래서 마지막 계산은 공학용 계산기를 썼다.

정답

정답보기