creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
ความพึงพอใจสูงสุดของลอร์ดโวลเดอร์มอต์

โจทย์ข้อนี้ผมนำมาจากโจทย์แข่งขัน SMT 2008 การแต่งโจทย์แสดงความน่ารักของผู้แต่งได้ดีทีเดียว เขาว่า ในวันหนึ่ง ๆ ลอร์ดโวลเดอร์มอต์ทำแค่ 2 สิ่ง คือ สาปพวกมักเกิ้ลกับเตะลูกหมา มักเกิ้ลที่ถูกสาปนั้นมีโอกาสตาย 50% ในขณะที่ลูกหมาที่ถูกเตะนั้น ถูกเตะแน่นอน (ดาร์กลอร์ดของเราเตะลูกหมาสำเร็จทุกครั้งที่อยากเตะครับ แต่ฆ่าคนไม่สำเร็จทุกครั้งที่อยากฆ่า) ถ้ามักเกิ้ลตาย 1 คน ทำให้เขารู้สึกพอใจ 3 หน่วย เตะลูกหมา 1 ตัว ทำให้เขารู้สึกพอใจ 2 หน่วย และเมื่อครบ 1 วัน มีเกิ้ลตายเป็นจำนวนคู่คน เขาจะมีความพึงพอใจเพิ่มขึ้นเป็น 2 เท่าต่อศพของมักเกิลที่ตาย นั่นคือแต่ละศพให้ความพึงพอใจถึง 6 หน่วย แต่ไม่ว่าเก่งกาจถึงเพียงไหนดาร์กลอร์ดของเราก็มีขีดความสามารถจำกัด ใน 1 ชั่วโมง เขาสามารถสาปมักเกิ้ล 1 คน หรือ เตะลูกหมา 1 ตัว อย่างใดอย่างหนึ่งเท่านั้น คำถามคือ เขาควรปันเวลาเตะลูกหมากี่ตัว สาปมักเกิ้ลกี่คน เพื่อให้มีค่าคาดหมายของความพึงพอใจสูงสุด



ทริ๊กของมันอยู่ที่ เมื่อไรเราจึงพูดว่าโวลดี้สาปคนได้เป็นจำนวนคู่ หรือสาปคนได้เป็นจำนวนคี่ เราต้องดูผลลัพธ์จากคนสุดท้ายในวันนั้นที่ถูกสาปถูกมั้ยครับ ซึ่งคน ๆ นั้นนะมีโอกาสเป็นเท่ากับโอกาสตาย 50-50 ดังนั้นโอกาสที่ดาร์กลอร์ดโวลดี้สาปคนแล้วตายจำนวนคู่เท่ากับโอกาสที่สาปคนแล้วตายเป็นจำนวนคี่ ถ้าในวันนั้นโวลดี้สาป n คน เราเขียน En แทนค่าคาดหมาย (expected value) ของศพมักเกิ้ลที่สุดท้ายแล้วเป็นจำนวนคู่ และ On แทนค่าคาดหมายของศพมักเกิ้ลที่สุดท้ายแล้วเป็นจำนวนคี่ ในกรณีที่โวลดี้สาป n คน ค่าคาดหมายของศพคือ n/2 มันก็คือค่าเฉลี่ยของ En กับ On ดังนั้น En + On = n แบ่งเป็น 2 กรณีคือ n = 2k และ n = 2k+1 เมื่อ k เป็นจำนวนเต็ม ในกรณีที่ n = 2k เรารู้ว่าโอกาสมีศพของมักเกิ้ลจำนวน k-i ศพ เท่ากับ โอกาสมีศพของมักเกิ้ลจำนวน k+i ศพ เมื่อ i เป็นจำนวนเต็ม ดังนั้น En = k ส่วนกรณี n = 2k+1 เราจะได้ En = (En-1 + [On-1+1])/2 มันก็คือค่าเฉลี่ยของ En-1 (โวลดี้สาป n-1 คนแล้วคาดหมายว่าตายเป็นจำนวนคู่ En-1 คน และคนสุดท้ายที่ถูกสาป คือคนที่ n ไม่ตาย) กับ On-1+1 (โวลดี้สาป n-1 คนแล้วคาดหมายว่าตายเป็นจำนวนคี่ On-1 คน และ +1 คนสุดท้ายหรือคนที่ n ตาย) ก็จะได้ En = n/2

จึงเป็นข้อสรุป ไม่ว่า n เป็นเท่าไรก็ตาม En = On = n/2 ดังนั้นเมื่อดาร์กลอร์ดโวลดี้สาปมักเกิ้ล n คน โวลดี้จะมีค่าคาดหมายของความพอใจเท่ากับ (3On + 6En)/2 = 9n/4 = 2.25n ในขณะที่โวลดี้เตะลูกหมา n ตัว จะได้ความพึงพอใจเพียง 2n เมื่อเป็นดังนี้ โวลดี้ของเราจึงเลิกสนใจลูกหมาแล้วหันมาสาปมักเกิ้ลมันทั้งวันเลยครับ นั่นคือสาปมักเกิ้ล 24 คน จะคาดหวังความพึงพอใจได้ 54 หน่วย





Create Date : 21 เมษายน 2551
Last Update : 21 เมษายน 2551 21:19:33 น. 0 comments
Counter : 987 Pageviews.

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