 |
ผมขออ้างอิง #13กับ#19 มาขยายความให้เป็นเชิงคณิตศาสตร์นะคับ
เนื่องจากหมวกมี2สี เราลองพิจารณาเศษที่เหลือจากการหารจำนวนเต็มด้วย2 ซึ่งได้แก่0กับ1
กำหนดฟังก์ชัน f(n) โดยที่
f(n) = 1 เมื่อนักโทษคนที่ n สวมหมวกสีฟ้า
f(n) = 0 เมื่อนักโทษคนที่ n สวมหมวกสีชมพู
พูดง่ายๆก็คือ นักโทษแต่ละคนจะมีหมายเลขประจำตัวตามสีหมวกที่ตนเองสวม
เช่นถ้านักโทษคนที่ 3 สวมหมวกสีฟ้า เขาก็จะมีเลขประจำตัวคือ 1 นั่นคือ f(3) = 1
ถ้านักโทษคนที่18สวมหมวกสีชมพู เขาก็จะมีเลขประจำตัวคือ 0 นั่นคือ f(18) = 0
จะเห็นว่าในตอนเริ่มต้นนักโทษทุกคนจะไม่รู้หมายเลขประจำตัวของตัวเอง
แต่จะรู้หมายเลขประจำตัวของนักโทษคนที่อยู่ข้างหน้าเขาทุกคน
กำหนดฟังก์ชัน F(n) โดยที่
F(n) = [f(1) + f(2) +...+ f(n)] mod 2 เมื่อ n > 0
F(n) = 0 เมื่อ n = 0
พูดง่ายๆก็คือ F(n) แทนเศษที่เกิดจากการหาร [ผลรวมของเลขประจำตัวของนักโทษทุกคนตั้งแต่คนแรกจนถึงคนที่ n ] ด้วย 2
จะเห็นว่านักโทษคนที่ n จะทราบค่า F(n-1) เพราะเขาทราบค่า f(1) , f(2) ,..., f(n-1)
ลองสมมติว่ามีนักโทษเหลือทั้งหมด k คนก่อน
และสมมติว่านักโทษที่เหลือทุกๆคนทราบว่า F(k) มีค่าเท่าใด
เนื่องจากนักโทษคนที่ k ย่อมทราบว่า F(k-1)มีค่าเท่าใด และเขาทราบค่าF(k)
เขาก็ย่อมทราบว่า f(k) มีค่าเท่าใดด้วย นั่นคือทราบว่าตนเองสวมหมวกสีอะไร
(หรือพูดอีกแบบก็คือถ้านักโทษทุกๆคนรู้ว่าผลรวมหมายเลขประจำตัวของนักโทษทุกคนหารด้วย2แล้วเหลือเศษเท่าไหร่
นักโทษคนหลังสุดย่อมรู้ว่าตนเองมีหมายเลขประจำตัวอะไร นั่นคือรู้ว่าตัวเองสวมหมวกสีอะไร)
ดังนั้นนักโทษคนที่ k ก็สามารถตอบคำถามได้ถูกต้อง
และนักโทษคนอื่นๆทุกคนก็จะรู้ด้วยว่านักโทษคนที่ k ตอบถูกแน่นอน
จึงทำให้นักโทษคนอื่นๆที่เหลือทราบค่า f(k)
เนื่องจากนักโทษคนที่ k-1 ทราบค่า F(k) จากสมมติ , ทราบค่าf(k) จากคำตอบของคนข้างหลัง และ ทราบค่าF(k-2) จากสีหมวกของคนข้างหน้าทุกคน
ดังนั้นเขาก็จะทราบค่า f(k-1) (รู้ว่าตนเองสวมหมวกสีอะไร)
ทำให้เขาตอบคำถามได้ถูกต้อง และจะทำให้นักโทษคนอื่นๆที่เหลือทราบค่า f(k-1) ด้วย
ในทำนองเดียวกันนักโทษที่เหลือทั้งหมดก็จะตอบคำถามถูก และไม่โดนประหารชีวิต
เราจึงสรุปได้ว่า ภายใต้กติกาที่พระราชากำหนด
ถ้า "มีนักโทษเหลือ k คน และนักโทษทั้งหมดkคนทราบว่า F(k)มีค่าเท่าใด" แล้ว "นักโทษทั้งkคนสามารถตอบคำถามถูกทุกคนได้"
กลับมาที่ปัญหาจริงๆ มีนักโทษทั้งหมด 20 คน
และนักโทษทุกคนไม่มีใครรู้เลยว่า F(20) มีค่าเท่าไหร่
แต่นักโทษคนที่20(คนหลังสุด) รู้ว่า F(19) มีค่าเท่าไหร่
เราจึงวางแผนการให้ นักโทษคนที่20 ตะโกนบอกค่าF(19)
(หมายความว่าถ้า F(19) = 1 ก็ให้เขาตะโกนว่า สีฟ้า ถ้าF(19) = 0 ก็ให้เขาตะโกนว่าสีชมพู)
ซึ่งจะทำให้นักโทษที่เหลือทั้งหมด19คนทราบค่าF(19) และสามารถตอบได้ถูกต้องตามที่ได้แสดงไว้ข้างต้น
จึงมีนักโทษคนที่20ที่เสี่ยงเพียงคนเดียว
หมายเหตุ : mod 2 หมายถึงหารด้วย2แล้วเอาเศษ เช่น 5mod2 = 1 , 1mod2 = 1, 10mod2 = 0
แก้ไขเมื่อ 19 ส.ค. 54 17:54:17
| จากคุณ |
:
อิอิคุง  
|
| เขียนเมื่อ |
:
19 ส.ค. 54 17:32:55
|
|
|
|
|
คุณจะคิดแผนการและเตี๊ยมกับพวกเขาว่ายังไงครับ???
