เฉลย

posted on 13 Jul 2005 13:06 by house in Other

ผมยกคำตอบมาให้แบบเต็มๆ คำต่อคำ จากเจ้าของโจทย์ครับ

โอเค ดูเหมือนโจทย์จะยากอยู่บ้างมีใครทราบคำตอบแล้วบ้างไหมเนี่ย สำหรับคำตอบตัวเลขตั้งต้นทั้งสองก็คือ 4 กับ 13 ถ้าใครยังไม่ทราบวิธีหาคำตอบและอยากคิดเล่นๆ เป็นการบ้านต่อไปก็ไม่จำเป็ต้องอ่านต่อนะครับ ผู้ที่สนใจสามารถอ้านคำอธิบายได้ข้างท้ายข้อความฉบับนี้

>
> คิดออกแล้วเหมือนกัน ถ้างั้นลองดูปัญหานี้บ้าง เป็นปัญหาเก่าแล้ว
> มีคนเคยแก้โจทย์นี้ในใจออกก่อนนอนด้วยนะ
>
> ---------------------------------------------------------------
> สำหรับจำนวนเต็มบวกสองจำนวนที่มีค่าตั้งแต่ 2 ถึง 99 และมีคนสองคน สมมุติคือ A และ B โดย
> A ทราบค่าผลคูณของสองจำนวนนั้น ส่วน B ทราบผลบวก
> เมื่อถูกถามว่าจำนวนเต็มบวกทั้งสองคืออะไร ต่อไปนี้เป็นการสนทนาของทั้งคู่
>
> A: ผมไม่รู้ว่าจำนวนทั้งสองคืออะไร
> B: ผมรู้อยู่แล้วล่ะรู้ว่าคุณไม่รู้หรอก
> A: ถ้างั้นผมรู้แล้วล่ะว่าทั้งสองจำนวนคืออะไร
> B: ถ้างั้นผมก็รู้แล้วเหมือนกัน
>
> A และ B ทราบคำตอบได้อย่างไร และจำนวนทั้งสองคืออะไร คำตอบมีเพียงคำตอบเดียวจริงหรือไม่
> ---------------------------------------------------------------
>
> Solution ====================================================จากบทสนทนาสามารถสรุปได้เบื้องต้นดังนี้:
1. ผลคูณที่ A มีต้องไม่ใช่ผลคูณของจำนวนเฉพาะ 2 จำนวน
2. ถ้าแยกตัวประกอบของผลคูณที่ A มีอยู่ จะได้ตัวประกอบจำนวนเฉพาะที่มีค่าน้อยกว่า 50 หรืออีกนัยหนึ่งคือ ตัวประกอบของผลคูณของ A ต้องไม่มีจำนวนเฉพาะที่มีค่าตั้งแต่ 53 ขึ้นไป

เหตุผล #1: ถ้าแยกตัวประกอบได้เป็นจำนวนเฉพาะสองจำนวน A จะต้องทราบคำตอบได้ทันที
เหตุผล #2: เนื่องจากตัวเลขตั้งต้นทั้งสองมีค่าตั้งแต่ 2 ถึง 99 ดังนั้น ถ้ามีตัวประกอบจำนวนเฉพาะที่มีค่ามากกว่า 50 จะทราบได้ทันทีว่าตัวประกอบนั้นจะเป็นตัวเลขตั้งต้นตัวหนึ่ง (เพราะ 50 คูณกับ 2 ซึ่งเป็นตัวประกอบที่น้อยที่สุด จะมีค่าเกิน 99) และจะทราบตัวเลขตั้งต้นอีกตัวหนึ่งได้จากผลคูณของตัวประกอบที่เหลือ

ซึ่งเมื่อ B ซึ่งได้รับผลบวกของจำนวนทั้งสองสามารถทราบได้ว่า
A ไม่สามารถระบุตัวเลขคำตอบได้แน่นอน ค่าที่ B จะต้องสามารถรับประกันคุณสมบัติข้างต้น ดังนั้นค่าที่ B มีจะต้องไม่สามารถเขียนในรูปผลบวกของจำนวนเฉพาะได้ ซึ่งถ้าลองไล่เลขจำนวนเฉพาะตั้งแต่ 2 - 99 จะพบว่าเลขคู่ทั้งหมดที่มากกว่า 2 สามารถเขียนในรูปแบบของผลบวกของจำนวนเฉพาะสองจำนวนได้ เช่น 4=2+2, 6=3+3, 8=3+5,.., 188=91+97,.. (Goldbach Conjecture[1])

ส่วนเลขคี่ที่เป็นผลบวกของจำนวนเฉพาะ จะต้องมี 2 เป็นหนึ่งในตัวเลขนั้น ดังนั้นค่าที่ B มีอยู่จะต้องเป็นเลขคี่ และเขียนอยู่ในรูป N + 2 โดย N ไม่ใช่จำนวนเฉพาะ และค่าผลบวกนี้ต้องมีค่าน้อยกว่าหรือเท่ากับ 54 (แทนค่า N=52<53; 52+2=54) จึงจะรับประกันคุณสมบัติตามข้อสังเกตที่ 2 ได้

ซึ่งจากข้ออนุมานข้างต้น เซตของผลบวกของ B ที่เป็นไปได้มีดังต่อไปนี้:
S0 = {9+2, 15+2, 21+2, 25+2, 27+2, 33+2, 35+2, 39+2, 45+2, 49+2, 51+2} = {11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53}

และเมื่อ B กล่าวว่าเขาทราบว่า A ไม่ทราบตัวเลขตั้งต้นนั้น A ก็สามารถอนุมานได้ว่าผลบวกที่ B มีนั้นอยู่ในเซต S0 ข้างต้น และเมื่อประมวลเข้ากับตัวเลขผลคูณที่ตนมีอยู่ก็สามารถทราบตัวเลขตั้งต้นได้ นั่นย่อมหมายความว่าผลคูณที่ A มีสามารถหาผลบวกของเลขตั้งต้นทั้งสองได้ในเซต S0 โดยไม่เกิดความกำกวม เช่น ถ้า ผลคูณสามารถเขียนได้หลายแบบ และผลบวกของตัวคูณมากกว่าหนึ่งแบบเป็นสมาชิกของ S0 ก็จะไม่สามารถระบุคำตอบที่แน่ชัดได้ เช่น 30 เขียนได้ เป็น 6x5 หรือ 2x15 ซึ่งผลบวกของตัวคูณคือ 11 และ 17 อยู่ใน S0 ทั้งคู่

แต่ถ้าผลคูณที่ A มีสามารถเขียนได้ในรูป P x 2^n โดย P เป็นจำนวนเฉพาะ A ก็จะสามารถทราบคำตอบได้โดยง่ายดาย เช่น ถ้าผลคูณคือ 24

A ก็สามารถระบุได้ทันทีว่าคำตอบคือ 8 และ 3 ซึ่ง 8+3=11 อยู่ในเซต S0 หรือถ้าผลคูณคือ 28 ก็สามารถระบุคำตอบคือ 7 และ 4 ซึ่ง 7+4=11 เป็นต้น

แต่ในกรณีที่ผลบวกเท่ากับ 11 นี้ B จะไม่สามารถทราบคำตอบได้แน่ชัด (ในกรณีนี้อาจเป็นได้ทั้ง 7+4 หรือ 3+8) ดังนั้นผลบวกที่ B มีอยู่จะต้องสามารถเขียนในรูป P + 2^n ได้เพียงรูปแบบเดียว

สมาชิกของเซต S0 สามารถเขียนในรูป P + 2^n ได้ดังนี้:
11 = 7 + 4 = 8 + 3
17 = 13 + 4
23 = 19 + 4 = 16 + 7
27 = 23 + 4 = 19 + 8 = 11 + 16
29 = 13 + 16
35 = 31 + 4 = 19 + 16
37 = 29 + 8 = 5 + 32
41 = 37 + 4
47 = 43 + 4 = 31 + 16
51 = 47 + 4 = 43 + 8 = 19 + 32
53 = 37 + 16

ดังนั้นจะได้เซตผลบวกที่เป็นไปได้ของ B ต่อไปนี้ S1 = {17, 29, 41, 53} ถ้าลองพิจารณาตัวประกอบที่เป็นไปได้จากผลบวกในเซต S1 แต่ละค่าจะได้ว่า
17: 2x15 = 6x5 A ระบุคำตอบไม่ได้ เนื่องจาก 6+5 = 11 อยู่ใน S0
3x14 = 2x21 A ระบุตอบไม่ได้ เนื่องจาก 21+2 = 23 อยู่ใน S0
4x13 เป็นค่าที่ A สามารถระบุคำตอบได้
5x12 = 3x20 A ระบุตอบไม่ได้ เนื่องจาก 20+3 = 23 อยู่ใน S0
6x11 = 2x33 A ระบุตอบไม่ได้ เนื่องจาก 33+2 = 35 อยู่ใน S0
7x10 = 2x35 A ระบุตอบไม่ได้ เนื่องจาก 35+2 = 37 อยู่ใน S0
8x9 = 3x24 A ระบุตอบไม่ได้ เนื่องจาก 24+3 = 27 อยู่ใน S0
ดังนั้น เมื่อผลบวกของ B คือ 17 ตัวเลขตั้งต้นคือ 4 และ 13 เป็นคำตอบที่ถูกต้องที่ทำให้ A และ B ต่างสามารถอนุมานคำตอบของกันและกันได้เพียงกรณีเดียว

สำหรับค่าผลบวกอื่นๆ ในเซต S1 นั้น เมื่อลองพิจารณาในลักษณะเดียวกันจะพบคำตอบที่กำกวมสำหรับ B (มีกรณีที่ A สามารถทราบคำตอบได้มากกว่า 1 กรณี) ดังนี้ (โดยละกรณีที่ A ไม่สามารถระบุคำตอบได้)
29: 16x13 เป็นค่าที่ A สามารถระบุคำตอบได้ 4x25 = 20x5 A หาคำตอบได้คือ 4x25 เนื่องจาก 20+5=25 ไม่อยู่ใน S0

41: 4x37 เป็นค่าที่ A สามารถระบุคำตอบได้ 3x38 = 2x57 = 6x19 A หาคำตอบได้คือ 3x38 เนื่องจากทั้ง 2+57=59 และ 6+19=25 ไม่อยู่ใน S0

53: 16x37 เป็นค่าที่ A สามารถระบุคำตอบได้ 6x47 = 2x141 = 3x94 A หาคำตอบได้คือ 6x47 เนื่องจากอีกสองกรณีผลบวกที่ไม่อยู่ใน S0

คำตอบที่ถูกต้องจึงมีเพียงคำตอบเดียวคือ เลขตั้งต้นทั้งสองคือ 4 และ 13
ซ.ต.พ. http://mathworld.wolfram.com/GoldbachConjecture.html

ผมไม่ใช่คนคิดปัญหานี้ขึ้นและไม่ได้แก้โจทย์นี้ออกหรอกนะ คนที่ขบคิดปัญหานี้และแก้ออกชั่วข้ามคืน(คิดในใจ!) ก็คือ E. W. Dijkstra ผู้สนใจสามารถอ่านบันทึกของท่านเกี่ยวกับการแก้ปัญหานี้ได้เพิ่มเติมที่ http://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD666.html

ผู้ที่สนใจงานของ Dijkstra สามารถอ่านบันทึกอื่นๆ และงานทางวิชาการ ตลอกจนชีวประวัติของนักวิทยาการคอมพิวเตอร์ผู้ล่วงลับนี้ได้ที่ E. W. Dijkstra Archive http://www.cs.utexas.edu/users/EWD/
-tlt

edit @ 2005/07/13 13:21:08
edit @ 2005/07/13 13:26:50
edit @ 2005/07/13 13:29:23
edit @ 2005/07/13 20:42:55

10 Comments