จำนวนกราแฮม

จากวิกิพีเดีย สารานุกรมเสรี

จำนวนกราแฮม (อังกฤษ: Graham's number) ตั้งชื่อตามชื่อของ โรนัลด์ กราแฮม เป็นจำนวนที่ได้รับการรับรองจากกินเนสส์บุ๊คว่าเป็นจำนวนที่มีค่ามากที่สุดเท่าที่เคยใช้ในบทพิสูจน์ทางคณิตศาสตร์

นิยามของจำนวนกราแฮม[แก้]

จำนวนกราแฮม สามารถนิยามโดยใช้สัญลักษณ์ลูกศรของคนูธได้ว่า


\left.
 \begin{matrix}
  G &=&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots\cdots \uparrow}3 \\
    & &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow}3 \\
    & &\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
    & &3\underbrace{\uparrow \uparrow \cdots\cdot\cdot \uparrow}3 \\
    & &3\uparrow \uparrow \uparrow \uparrow3
 \end{matrix}
\right \} \text{64 layers}

โดยที่ลูกศรของแต่ละชั้น (layer) มีจำนวนเท่ากับค่าของชั้นที่อยู่ถัดลงมา เมื่อเริ่มต้นจากชั้นบนสุด (ชั้นที่ 64) สามารถอธิบายเป็นสูตรทางคณิตศาสตร์ได้ดังนี้

G = g_{64},\text{ where }g_1=3\uparrow\uparrow\uparrow\uparrow 3,\  g_n = 3\uparrow^{g_{n-1}}3,

ปัญหาของกราแฮม[แก้]

จำนวนกราแฮมมีที่มาจากปัญหาของกราแฮมดังนี้

พิจารณาลูกบาศก์ n มิติ เชื่อมจุดยอดทุกคู่ให้เกิดกราฟสมบูรณ์ที่มีจุดยอด 2^n จุด จากนั้นระบายสีเส้นเชื่อมทุกเส้นด้วยสี 2 สี ค่าของ n ที่น้อยที่สุดเป็นเท่าไรที่จะต้องเกิดกราฟสมบูรณ์ที่มีจุดยอด 4 จุดซึ่งอยู่บนระนาบเดียวกันและทุกเส้นเชื่อมมีสีเดียวกัน

อย่างไรก็ตาม ยังไม่มีใครค้นพบคำตอบของปัญหาข้อนี้ แต่จำนวนกราแฮมถือเป็นขอบเขตบนที่ดีที่สุดของคำตอบเท่าที่มีการค้นพบ