그레이엄 수

위키백과, 우리 모두의 백과사전.

그레이엄 수(Graham's number)는 미국수학자 로널드 그레이엄이 이름을 붙인 특정한 자연수의 명칭으로서, 로 표시한다. 램지 이론에 대한 수학 문제의 해결과정에서 상계(upper bound)로 제시된 큰 수로서, 1980년 기네스 북에 의해 수학적 의미를 갖는 수 가운데 가장 큰 수의 일례로 들리기도 했다. 일상적인 자연수 표기법이나 거듭제곱의 방법으로는 도저히 나타낼 수 없어서, 특수하게 정의된 큰 수 표기법을 사용하여 나타낸다. 이 수 전체는 아직까지 계산된 적도, 또한 그렇게 계산된 수를 나열하는 것도 불가능하다. 다만, 계산 과정에 규칙성이 있기 때문에 1의 자리부터 마지막 500자리까지의 수는 알려져 있다.

하지만 이보다 큰 수는 만들어낼 수 있다. 덧셈을 재귀하면 곱셈, 지수, 화살표, G(n), 콘웨이 화살표 식으로 가게 된다. 단순히 재귀만 해도 하이퍼 그레이엄은 물론, {3,3,3,2}까지도 넘을 수 있다. 그리고 콘웨이 화살표 이후부터는 재귀만 해서는 다음 단계로 넘어갈 수 없다.

문제[편집]

한개의 평면 완전부분그래프를 가진 2색 3차원 그래프. 부분 그래프는 아래에 그려졌다. 만약 이 부분그래프의 바닥 모서리를 파란색으로 바꾼다면 한개의 색을 가진 네 꼭짓점 평면 완전 그래프는 없다. 따라서 N* > 3이다.

N차원 초입방체의 모서리, 모든 대각선을 포함한 완전 그래프 을 그린다. 그래프의 변을 두 가지 색으로 칠할 때, 몇 차원 이상이 되면 초입방체의 한평면에 있는 4개의 점에 대해서 4 개 꼭짓점을 이은 완전 그래프 는 하나의 색으로 되어 있다. 그레이엄은 이 N의 상계로서 그레이엄의 수를 제시하였다.

유도 방법[편집]

그레이엄 수의 기본은 3이다. 3을 밑으로 하여 3의 연산을 무수히 반복하는 과정이 되풀이된다. 물론 실제로 무수히 반복하지는 않고 유한하지만, 그 수의 크기가 극도로 크다는 말로는 모자라기 때문에 이 수를 감당해내는 것조차도 불가능하다. 이 연산을 나타내기 위해서 커누스 윗화살표 표기법의 이해가 필요하다. 커누스 윗화살표 표기법은 하이퍼연산자라고도 하며, 덧셈-곱셈-거듭제곱-테트레이션-펜테이션-....등으로 그 직전 연산의 반복으로 상위 연산을 정의하는 기호이다. 이 커누스 윗화살표 표기법을 재귀하면 G(n)에 도달한다.

커누스 윗화살표 표기법을 이용하여 f(n)를 다음과 같이 정의하자.

지수를 조금만 쌓았음에도 벌써 조단위다. 게다가 이 지수는 앞으로 늘어날 화살표 앞에서는 먼지만도 못하다.

  (f(2)번 반복) (7,625,597,484,987번 반복)

벌써부터 상상을 깨버린 수가 나왔다. 화살표 3개만 되었음에도 지수로 표시하기에도 그냥 써서는 평생 써도 다 못 쓸 정도로 크며, 2cm 크기로 써도 지수 계단의 높이는 지구에서 태양까지 도달한다. 만약 구골플렉스 진법으로 이보다 큰 수를 만들려면 숫자를 하나씩 써서는 당연히 못 쓰고, 임의의 숫자 뒤에 숫자를 쭉 쓴 후 모두 선택 후 복붙을 반복해서 얻은 수만큼 진법을 늘리기를 반복해야만 한다. 하지만 그레이엄 수까지는 아직이다, 아직 멀었다.

  (G(3)번 반복)
            (f(3)번 반복)

이렇게 급격히 증가하며, f(3)부터 이미 계산하거나 표기하기가 곤란해진다. 여기서 라 정의된다. 그러면

(화살표가 f(4)개, 여기서 지수는 합성 횟수를 뜻한다.)

(화살표가 f2(4)개)

(화살표가 f3(4)개)

...

(화살표가 f62(4)개)

(화살표가 f63(4)개)

이와 같이 증가하여 로 정의되는 G가 그레이엄 수이다.

결과[편집]

그레이엄 수는 너무 크기 때문에 10진수로 표기하는 것이 불가능하지만, 마지막 500자리의 수는 다음과 같이 알려져 있다.(그리고, 그레이엄 수가 정확히 몇 자리의 수인지도 알려져 있지 않고, 그것을 정확히 알아내는 것도 불가능하다. 위 수학 문제만 해도 실제로 그만한 차원의 도형에 하나씩 선을 그은 것도 아닌데, 아래의 수는 계산 패턴을 통해 알아낸 것.)

 …02425950695064738395657479136519351798334535362521
  43003540126026771622672160419810652263169355188780
  38814483140652526168785095552646051071172000997092
  91249544378887496062882911725063001303622934916080
  25459461494578871427832350829242102091825896753560
  43086993801689249889268099510169055919951195027887
  17830837018340236474548882222161573228010132974509
  27344594504343300901096928025352751833289884461508
  94042482650181938515625357963996189939679054966380
  03222348723967018485186439059104575627262464195387

수의 규모[편집]

  • 그레이엄 수를 플랑크 길이의 크기로 인쇄하더라도, 그 수의 전체 길이는 우주의 직경보다 더 크다.
  • 그레이엄 수를 1초에 구골플렉스 글자씩 빠르게 적더라도, 우주의 나이보다 더 오랜 시간이 필요하다.
  • 그레이엄 수는 우주에 존재하는 모든 소립자의 개수보다 더 크다.
  • 그레이엄 수를 지수를 사용해 쓰더라도, 쓸 종이를 우주에 다 구겨넣을 수 없다.
  • 그레이엄 수 만큼의 모래들이 만약 있다면, 넓디 넓은 모든 우주를 총 동원해도 턱없이 부족하며, 지구상 관측 가능 우주 크기의 9999 나유타×99초과관수 이상의 9를 9999경 면적을 곱해 합쳐도 터무니 없이 부족하다.
  • 그레이엄 수의 숫자를 수백 항하사 개의 소립자가 들어갈 수 있는 세계에서 가장 작은 크기(기준)인 초극암원 A3원자(超極暗原 A3原子)의 크기로 채워도(써도) 모든 전 우주는 공간이 모자라다.
  • 그레이엄 수는 구골플렉스보다도 더 크다.

더 보기[편집]

참고 문헌[편집]

  • Graham, R. L.; Rothschild, B. L. (1971). “Ramsey's Theorem for n-Parameter Sets” (PDF). 《Transactions of the American Mathematical Society》 159: 257–292. doi:10.2307/1996010. JSTOR 1996010. 2012년 4월 1일에 원본 문서 (PDF)에서 보존된 문서. 2014년 5월 26일에 확인함.  The explicit formula for N appears on p. 290. This is not the "Graham's number" G published by Martin Gardner.
  • Graham, R. L.; Rothschild, B.L. (1978). "Ramsey Theory", Studies in Combinatorics, Rota, G.-G., ed., Mathematical Association of America, 17:80–99. On p. 90, in stating "the best available estimate" for the solution, the explicit formula for N is repeated from the 1971 paper.
  • Gardner, Martin (November 1977). “Mathematical Games” (PDF). 《Scientific American》 237: 18–28. doi:10.1038/scientificamerican1177-18. ; reprinted (revised) in Gardner (2001), cited below.
  • Gardner, Martin (1989). 《Penrose Tiles to Trapdoor Ciphers》. Washington, D.C.: Mathematical Association of America. ISBN 0-88385-521-6. 
  • Gardner, Martin (2001). 《The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems》. New York, NY: Norton. ISBN 0-393-02023-1. 
  • Exoo, Geoffrey (2003). “A Euclidean Ramsey Problem”. 《Discrete and Computational Geometry》 29 (2): 223–227. doi:10.1007/s00454-002-0780-5.  Exoo refers to the Graham & Rothschild upper bound N by the term "Graham's number". This is not the "Graham's number" G published by Martin Gardner.
  • Barkley, Jerome (2008). “Improved lower bound on an Euclidean Ramsey problem”. arXiv:0811.1055v1 [math.CO]. 

외부 링크[편집]