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 น.
Counter : 987 Pageviews.  

monty hall Problem

เป็นปัญหาคลาสสิกข้อหนึ่งทีเดียว ในการเล่นเกมที่มี 3 ตัวเลือก และมีรางวัลอยู่ 1 อันใน 3 ตัวเลือกนั้น ถ้าให้เลือกครั้งเดียว โอกาสถูกรางวัลย่อมเท่ากับ 1/3 ต่อมาหลังจากที่เราเลือก มีคนใจดีให้ข้อมูลเพิ่มเติม คือ บอกเราว่า ใน 2 ตัวเลือกที่เหลือนั้น ตัวไหนคือตัวที่ผิด เป็นอย่างนี้แล้วเราจะเปลี่ยนใจมั้ยครับ ?

หากดูเพียงผิวเผิน เหมือนกับเราเหลือ 2 ตัวเลือกที่มีโอกาสถูกเท่า ๆ กัน 50-50 ดังนั้นจะเปลี่ยนใจหรือไม่เปลี่ยนใจก็ไม่น่าจะมีผลอะไร แต่โดยทฤษฎีความน่าจะเป็นกลับบอกเราอีกอย่าง หากเปลี่ยนใจ เราจะมีโอกาสถูกมากถึง 2/3 ทีเดียว ฉะนั้นถ้าว่าในทางคณิตศาสตร์แล้วให้เราเปลี่ยนใจเสมอสำหรับเหตุการณ์แบบนี้ครับ (ดูรูปแจกแจงกรณีประกอบ)







 

Create Date : 21 เมษายน 2551    
Last Update : 21 เมษายน 2551 18:23:20 น.
Counter : 2128 Pageviews.  

โอกาสออกจากเขาวงกต

สมมติว่าเขาวงกต (ที่ไม่ค่อยซับซ้อนเท่าไร) มีลักษณะดังรูป



คุณเข้าไปทาง A และทุกครั้งที่เจอทางแยก คุณเลือกอย่างสุ่ม ด้วยโอกาสเท่า ๆ กันว่าจะไปทางซ้ายหรือขวาหรือหันหลังกลับ แต่ถ้าคุณพบทางออกแล้ว (A, B, C, D) คุณจะไม่ย้อนเข้าไปในเขาวงกตอีก โจทย์ข้อนี้ให้หาโอกาสที่คุณจะกลับออกมาจากทาง A ครับ (หรืออาจพูดว่า ให้หาโอกาสที่เข้าทางไหน ก็ออกทางนั้น)

ถ้าเราตั้งสมการเป็น ปัญหาข้อนี้สามารถแก้ได้ง่าย ๆ ด้วยการแก้ระบบสมการเชิงเส้นธรรมดา ๆ สมมติเรียกชื่อแยกว่า a, b, c, d ตามแยกที่เชื่อมกับทางเข้าออก A B C D ตามลำดับ เมื่อกำหนดให้ Px แทน โอกาสที่จะออกจากทาง A เมื่ออยู่แยก x, เราได้สมการ

Pa = (1/3)(1) +(1/3)Pb +(1/3)Pd
Pb = (1/3)(0) +(1/3)Pa +(1/3)Pc = Pd
Pc = (1/3)(0) +(1/3)Pb +(1/3)Pd

ได้ Pa = 7/15






 

Create Date : 19 เมษายน 2551    
Last Update : 21 เมษายน 2551 18:34:09 น.
Counter : 1255 Pageviews.  

แผ่นดินของเรา

สีม่วง แอนตาร์กติกา
สีเขียว อัฟริกา อาราเบียน-เพ็นนินซูลา
สีเหลือง ออสเตรเลีย นิวกีนี
สีฟ้าอ่อน ยุโรป เอเชีย อินโดเนเชีย
สีชมพู อินเดีย
สีฟ้า มาดากัสก้า
สีแดง อเมริกาเหนือ
สีน้ำเงิน อเมริกาใต้
เส้นที่เห็นคือเส้นอิเควเตอร์ (เส้นศูนย์สูตร)

510 ล้านปีที่แล้ว



410 ล้านปีที่แล้ว



320 ล้านปีที่แล้ว



260 ล้านปีที่แล้ว



220 ล้านปีที่แล้ว

ยุค Mesozoic/ Triassic/ Norian เข้าสู่ยุคไดโนเสาร์แล้วครับ ไตรอัสสิกนี่เป็นยุคเริ่มวิวัฒนาการไดโนเสาร์ก่อนจะไปสู่ยุคจูราสสิก



170 ล้านปีที่แล้ว

ยุคจูราสสิกไดโนเสาร์ครองโลก เคยดูจูราสสิก ปาร์คกันใช่มั้ยครับ จะมีเจ้า T.rex หรือ Tyrannosaurus rex แล้วก็พวกไดโนเสาร์กินพืชกลุ่ม Stegosaurus กับ Ankylosaurus ถ้าคนช่างจับผิดหน่อยจะต้องร้อง เอ๊ะ เพราะว่า Stegosaurus อยู่ยุคจูราสสิกจริง แต่เจ้า T.rex ต้องรออีกประมาณ 80 ล้านปี จึงจะถือกำเนิด เพราะมันอยู่ครองโลกอยู่ในปลายครีเตเชียส ดังนั้นเจ้า 2 ตัวนี้ไม่มีทางเคยพบหน้ากันมาก่อน ไม่ได้เกิดร่วมยุคกัน (ยกเว้นในหนัง)



100 ล้านปีที่แล้ว



50 ล้านปีที่แล้ว

ยุค Cenozoic บางทีถูกเรียกว่า ยุคแห่งสัตว์เลี้ยงลูกด้วยนมบ้าง ยุคแห่งพืชดอกบ้าง ยุคแห่งแมลงบ้าง ยุคแห่งปลามีกระดูกบ้าง หรือยุคแห่งนกบ้าง







 

Create Date : 16 เมษายน 2551    
Last Update : 16 เมษายน 2551 23:11:02 น.
Counter : 1600 Pageviews.  

a Knight's tour

The Knight's Tour Problem คือ ปัญหาการเดินอัศวิน (ม้าหมากรุก) บนกระดานหมากรุก เพื่อให้ม้าเดินครบทุกช่องโดยไม่ซ้ำช่องเดิม แล้วกลับมายืนยังจุดตอนเริ่มต้น นี่คือตัวอย่าง Euler's tour สำหรับกระดาน 8x8



ใช่ว่ากระดานทุกขนาดจะมี Knight's tour ตัวอย่างเช่นกระดานขนาด 4x4 ไม่มี tour (ลองหาคำตอบดูเองนะครับว่าทำไม?) เพื่อความสนุกและท้าทายความคิดยิ่งขึ้น กำหนดให้เรามีกระดานหมากรุกทรงลูกบาศก์ 2 x 2 x 2 เรามีช่องให้เดินม้าได้ทั้งหมด 24 ช่อง เนื่องจากแต่ละด้านของลูกบาศก์มีขนาด 2x2 ดังนั้นการเดินม้าจึงหลีกเลี่ยงไม่ได้ที่จะข้ามขอบของลูกบาศก์ เมื่อมีการข้ามขอบลูกบาศก์ รูปแบบการเดินม้าจึงขึ้นอยู่กับการคลี่ของกล่อง มีข้อที่เราควรทำความตกลงร่วมกันก่อนคือ ม้าสามารถเดินไปได้ทุกที่ที่สามารถคลี่กล่องแล้วไม่ผิดกฎการเดินม้า รูปด้านล่างขวามือ ผมแสดงตัวอย่างช่อง O ที่ม้าสามารถเดินได้ (บนกระดานปกติม้าสามารถเลือกเดินได้ไม่เกิน 8 ช่อง แต่บนกระดานพิสดารของเราอันนี้ม้าเลือกเดินได้ 10 ช่อง) คิดว่าตารางหมากรุกพิสดารอันนี้มี Knight's tour มั้ยครับ ถ้ามีคือเส้นทางใด?








 

Create Date : 28 มีนาคม 2551    
Last Update : 28 มีนาคม 2551 15:26:53 น.
Counter : 1478 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.