[월:] 2008년 09월

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

문제의 원문은

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)보다 많은 것은 사실이었다. 그래서 마지막 계산은 공학용 계산기를 썼다.

정답

정답보기

1. 
   
   
   
   청개구리
   
   
   
   
   
   2008/09/12 00:04
   
   
   
   
   Modify/Delete
   
   
   
   
   Reply
   
   
   

   아 방명록이 여기 있었네요 ^_^; 먼저, 우주에서 자연적으로 발생하는 수많은 충돌과 반응들은 LHC실험과는 조금 다릅니다. 대표적으로 태양에서 발생하는 에너지도 핵융합에서 비롯되는 것이지 입자가 깨진다거나 하지는 않습니다. LHC에서는 입자를 빛의 속도에 근접하게 가속시킨 후 충돌시킵니다. 우주 어느곳에서도 빛의 속도로 날아와서 서로 충돌하는 경우도 없고, 입자가 직접 부‹H힐 확률도 제로입니다. 만약 snowall님의 말씀처럼 우주에서 더 강력한 에너지와 더 높은 빈도로 충돌과 폭발이 일어난다면 LHC실험을 하는 이유가 없어지죠. 우주 어디에서나 쉽게 관찰할 수 있을테니까요. 대부분의 기사에서도 입자들을 서로 빛의 속도로 충돌시켜 ‘빅뱅 직후의 고에너지 상태’를 재현할 수 있다고 말하고 있네요. 빅뱅이 있었는지 없었는지 모르겠지만 과학자들이 그런말을 한다는 것은 최소한 지금 이 우주에는 LHC안의 현상이 일어나지 않는다는 얘기일 겁니다.

먼저 우주에서 자연적으로 발생하는 수많은 충돌과 반응들은 LHC실험과 본질적으로 동일합니다.

현재 우주에 존재하는 상호작용은 4개로 제안되고 있으며, 거의 확인이 되어 절대적으로 믿어도 좋을 만큼 근거가 쌓여 있습니다. 대표적인 예로, 태양에서 발생하는 에너지가 핵융합에서 비롯되어 입자가 깨진다거나 하지는 않는다고 하셨는데, 태양 에너지가 핵융합에서 비롯된 것은 맞지만 입자가 깨지지 않는다는 것은 틀렸습니다. 핵융합에서 발생된 전자와 중성미자들은 다른 입자와 충돌하여 새로운 입자들을 만들어 냅니다. 이것은 LHC에서 일어나는 일보다 에너지 수준이 작긴 하지만 본질적으로 동일한 현상입니다.

또한, 우주에서 입자가 빛의 속도로 날아와서 서로 충돌할 경우도 없고 입자가 직접 부딪칠 확률도 제로라고 하셨는데, 이건 명백하게 틀렸습니다. 우주에서는 아주 많은 입자들이 날아오고 있으며, 그중에는 10^20 eV의 에너지를 가지는 초 고에너지 입자선도 지구로 떨어집니다. 지구로 날아오면 당연히 지구의 대기 입자들과 충돌하며, 실제로 그 효과가 관측됩니다.

20061122.pdf에 액세스하려면 클릭하세요.

의 19번째 페이지를 참고하세요. 또는 구글에서 Extended Air Shower 라는 현상에 대해 검색해 보세요. 덧붙이자면, 10^20eV는 인간이 만들 수 있는 최대 에너지보다 1000만배 강력한 에너지 수준입니다. 만약 LHC 실험 때문에 미시 세계 1개가 멸망했다면 10^20 eV를 갖는 입자의 충돌에 의해 생성된 충격은 미시 세계 1000만개를 멸망시킬 수도 있습니다.

LHC실험을 하는 이유는 우리가 통제 가능한 실험을 하기 위해서 하는 겁니다. 외부 우주에서 날아오는 입자들은 통제할 수가 없기 때문에, 강력하긴 하지만 그냥 목빠지게 기다려야 하는 단점이 있습니다. 하지만 실험장치를 이용하면 그보다는 약하지만 우리 마음대로 실험할 수 있다는 장점 때문에 LHC 실험이 의미가 있습니다.

대부분의 신문 기사는 전혀 과학적이지 않습니다. 빅뱅 직후의 고에너지 상태를 재현하려면 실제로 우주 전체의 에너지를 전부 모아야 할 정도로 많은 에너지가 필요합니다.

어찌되었든, LHC에서 사용되는 에너지 수준보다 훨씬 강력한 에너지 소스가 우주에 존재한다는 것은 분명합니다. 이것은 각종 입자 검출기 실험을 통해서 검증된 부분이므로 믿어도 좋습니다. 의심가신다면 High Energy Cosmic Rays에 대해서 검색해 보시기 바랍니다. LHC 따위는 그냥 장난감 물총으로 봐도 좋을 만큼 강력한 에너지 원은 우주에 널려 있습니다. 그리고 그것들이 각자 자신의 위치에서 사방으로, 무작위로 입자들을 쏘아대는데도 불구하고 이 작은 행성인 지구에는 1년에 수십개씩의 입자들이 쏟아져 내립니다. 그래도 그 초강력 입자가 적다고 하실 겁니까?

1. 
   
   
   
   청개구리
   
   
   
   
   
   2008/09/12 00:17
   
   
   
   
   Modify/Delete
   
   
   
   
   Reply
   
   
   

   그리고 우주는 무한하지만, 동시에 하나로 연결되어있습니다. 대표적으로 양자역학 실험에서 보면 멀리 떨어진 두 입자의 반응이 동일하다는 것을 봐도 알 수 있죠. 미시세계, 거시세계라고 다를 건 없습니다. 스노우올님의 몸은 셀수없을 정도로 많은 입자로 구성되어 있고, 무한한 미시세계가 끝없이 존재합니다. 이러한 무한 우주는 바로 나 자신이기도 합니다. 어떻게 미시세계가 단지 눈에 보이지 않는다고해서 무시할 수 있을까요? 그 미시세계는 스노우올님 자신이기도 하고, LHC안에 갇혀 파괴될 운명의 수천억개의 양성자 안에도 존재하고 있는 것입니다. 쓰고나니까 마치 선문답같네요 -_-;; 별로 아는게 없지만 대략 이런 느낌입니다 =_=;;

미시세계가 파괴되기 위해서는 거시세계가 미시세계에 영향을 미쳐야만 합니다. 명제 형태로 쓴다면, “미시세계가 거시세계에 의해 파괴되었다면, 거시세계는 미시세계에 영향을 주었다”는 참으로 받아들이셔야 합니다. 그런데, 우리가 무언가의 존재를 입증할 때에는, 우리가 어떤 수단을 통해서 그 무언가에게 영향을 줄 수 있어야만 합니다. 가령, 원자핵의 존재를 입증하기 위해서 러더포드는 전자를 금박에 때려보는 실험을 했죠. 그 실험 결과를 분석하여 원자핵의 존재를 입증했습니다. 만약 미시세계가 존재하고 그것이 거시세계에 의해서 영향을 받는다고 하면, 거시세계에서는 반드시 그 미시세계를 관찰할 수 있어야만 합니다. 만약, 관찰할 수 없다면 거시세계는 미시세계에 영향을 줄 수도 없습니다.

가령, 어떤 물질을 관찰할 때, 그냥 만져보거나 바라보기만 하면 우리는 그 물질이 분자로 이루어져 있다는 사실을 모릅니다. 그냥 물질의 연속체로서 관찰될 뿐입니다. 이런식으로 관찰한다면, 분자는 관찰되지 않으며 없는 것이나 마찬가지입니다. 또한, 분자는 우리라 만질 수 있는 세계나 눈으로 관찰하는 세계에 전혀 영향을 주지 않습니다. 하지만 좀 더 강력한 현미경을 사용하고, 분자에 대한 적절한 가설을 세운 후 그것을 검증해 나가다 보면 물질이 사실은 분자라고 하는 작은 알갱이로 이루어져 있다는 것을 알 수 있습니다. 이것은 분자에 영향을 줄 수 있는 실험을 하였기 때문입니다. 이것을 화학이라고 합니다. 화학 실험은 전부 분자에게 영향을 주는 실험으로 구성됩니다. 그럼, 화학에서 쿼크는 존재할까요? 화학에서는 쿼크는 있으나 없으나 관계 없습니다. 화학에서는 분자가 원자로 구성된다는 것 까지만 알고 검증하면 그걸로 끝일 뿐, 그보다 더 미시세계인 쿼크의 존재성은 알 필요가 없습니다. 왜냐하면 화학적 에너지로는 쿼크에 아무런 영향을 줄 수 없기 때문이죠. 반대로, 쿼크 역시 화학 실험에는 아무런 영향을 주지 않습니다.

따라서, 관찰되지 않을만큼 충분히 작은 미시세계가 거시세계의 실험에 의해 파괴될 수 있다는 것은 그 자체로서 논리적인 모순을 발생시킵니다. 미시세계가 거시세계의 실험에 의해 파괴되었다면, 그것은 반드시 관찰되어야만 하기 때문입니다. 반대로, 관찰되지 않을만큼 충분히 작다면, 미시세계는 거시세계의 실험에 의해 결코 파괴될 수가 없습니다.

이러한 것이 존재하는가 아닌가에 대한 논쟁은 빛을 전달하는 매질인 “에테르(Aether)”의 존재성에 관한 실험에 잘 나타납니다. 마이켈슨과 몰리의 실험을 자세히 살펴보면, 빛은 에테르를 필요로 하지 않음을 증명할 수 있습니다. 아인슈타인의 상대성 이론은 결코 에테르의 존재성 자체를 부정한 것이 아닙니다. 다만, 빛의 특징을 전부 설명하는데 있어서 에테르가 단 한번도 등장할 이유가 없고, 따라서 에테르는 그냥 있든 없든 우리 세계에 전혀 영향을 주지 않음을 증명한 것일 뿐입니다. (적어도 전자기학에는 영향을 주지 않는다는 것입니다.)

우리는, 어떤 것을 관찰하기 위해서 만져봐야 합니다. 만져지지 않는다면, 그것은 없는 것과 마찬가지이고, 만지지 않았는데 뭔가가 변한다는 것은 논리적인 모순입니다. 이해 하시겠습니까?

물론 이 비용은 교통수단마다 다르다.

내게 있어 실제적인 지출에 해당하는 것은 “시간”과 “돈”이므로, 시간과 돈을 곱한 값을 “비용”으로 처리해야 할 것이다. 물론 시간가치를 돈으로 환산해서 합산해도 되지만, 이 경우에는 곱셈이 맞다고 본다. 왜냐하면 돈을 아주 많이 들인다고 시간이 0이 되는 것도 아니고, 시간이 아주 오래 걸린다고 해서 돈이 0원이 들어가는 것도 아니기 때문에, 0이 아닌 “비용”을 사용했다면 반드시 둘 다 0이 아니어야 하기 때문이다. 또한, 절충한답시고 덧셈과 곱셈을 같이 쓰는 건 다음과 같이 의미가 없다. 돈을 $m$이라고 하고 시간을 $t$라고 하면

$m+t+m*t = m+t+m*t +1 -1 = m*(1+t)+t+1-1 = (m+1)*(t+1)-1$

이 되어서 대략 곱셈에 비례하게 된다.

그럼, 대략 방정식을 세워보면

$m*t=C$

여기서, $C$는 비용이 되겠다. 비용은 다시 다른 방법으로 계산해야 하는데

$C=C(기름값, 교통비, 시간, 교통량, 속력 )$

등등의 함수가 될 것이다. 물론 이때 교통비는 다시 기름값과 시간의 함수로 표현된다.

이제, 이것을 Action으로 두고 최적화 시키는 것을 써 보자.

$L(m, \dot{m}, t)=C-m*t$

$\frac{\partial L}{\partial_m}-\frac{d}{dt}\frac{\partial}{\partial_{\dot{m}}}$

그럼 이제 $m(t)$를 구할 수 있다.

주의 : 난 물리학 전공이지 경제학 전공이 아니므로 위 내용이 맞는 내용인지는 보증하지 못한다.