그레이엄 수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

그레이엄 수(Graham's number)는 미국의 수학자 로널드 그레이엄이 이름붙인 특정 자연수의 명칭이다. 램지 이론에 대한 수학 문제의 해결과정에서 상계로 제시로서, 단순한 크기 이외의 수학적 의미를 갖는 수 가운데 가장 큰 수라는 의의를 갖는 수로서 기네스북에도 실려 있다. 그 크기는 너무나 거대해서 자연계 또는 물리적인 실체, 또는 문학적 비유나 상상등으로조차 비견될만한 존재가 없다. 일상적인 자연수 표기법이나 거듭제곱의 방법으로는 도저히 나타낼 수 없어서 특수하게 정의된 큰 수 표기법을 사용하여 나타낸다. 이 수 전체는 아직까지 계산된 적도, 또한 그렇게 계산된 수를 나열하는 것도 불가능하나, 계산과정에 규칙성이 있기 때문에 마지막 500자리의 수는 알려져 있다. 이름이 붙어있는 수 가운데 그레이엄 수보다 더 큰 수는 있으나, 수학적,또는 물리적 의의는 없다.

문제[편집]

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

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

유도 방법[편집]

그레이엄 수의 기본은 3이다. 3을 밑으로 하여 3의 연산을 무수히 반복하는 과정이 되풀이된다. 이 연산을 나타내기 위해서 크누스 윗화살표 표기법의 이해가 필요하다. 크누스 윗화살표 표기법은 하이퍼연산자라고도 하며, 덧셈-곱셉-거듭제곱-테트레이션-펜트레이션-....등으로 그 직전 연산의 반복으로 상위 연산을 정의하는 기호이다. 크누스 윗화살표 표기법을 이용하여 G(x)를 계산해 보면,

G(1) = 3\uparrow 3 = 3^3 = 27

G(2) = 3\uparrow \uparrow 3 = 3\uparrow (3\uparrow \uparrow 2) = 3\uparrow (3\uparrow 3) = 3\uparrow 27 = 7,625,597,484,987

G(3) = 3\uparrow \uparrow \uparrow 3 = 3\uparrow \uparrow (3\uparrow \uparrow \uparrow 2) = 3\uparrow \uparrow (3\uparrow \uparrow 3) = 3\uparrow \uparrow G(2) = 3\uparrow \uparrow 7,625,597,484,987=3^{3^{3^{.^{.^.}}}} (7,625,597,484,987번)

G(4) = 3\uparrow \uparrow \uparrow \uparrow 3 = 3\uparrow \uparrow \uparrow G(3) =\left.\begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{\cdot^{3}}}}}}\end{matrix}\right \}\left.\begin{matrix}3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}\end{matrix}\right \}\dots\left.\begin{matrix}3^{3^3}\end{matrix}\right \}3 (G(3)번)

이렇게 급격히 증가하며, G(3)부터 이미 계산하거나 표기하기가 곤란해진다.

G^2(4) = G(G(4)) = 3\uparrow ...\uparrow 3 (화살표가 G(4)개, 여기서 지수는 합성 횟수를 뜻한다.)

G^3(4) = G(G^2(4)) = 3\uparrow ...\uparrow 3 (화살표가 G2(4)개)

...

이와 같이 증가하여 G64(4)에 이른 것이 그레이엄 수이다.

더 보기[편집]

참고 문헌[편집]

  • Graham, R. L. (1971년). Ramsey's Theorem for n-Parameter Sets. 《Transactions of the American Mathematical Society》 159: 257–292. doi:10.2307/1996010. JSTOR 1996010. 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. 《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.
  • 틀:Cite arxiv

바깥 고리[편집]