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

ในการคิดปัญหาข้อนี้ก่อนอื่นเราอาจต้องสร้างโมเดลที่เข้าใจได้ง่ายกว่าการ์ดในถุงขนม ลองดูโมเดลนี้ครับ สมมติว่ามีลูกปิงปอง n ลูก n สี สีละลูกอยู่ในกล้องปิดทึบ คุณล้วงมือเข้าไปหยิบลูกปิงปองอย่างสุ่มขึ้นมาทีละลูก แล้วจดสีลูกปิงปองที่คุณหยิบได้ จากนั้นใส่ลูกปิงปองคืนกลับลงไปในกล่อง แล้วล้วงครั้งที่ 2 ทำแบบนี้ไปเรื่อย ๆ จนกว่าคุณจะจดได้ครบทั้ง n สี จำนวนครั้งที่คุณล้วงหยิบลูกปิงปองโดยเฉลี่ยจนกระทั่งได้ครบทุกสีเท่ากับกี่ครั้งจะเทียบได้กับปัญหาการ์ดในถุงขนมใช่มั้ยครับ?



อันที่จริงก็ไม่ใช่นะ ไม่ถูกเสียทีเดียว โมเดลที่ผมยกตัวอย่างมานี้ไม่อาจเทียบเท่ากับปัญหาการ์ดในถุงขนมได้เป๊ะ ๆ ครับ ทำไม? สมมติเราตัดประเด็นว่าบริษัทเล่นไม่แฟร์ผลิตการ์ดแบบหนึ่งน้อยกว่าปกติ การ์ดรูปอื่นผลิต 10,000 ใบ แต่การ์ดรูปหัวใจผลิต 10 ใบ ทำให้การ์ดรูปหัวใจมีค่ามากกว่าการ์ดรูปอื่นเพราะเป็นของหายาก โอกาสที่คุณจะสะสมได้ครบทีนี้ดันไปขึ้นอยู่กับโอกาสได้การ์ดรูปหัวใจ ยังมีประเด็นอื่นอีก เมื่อมีคนซื้อขนม จะทำให้ความน่าจะเป็นที่จะได้การ์ดแต่ละใบไม่คงที่ เปลี่ยนแปลงตามโอกาสของคนอื่น ๆ ที่ซื้อขนม เพื่อขจัดปัญหาดังกล่าวเราจะสมมติว่าบริษัทมี demon machine เครื่องผลิตและบรรจุการ์ดที่สามารถรักษาให้โอกาสการได้การ์ดรูปใด ๆ เท่ากันและเท่าเดิมตลอดเวลา ภายใต้เงื่อนไข demon machine ของเรา โมเดลลูกปิงปองในกล่องกับปัญหาการ์ดในถุงขนมก็จะเทียบเท่ากันพอดี

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



ดังนั้นจำนวนครั้งที่หยิบโดยเฉลี่ย (ค่าคาดหมาย) ที่เราจะหยิบลูกปิงปองได้ครบทั้ง n สี อย่างน้อยสีละหนึ่งครั้ง เท่ากับ



พจน์ในวงเล็บซ้ายมือสุดคือ Hn จำนวนฮาร์โมนิกอันดับที่ n ประมาณเท่ากับ ln(n) [คุณอาจประมาณมันโดยอินทิเกรต (1/x)dx ค่า x จาก 1 ถึง n] ดังนั้นค่าเฉลี่ยของจำนวนถุงขนมที่ต้องซื้อเพื่อให้ได้การ์ดครบทุกแบบเท่ากับ nHn


Create Date : 12 ตุลาคม 2552
Last Update : 12 ตุลาคม 2552 14:13:36 น. 0 comments
Counter : 1761 Pageviews.

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