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 น. 0 comments
Counter : 2310 Pageviews.

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