creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
กลยุทธ์กลุ่มกับเกมไพ่

เราทำการทดสอบกลุ่ม N คน ดังนี้ มีไพ่ N ใบ เขียนหมายเลข 1 ถึง N บนด้านหลังของไพ่ และเขียนชื่อคนแต่ละคนบนด้านหน้าของไพ่แต่ละใบ (ดังนั้น ไพ่ 1 ใบ ด้านหลังมีตัวเลข 1 ตัว และด้านหน้ามีชื่อคน 1 ชื่อ) ในห้อง ไพ่ถูกเรียงคว่ำหน้า (แสดงด้านตัวเลข) คนเข้าไปในห้องทีละคน แต่ละคนสามารถพลิกไพ่ได้ N/2 ใบ ถ้าพลิกไพ่แล้วเจอชื่อของตัวเองถือว่าคนนั้นทำงานสำเร็จ ก่อนนำคนต่อไปเข้ามาภายในห้อง เราจัดไพ่ให้เหมือนเดิมทุกประการ ให้อยู่ในสภาพก่อนคนแรกเข้าห้อง กลุ่มที่ทำการทดสอบจะชนะก็ต่อเมื่อทุกคนทำงานสำเร็จ แต่ถ้ามีอย่างน้อย 1 คนทำงานไม่สำเร็จ ถือว่าทีมแพ้ ถ้าไม่มีการนัดแนะใด ๆ กันเลยระหว่างสมาชิกในกลุ่ม ดังนั้นใครก็ตามที่เข้าห้องมีโอกาสทำงานสำเร็จเท่ากับ 50% โอกาสที่กลุ่มจะชนะเท่ากับ 0.5N ยิ่ง N มากก็หมายความว่ามีโอกาสชนะน้อยลง แบบนี้คงเป็นเกมที่โหดร้ายเกินไป เราจึงอนุญาตให้กลุ่มประชุมและวางแผนกันได้ก่อนเริ่มเกม แต่เมื่อเริ่มเกมแล้ว เราห้ามคนในกลุ่มสื่อสารกันไม่ว่าจะโดยวิธีการใดก็ตาม

ปัญหาข้อนี้คือ ให้สมมติว่าคุณเป็นสมาชิกคนหนึ่งในกลุ่มที่ทำการทดสอบ สมมติว่าคุณเป็นหัวหน้ากลุ่ม เป็นกุนซือของกลุ่มก็แล้วกัน คุณจะเสนอกลยุทธ์ใดเพื่อให้กลุ่มมีโอกาสชนะด้วยความน่าจะเป็นคงที่ค่าหนึ่ง (เช่น คุณอาจจะเสนอกลยุทธ์แล้วพิสูจน์ให้เห็นว่ากลยุทธ์ของคุณนำชัยชนะมาสู่ทีมด้วยความน่าจะเป็นจำนวนจริงบวกคงที่ x)



โจทย์ข้อนี้จะว่ายากก็ค่อนข้างยากครับ แต่ถ้าคิดดี ๆ ก็ไม่ยากมาก เพราะเรารู้ว่าถ้าให้แต่ละคนเข้าไปเปิดไพ่อย่างสุ่ม ทำให้เหตุการณ์การเปิดไพ่แต่ละรอบเป็นอิสระต่อกัน โอกาสชนะของทีมย่อมเท่ากับ 0.5N อย่างหลีกเลี่ยงไม่ได้ ดังนั้นเราต้องคิดกลยุทธ์ที่การเปิดไพ่แต่ละรอบ (แต่ละคน) ไม่เป็นอิสระต่อกัน ลองพิจารณาตัวอย่างกรณี N = 4 ซึ่งแต่ละคนมีโอกาสเปิดไพ่ 2 ใบ ให้ทั้ง 4 คนชื่อ A B C D และใช้กลยุทธ์ว่าต่อไปนี้เราเปลี่ยนชื่อเป็นตัวเลข A B C D = 1 2 3 4 ตามลำดับ การเปิดไพ่ให้เปิดใบหมายเลขตามชื่อของตัวเองเป็นใบแรก ถ้าใบแรกไม่ตรง ก็ให้เปิดไพ่หมายเลขตามชื่อที่ปรากฎในไพ่ใบแรกเป็นใบต่อไป

เช่นถ้าผมคือ A ผมเข้าห้องไปปุ๊บ เปิดใบที่ 1 เป็นใบแรก (เพราะผมคือ A) ถ้าชื่อที่ปรากฎคือ C ผมก็จะเปิดไพ่ใบหมายเลข 3 เป็นไพ่ใบที่ 2 (เพราะ C คือ 3 ตามที่ตกลงกันไว้) จากนั้นเขียนการสับเปลี่ยนทั้งหมดที่เป็นไปได้ของไพ่กับชื่อดังนี้

1 2 3 4 <---- ไพ่หมายเลข 1 - 4

A B C D <---- กรณีที่ชื่อหน้าไพ่ตรงกับหมายเลขที่เรากำหนดพอดี (win)
A B D C <--- win
A D B C
A D C B <--- win
A C B D <--- win
A C D B
B A C D <--- win
B A D C <--- win
B C A D
B C D A
B D C A
B D A C
C A B D
C A D B
C B A D <--- win
C B D A
C D B A
C D A B <--- win
D A C B
D A B C
D B A C
D B C A <--- win
D C B A <--- win
D C A B

ด้วยกลยุทธ์นี้โอกาสที่ทีมชนะเท่ากับ 5/12 หรือ 41.6% ไม่เลวเลยทีเดียว ลองขยายผลกับกรณี N ใด ๆ กลยุทธ์นี้โดยเนื้อแท้ของมันคือการสร้างรูปแบบการเปิดที่เป็นวง (ถ้าวงใด ๆ วนครบรอบด้วยความยาวที่น้อยกว่า N/2 คนที่อยู่ในวงนั้นจะทำงานสำเร็จทุกคน) กำหนดให้ l คือความยาวของวง เราลองย้อนไปดูค่า l ทั้งหมดในกรณี N = 4 ก่อนนะครับ

1 2 3 4 <---- ไพ่หมายเลข 1 - 4
A B C D : l = 1 x 4
A B D C : l = 1 x 2, l = 2
A D B C : l = 1, l = 3
A D C B : l = 1 x 2, l = 2
A C B D : l = 1 x 2, l = 2
A C D B : l = 1, l = 3
B A C D : l = 1 x 2, l = 2
B A D C : l = 2 x 2
B C A D : l = 1, l = 3
B C D A : l = 4
B D C A : l = 1, l = 3
B D A C : l = 4
C A B D : l = 1, l = 3
C A D B : l = 4
C B A D : l = 1 x 2, l = 2
C B D A : l = 1, l = 3
C D B A : l = 4
C D A B : l = 2 x 2
D A C B : l = 1, l = 3
D A B C : l = 4
D B A C : l = 1, l = 3
D B C A : l = 1 x 2, l = 2
D C B A : l = 2 x 2
D C A B : l = 4

กรณีที่มี l > N/2 ทีมแพ้อย่างแน่นอน ดังนั้นสิ่งที่ต้องทำคือหาโอกาสที่ permutation มีวงยาว l สามารถหาได้โดยเลือกไพ่ที่ไม่อยู่ในวงยาว l ได้ C(N,N-l) แบบ แต่ละแบบสับเปลี่ยนได้ (N-l)! และแต่ละแบบเกิดวงที่ยาว l ได้ (l-1)! แบบ ดังนั้นจำนวนแบบทั้งหมดที่มีวงยาว l = N!/l (ถ้าพูดให้เจาะจงยิ่งขึ้นคือจำนวนวงทั้งหมดในทุกแบบที่เป็นไปได้ที่ยาว l เช่น N = 4, l = 1 มีทั้งหมด 24 วง แต่อย่าลืมว่าในแบบการสับเปลี่ยนแบบ A B C D แบบเดียวมันมีถึง 4 วง หรือกรณี l = 2 มีทั้งหมด 12 วง แต่แบบ B A D C, C D A B และ D C B A มีแบบละ 2 วง อย่างไรก็ดีในกรณีนี้ไม่ซีเรียสครับเพราะสุดท้ายเราสนใจที่ l > N/2 ซึ่งจำนวนวงที่ l > N/2 นี้เกิดขึ้นในเหตุการณ์แต่ละแบบเท่านั้น จำนวนวงจึงเท่ากับจำนวนแบบ) หรือโอกาสที่ permutation มีวงยาว l = 1/l

มันมีอีก 1 ข้อสังเกตครับ คือ การเกิดเหตุการณ์ที่ l > N/2 ใด ๆ จะเป็นอิสระจากกัน เช่นถ้า N = 4 การมีวง l = 3 กับ l = 4 ไม่มีทางเป็นเหตุการณ์ที่เกิดร่วมกัน และโอกาสที่ทีมไม่ชนะ ก็คือโอกาสที่การสับเปลี่ยนมี l > N/2 กำหนดให้ Pl เท่ากับ โอกาสที่ permutation มีวงยาว l หรือ Pl = 1/l

สำหรับ N เป็นจำนวนคู่ โอกาสที่ทีมไม่ชนะเท่ากับ PN + PN-1 + PN-2 + ... + P(N/2)+1 = HN - HN/2

เมื่อ

Hn = เลขฮาร์โมนิกอันดับที่ n = 1 + 1/2 + 1/3 + ... + 1/n

ค่าของ HN - HN/2 อาจหาได้จากพื้นที่ใต้กราฟ 1/x เมื่อค่า x อยู่ในช่วง [N/2,N] (อินทิเกรตหาพื้นที่ใต้กราฟ 1/x dx ค่า x ในช่วง [N/2,N]) ได้เท่ากับ ln(2) ดังนั้นโอกาสชนะของทีมด้วยกลยุทธ์นี้เท่ากับ 1 - ln(2) หรือประมาณ (อย่างน้อย) 30.68%

ถ้า N เป็นจำนวนคี่ เราหาขอบเขตบนของ HN - H(N-1)/2 ด้วยการหาพื้นที่ใต้กราฟ 1/x หรืออินทิเกรตแบบเดียวกับกรณีของ N เป็นจำนวนคู่ เราจะได้ว่า HN - H(N-1)/2 มีค่าไม่เกิน ln(2 + 2/(N-1)) ซึ่งไม่เกิน ln(2) + 1/(N-1) ดังนั้นโอกาสชนะของทีมเท่ากับ 1 - ln(2) - 1/(N-1)





Create Date : 28 เมษายน 2551
Last Update : 28 เมษายน 2551 18:13:23 น. 0 comments
Counter : 2168 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.