creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
ปัญหา Josephus กรณี m = 2

สมมติว่าคุณได้รับเชิญให้เล่นเกมที่มีเงินเดิมพันสูงลิบลิ่ว ประมาณว่าใครชนะครองโลกเป็นเจ้ายุทธภพเลยละกัน คุณเป็นหนึ่งใน 11 คนที่ร่วมเล่นเกม พวกคุณทั้ง 11 ยืนจับมือล้อมรอบเป็นวงกลม จากนั้นเพชฌฆาตซึ่งมีขวานเป็นอาวุธจะไล่ทุบหัวคนในวง โดยเขาจะละเว้น 1 คน (เริ่มจากคนแรก หมายเลข 1) จากนั้นทุบ 1 คน (หมายเลข 2) และละเว้น 1 คน (หมายเลข 3) ทุบ 1 คน (หมายเลข 4) เช่นนี้ไปเรื่อย ๆ จนกว่าจะเหลือคนสุดท้าย คุณจะเลือกยืนอยู่ตำแหน่งไหนเพื่อให้เป็นคนสุดท้ายครับ ให้ถือว่าอีก 10 คนที่เหลือซึ่งเป็นผู้ท้าชิงโง่มาก โง่ชนิดไร้คำบรรยาย ยืนให้เขาทุบหัวเอาฟรี ๆ เพราะคิดว่าตัวเองจะรอดเป็นเจ้าโลก

ถ้าคุณมีเวลาคิดสักเล็กน้อย คุณจะพบว่าปัญหาข้อนี้หาคำตอบพบง่ายมาก คุณก็แค่วาดตำแหน่งทั้ง 11 คนแล้วไล่จำลองเหตุการณ์เลียนแบบพฤติกรรมของอีตาเพชฌฆาตซะก็จบ (อ้อ ผมไม่ต้องบอกคุณก็คงเดาได้ว่าเพชฌฆาตคนนี้เดินทักษิณาวรรตมิใช่อุตราวรรตนะครับ) คุณเริ่มไล่รอบแรกดังรูป 2 ตาย, 4 ตาย, 6 ตาย, 8 ตาย, 10 ตาย


จากนั้นเริ่มรอบที่สอง 1 ตาย, 5 ตาย 9 ตาย และรอบสุดท้าย 3 ตาย, 11 ตาย ตำแหน่งที่รอดคือหมายเลข 7



ปัญหาที่ถามว่าใครคือคนที่รอดเป็นคนสุดท้ายนี่แหละครับเรียกว่า ปัญหา Josephus กรณีตัวอย่างที่ผมยกมานี้เราเรียกว่า Josephus ที่ n = 11 (มีคนเล่นทั้งหมด 11 คน) และ m = 2 (นับ 2 แล้วฆ่า) ถ้าเราเปลี่ยนกติกาใหม่ โดยเพชฌฆาตนับ 3 แล้วฆ่า หมายความว่า m = 3 ลำดับการตาย ก็เริ่มจาก 3, 6, 9, 1, ... (ใครรอดคุณคิดต่อเองได้) สมมติว่าคนที่รอดจาก Josephus (n,m) คือ L(n,m) ในตอนนี้เราจะลองมาหาค่า L(n,2) กันครับ

ในการหา L(n,2) เราแบ่งค่า n ออกเป็น 2 กรณี คือ (1.) n สามารถเขียนให้อยู่ในรูป 2 คูณกัน k ตัว หรือ n = 2k หรือพูดว่า log2n เป็นจำนวนเต็ม และ (2.) log2n ไม่เป็นจำนวนเต็ม หรือ n = 2k + w เมื่อ 0 < w < 2k < n (เหตุผลว่าทำไมเราจึงแบ่งเป็น 2 กรณีเช่นนี้ฝากคิดเป็นการบ้านนะครับ) ในกรณีแรกนั้นหมายเลข 1 รอด เพราะถ้า n = 2k เพชฌฆาตต้องฆ่า k รอบ แต่ละรอบคนก็หายไปครึ่งหนึ่งของรอบที่แล้ว รอบสุดท้ายเหลือ 2 คน คือหมายเลข 1 กับ หมายเลข (n/2)+1 เอาล่ะ แม้มันจะมองออกง่าย ๆ ในกรณีที่หนึ่งนี้ แต่ถ้าเราอยากจะเขียนพิสูจน์ เราจะเขียนยังไงดีครับ? สมมติว่าเราจะลองใช้อุปนัยเชิงคณิตศาสตร์ สิ่งที่เราจะต้องทำคือพิสูจน์ว่า k = 1 เป็นจริง และ ถ้า k เป็นจริงแล้ว k+1 เป็นจริง กรณี k = 1 หรือ n = 2 คนแรกรอด เป็นจริง คราวนี้ถ้า 2k คน คนที่รอดคือคนแรก สำหรับ 2k+1 คน จะมีคนมากกว่า 2k คน 2 เท่า เมื่อเพชฌฆาตฆ่าคนรอบแรก จะฆ่าคนหมายเลขคู่ทั้งหมดทิ้ง ทำให้เหลือ 2k คนโดยเริ่มนับ 1 ที่คนแรกเหมือนเดิม ดังนั้นผลลัพธ์จึงเหมือน 2k เป็นอันสิ้นสุดการอุปนัยสำหรับกรณีที่หนึ่ง

กรณีที่สอง log2n ไม่เป็นจำนวนเต็ม หมายความว่าเราสามารถเขียน n ให้อยู่ในรูป n = 2k + w ได้โดย w มีค่าระหว่าง 0 ถึง 2k (ถ้า w เป็น 0 พอดี หรือเป็น 2k พอดี มันจะกลายเป็นกรณีแรกที่ n = 2k กับ n = 2k+1 ตามลำดับ ถูกมั้ยครับ) ถ้าเรากำจัด w คนนี้ออกไปก่อน คนที่เหลือจะกลายเป็นกรณีที่หนึ่ง ในการกำจัด w คนแรกออกไป คนที่มีหมายเลขคู่ตั้งแต่ 2 จนถึง 2w จะถูกมือขวานทุบตายเป็นอันดับแรก ฉะนั้นคนที่รอดก็ได้แก่หมายเลข 2w + 1

ลองพิจารณาคำตอบทั้ง 2 กรณี เราพบว่ามันรวมกันได้โดยขยายกรณีที่สอง n = 2k + w เป็นกรณีทั่วไปคือ ถ้า w = 0 มันก็จะกลายเป็นกรณีแรก ถ้า w ไม่เท่ากับศูนย์ มันก็คือกรณีที่สอง ฉะนั้น L(n,2) = 2w + 1 ซึ่งคุณเห็นว่า w มีความหมายหยุมหยิม เราจะแปลงเจ้า w ที่หยุมหยิมให้เป็น w ที่จิ้มลิ้มได้หรือไม่

ได้อยู่แล้วครับ จาก n = 2k + w หรือ w = n – 2k แล้ว k คืออะไร กรณีที่ w = 0 เราบอกว่า k คือจำนวนรอบที่เพชฌฆาตฆ่า และ n = 2k ฉะนั้น k = log2n ครั้นพิจารณาที่ w > 0 ค่าของ log2n ไม่เป็นจำนวนเต็ม จากความหมายของมัน k คือจำนวนเต็มที่มากที่สุดที่น้อยกว่า log2n ฉะนั้น k = floor(log2n) บางทีเราก็นิยมเขียน lg(n) แทน log2n นำไปแทนค่าได้สมการ

L(n,2) = 2(n – 2floor(lg(n))) + 1 = 1 + 2n – 21+floor(lg(n))

ถ้าลองแทนค่า n = 1, 2, 3, … เราจะได้ลำดับของ L(n,2) ที่มีรูปแบบ คือ 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, ... เลข 1 ตัวหนาคือกรณีที่หนึ่ง


Create Date : 29 กันยายน 2552
Last Update : 30 กันยายน 2552 20:11:52 น. 0 comments
Counter : 2042 Pageviews.

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