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 คนยืนต่อคิวแถวเดียว ทุกคนมองตรงไปข้างหน้า (นึกภาพต่อคิวซื้ออาหาร ซื้อตั๋วชมภาพยนตร์ รอรถบัส --- เหตุการณ์เหล่านี้นาน ๆ ทีจึงเกิดขึ้นที่บ้านเรา) คุณคิดว่าโดยเฉลี่ยแล้วจะมีกี่คนที่สามารถพูดได้ว่า "คนที่ยืนอยู่ข้างหน้า เตี้ยกว่าฉันทุกคน"



วิธีคิดมีหลายวิธีครับ ผมเคยนำโจทย์ข้อนี้ไปโพสให้เพื่อน ๆ ในห้องหว้ากอคิดลับสมองกันเล่น ๆ คนแรกที่เข้ามาเขียนคำตอบไว้สวยงามคือคุณ Duke! เริ่มจากการหาจำนวนรูปแบบการเรียง ที่คนตำแหน่ง K จะเห็นคนข้างหน้าเตี้ยกว่า ดังนี้ ขั้นแรกเลือกคนมา K คนจาก N คน แล้วให้คนที่สูงที่สุดในกลุ่มที่เลือกมาไปยืนตำแหน่ง K แล้ว K-1 คนที่เหลือในกลุ่มไปยืนหน้าตำแหน่ง K อีก N-K คนนอกกลุ่มไปยืนหลัง K ด้วยการจัดแบบนี้คนที่อยู่ตำแหน่ง K จะมองเห็นคนข้างหน้าเตี้ยกว่าเสมอ มีรูปแบบทั้งหมดเท่ากับ C(N,K)(K-1)!(N-K)! = N!/K หรือโอกาสที่คนยืนตำแหน่ง K จะเห็นคนข้างหน้าเตี้ยกว่าเท่ากับ 1/K แทนค่า K ตั้งแต่ 1 ถึง N ได้ 1 + 1/2 + 1/3 + ... + 1/N นั่นคือฮาร์โมนิกนัมเบอร์อันดับที่ N เป็นคำตอบครับ

อีกวิธีที่น่าสนใจพอกันคือ ให้ s(N) แทนจำนวนคนโดยเฉลี่ยของแถวยาว N ที่สามารถพูดว่า "ทุกคนที่อยู่หน้าฉันเตี้ยกว่าฉันทุกคน" ได้ ดังนั้น s(N-1) คือจำนวนคนโดยเฉลี่ยของแถวยาว N-1 เมื่อเราเอาคน 1 คนไปต่อท้ายแถวยาว N-1 จะได้แถวยาว N และโอกาสที่คนคนนั้นจะเป็นคนที่สูงที่สุดเท่ากับ 1/N ตั้งเป็นสมการ

s(N) = s(N-1) + 1/N

สมการนี้อาจหาโดยวิธี induce จากกรณี 2 คน 3 คน 4 คน ไปจนถึง N คนได้ แล้วหาผลรวมอนุกรมธรรมดานะครับ เรารู้ว่า s(0) = 0 (แถว 0 คนคงไม่มีใครพูดได้หรอกนะ) s(1) = 1 = s(0) + 1/1 = 1 สุดท้ายผลลัพธ์ที่ได้ s(N) = ฮาร์โมนิกนัมเบอร์อันดับที่ N เป็นคำตอบเช่นกัน






 

Create Date : 29 เมษายน 2551    
Last Update : 29 เมษายน 2551 16:49:46 น.
Counter : 2333 Pageviews.  

เมื่อลอร์ดโวลเดอร์มอต์กับโยดาแข่งกันถอดรหัส

ใน bloggang เรามีนักคณิตศาสตร์ที่ปราดเปรื่อง 2 ท่าน หนึ่งคือคุณลอร์ดโวลเดอร์มอต์ อีกหนึ่งคือ อ. โยดา ทั้ง 2 ท่านแข่งกันถอดรหัสตัวเลขค่าหนึ่ง ซึ่งเป็นจำนวนเต็มบวกที่น้อยกว่า 60 ด้วยเทคนิคบางอย่างแต่ละท่านมีข้อมูลลับของตัวเลขตัวนั้นคนละนิดคนละหน่อย คุณลอร์ดโวลเดอร์มอต์ รู้ว่าหลักหน่วยของตัวเลขที่เป็นรหัสนั้นคือเลขอะไร ส่วน อ. โยดา รู้ว่ามีจำนวนที่หารเลขรหัสลงตัวอยู่กี่ตัว (โยดารู้ว่าโวลดี้รู้เลขหลักหน่วย และโวลดี้รู้ว่าโยดารู้จำนวนตัวเลขที่หารเลขรหัสลงตัว แต่ทั้งคู่ไม่รู้อย่างเจาะจงลงไปว่าอีกฝ่ายรู้เลขอะไร) หลังจากแข่งขันกันนานวันก็ไม่มีใครพบคำตอบสักที สุดท้ายทั้ง 2 ท่านจึงหันหน้ามาร่วมมือกัน

เช้าอากาศแจ่มใสวันหนึ่ง...

ลอร์ดโวลเดอร์มอต์ "โยดี้ยังถอดรหัสไม่ได้ใช่มั้ยล่ะ"

ทำเป็นแสร้งถามไปงั้นแหละครับ (เชื่อผมเถอะ) เพราะจริง ๆ แล้วคุณโวลเดอร์มอต์ เองแกก็มั่นใจว่าถ้าแกถอดไม่ได้ โยดี้ หรือ อ. โยดา ก็ต้องถอดไม่ได้

ลอร์ดโวลเดอร์มอต์ "ผมก็ถอดไม่ได้เหมือนกัน แต่ผมรู้ว่าเลขรหัสของเราสามารถหารด้วยจำนวนเฉพาะอย่างน้อย 2 ตัวได้ลงตัว"

อ. โยดา แอบยิ้มในใจ "อ้อ... งั้นเหรอ... ฉันรู้คำตอบแล้วล่ะ"

ลอร์ดโวลเดอร์มอต์ก็ไม่น้อยหน้า "ชั้นก็รู้เหมือนกัน"

นักคณิตศาสตร์แห่ง bloggang ทั้ง 2 ท่านนี้พูดจริงเสมอครับ แล้วคุณล่ะ รู้รึยังว่าเลขรหัสนั้นคือเลขอะไร

ไม่ยากครับ เพราะโจทย์บอกข้อมูลมาครบหมดแล้ว เราต้องตอบคำถามให้ได้ว่า เหตุใดโวลดี้จึงรู้ว่าเลขรหัสหารด้วยจำนวนเฉพาะอย่างน้อย 2 ตัวได้ลงตัว นั่นก็เป็นเพราะเขารู้ว่าหลักหน่วยคือ 0 (หากหลักหน่วยเป็นเลขอื่น เขาย่อมไม่กล้าฟันธงพูดเช่นนั้นเพราะยังมี 11, 32, 13, 64, 25, 16, 17, 8, 19 เป็นต้น) โยดาจึงรู้ว่าแคนดิเดทมีเพียง 10, 20, 30, 40, 50 เมื่อรวมกับสิ่งที่เขารู้ว่าจำนวนตัวเลขที่หารรหัสลงตัวย่อมสามารถนำไปสู่ข้อสรุปได้

10 มีตัวประกอบคือ 1 2 5 10 มี 4 ตัวที่หาร 10 ลงตัว
20 มีตัวประกอบคือ 1 2 4 5 10 20 มี 6 ตัวที่หาร 20 ลงตัว
30 มีตัวประกอบคือ 1 2 3 5 6 10 15 30 มี 8 ตัวที่หาร 30 ลงตัว
40 มีตัวประกอบคือ 1 2 4 5 8 10 20 40 มี 8 ตัวที่หาร 40 ลงตัว
50 มีตัวประกอบคือ 1 2 5 10 25 50 มี 6 ตัวที่หาร 50 ลงตัว

เมื่อโยดาพูดว่าเขารู้ว่าเลขรหัสคืออะไร นั่นคือเลขที่โยดารู้ตอนแรกได้แก่ 4 ทำให้โวลดี้สามารถใช้ตรรกะเช่นเดียวกันคิดได้ว่ารหัสนั่นคือเลข 10 ครับ






 

Create Date : 28 เมษายน 2551    
Last Update : 29 เมษายน 2551 1:25:25 น.
Counter : 1860 Pageviews.  

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

เราทำการทดสอบกลุ่ม 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 น.
Counter : 2180 Pageviews.  

สามเหลี่ยมปาสคาล

มีอะไรหลายอย่างซุกซ่อนอยู่ในสามเหลี่ยมปาลคาล มันเริ่มจากโจทย์ข้อหนึ่งซึ่งมีคนโพสต์ไว้ทางอินเทอร์เนตในเว็บบอร์ดห้องหว้ากอของ pantip.com โหดใช้ได้เลยทีเดียวครับ ระหว่างที่คิดไปคิดมาอยู่เป็นชั่วโมงก็พบคุณสมบัติบางประการที่น่าสนใจของสามเหลี่ยมปาสคาล จึงนำมาเล่าสู่กันฟัง ขอเริ่มจากสามเหลี่ยมปาสคาลแล้วค่อยย้อนกลับไปหาโจทย์ก็แล้วกัน


ตอนเรียน ม. ต้น ม. ปลายคงนึกออกเพราะเราใช้มันช่วยหาสัมประสิทธ์ของการกระจาย (x + y)n ถ้าเรียกแถวที่เป็นยอดบนสุดของสามเหลี่ยมว่าแถวที่ n = 0 และแถวถัดมาว่า n = 1, 2, ... เรียงต่อไปเรื่อย ๆ แบบนี้ แถวที่ n = 4 ก็คือ 1 4 6 4 1 แล้วนำตัวเลขแต่ละแถวมาเรียงใหม่เป็น 3 แถว ดังนี้

n = 0; 1
1
0
0

n = 1; 1 1
1
1
0

n = 2; 1 2 1
1
2
1

n = 3; 1 3 3 1
1 1
3
3

n = 4; 1 4 6 4 1
1 4
4 1
6

n = 16;
1 560 8008 11440 1820 16
16 1820 11440 8008 560 1
120 4368 12870 120


จากการสังเกตเราพบว่า เมื่อเรียงแบบใหม่นี้แล้ว ถ้านำเลขแต่ละแถวมารวมกัน จะมี 2 แถวที่ได้ผลรวมเท่ากันเสมอ ผมขอเรียก 2 แถวนี้ว่าแถวพันธมิตรนะครับ ส่วนอีกแถวที่เหลือจะมีผลรวมน้อยกว่าหรือมากกว่าแถวพันธมิตรอยู่ 1 เสมอ ซึ่งผมขอเรียกว่าแถวโดดเดี่ยว (ใครจะลองนำไปพิสูจน์ดูก็ดีครับ ผลตรงนี้มาจากการสังเกตอย่างเดียว) เมื่อลองเขียนเล่น ๆ แบบนี้จนพบความสัมพันธ์ระหว่างแถวพันธมิตรกับแถวโดดเดี่ยวจึงเกิดคำถามขึ้นว่า เมื่อไรแถวโดดเดี่ยวจะมีผลรวมมากกว่าแถวพันธมิตรและเมื่อไรจะน้อยกว่า จากการสังเกตได้คำตอบว่ามันขึ้นอยู่ที่ค่า n ถ้า n = 3j หรือ n = 3j + 2 (เมื่อ j = 0, 1, 2, ...) แถวโดดเดี่ยวจะมากกว่าแถวพันธมิตรถ้า j เป็นจำนวนคู่ แต่จะน้อยกว่าถ้า j เป็นจำนวนคี่ และตรงกันข้ามถ้า n = 3j + 1 ตัวอย่างเช่น n = 6 เราเขียนเรียงใหม่

1 20 1
6 15
15 6

แถวพันธมิตรคือ 6 15 กับ 15 6 มีผลรวมเท่ากันเท่ากับ 21 ส่วนแถวโดดเดี่ยวคือ 1 20 1 มีผลรวมเท่ากับ 22 กรณีนี้ n = 3j เมื่อ j คือ 2 เป็นจำนวนคู่ ผลรวมแถวโดดเดี่ยวมากกว่าผลรวมแถวพันธมิตรอยู่ 1 คุณสมบัติที่น่าสนใจนี่แหละครับที่ช่วยหาคำตอบให้กับโจทย์ปัญหา combinatorics ที่กล่าวถึงในตอนแรกได้



สิ่งที่โจทย์ให้หาคือ C(2008,2) + C(2008,5) + C(2008,8) + ... + C(2008,2006) ขอเขียนแทนด้วย C3k+2 และเรารู้จากทฤษฎีการกระจายสัมประสิทธิทวินามว่า

C(2008,0) + C(2008,1) + C(2008,2) + ... + C(2008,2008) = 22008

สิ่งที่โจทย์ให้หาเป็นผลรวมของ subsequence หนึ่งใน 22008 อาจเขียนแทนด้วย

22008 = A3k + B3k+1 + C3k+2

เมื่อ

A3k = C(2008,0) + C(2008,3) + C(2008,6) + ... + C(2008,2007)
B3k+1 = C(2008,1) + C(2008,4) + C(2008,7) + ... + C(2008,2008)
C3k+2 = C(2008,2) + C(2008,5) + C(2008,8) + ... + C(2008,2006)

ตรงนี้มันก็คือการเขียนแถวที่ n = 2008 = 3(669) + 1 ของสามเหลี่ยมปาสคาล โดยมีแถว C3k+2 เป็นแถวโดดเดี่ยว และอยู่ในแบบ n = 3j + 1 เมื่อ j เป็นจำนวนคี่ หรือแถวโดดเดี่ยวมีผลรวมมากกว่าแถวพันธมิตรอยู่ 1 ดังนั้นถ้าเราให้แถวพันธมิตรมีผลรวมเท่ากับ x เราสามารถเขียนสมการง่าย ๆ ได้ว่า

22008 = x + x + x + 1

ได้ x = (22008 - 1)/3 หรือ C3k+2 = x + 1 = (22008 + 2)/3





 

Create Date : 25 เมษายน 2551    
Last Update : 26 เมษายน 2551 13:48:28 น.
Counter : 6018 Pageviews.  

ปัญหาทอยลูกเต๋า

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



เราอาจเริ่มต้นจากการคิดง่าย ๆ กรณีที่ค่า N น้อย ๆ ที่ N = 1 คนโยนก่อนชนะแน่นอน ที่ N = 2 คนแรกมีโอกาสชนะ 3/4 ที่ N = 3 คนแรกมีโอกาสชนะ 19/27 หรือถ้าเราจับตามองโอกาสแพ้ของคนแรก จะได้โอกาสเท่ากับ 0, 1/4, 8/27 ที่ N = 1, 2, 3 ตามลำดับ ถ้าใครอึดแจกแจงต่อกรณี N = 4 จะพบว่าโอกาสแพ้ของคนแรกเท่ากับ 81/256 แล้วเห็นว่าลำดับ 0, 1/4, 8/27, 81/256,... มีรูปแบบที่มองออกได้ไม่ยากนักคือ (1 - 1/N)N ผลจากการสังเกตทำให้เราตอบว่าโอกาสที่คนแรกชนะเท่ากับ 1 - (1 - 1/N)N ก็ได้ครับ และเป็นคำตอบที่ถูกซะด้วย แต่ต้องไม่ลืมว่าคำตอบนี้มาจากการสังเกตรูปแบบที่ได้จากการแจกแจงกรณี N ต่ำ ๆ แล้วนำไปสู่ความสัมพันธ์ของรูปแบบ N ใด ๆ ยังไม่ใช่การพิสูจน์ที่ถูกต้องยอมรับได้ในทฤษฎีความน่าจะเป็น ลองดูต่อไปครับ

ถ้าให้ Lr คือ โอกาสที่คนโยนคนต่อไปแพ้เมื่อหน้าลูกเต๋าล่าสุดออกแต้ม r ดังนั้นคนต่อไปจะชนะได้ก็ต่อเมื่อเขาหรือหล่อนต้องทอยเต๋าที่มีแต้มสูงกว่า r นั่นคือค่าใดค่าหนึ่งตั้งแต่ r+1 จนถึง N ซึ่งแต่ละหน้าพวกนี้ก็มีโอกาสเกิดเท่ากันเท่ากับ 1/N และคู่แข่งของหล่อนต้องได้แต้มน้อยกว่านั้นในการโยนครั้งต่อไป จึงพูดได้ว่าหล่อนมีโอกาสชนะเมื่อคู่แข่งทอยได้ r เท่ากับ 1-Lr = (1/N)Lr+1+(1/N)Lr+2+...+(1/N)LN

1-Lr = (Lr+1+Lr+2+...+LN)/N ... (1)

แทน r ใน (1) ด้วย r-1 ได้

1-Lr-1 = (Lr+Lr+1+...+LN)/N ... (2)

(2) - (1) ได้

Lr-1 = (1 - 1/N)Lr แทนความสัมพันธ์นี้ด้วย r ตั้งแต่ 1 ถึง N โดย LN = 1 เราได้ Lr = (1 - 1/N)N-r โอกาสชนะของผู้เล่นคนแรกก็คือ 1 - L0 (หนึ่งลบด้วยโอกาสแพ้เมื่อแต้มก่อนหน้าคือ 0) หรือ 1 - (1 - 1/N)N ตรงกับความสัมพันธ์ที่ได้จากการพิจารณารูปแบบของลำดับในตอนต้น

สังเกตพจน์ (1 - 1/N)N เมื่อ N เข้าสู่อนันต์มันก็คือค่าคงที่ e ดังนั้นกรณี N ใหญ่ ๆ เราอาจประมาณโอกาสชนะของผู้โยนคนแรกได้เท่ากับ 1 - 1/e หรือ 63.2% ส่วนกรณีลูกเต๋า 6 หน้าธรรมดานั้นโอกาสชนะของผู้โยนคนแรกเท่ากับ 1 - (5/6)6 หรือประมาณ 66.5%





 

Create Date : 22 เมษายน 2551    
Last Update : 22 เมษายน 2551 16:43:35 น.
Counter : 3686 Pageviews.  

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.