creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
ปัญหาการจัดกลุ่มโหวต

สมมติว่าจะมีการเลือกตั้งเลือกประธานาธิบดีในประเทศ x ซึ่งมีประชากร 20 ล้านเสียง โดยประธานาธิบดีคนปัจจุบัน y มีเสียงสนับสนุนจากประชาชนไม่ถึง 1 เปอร์เซ็นต์ ส่วนเสียงที่เหลือสนับสนุน z คู่แข่งคนสำคัญที่ลงชิงชัยในการเลือกตั้งครั้งหน้า

y ต้องการเป็นประธานาธิบดีอีกครับ (แน่นอนว่าตามแบบวิถีประชาธิปไตย - ใช้เสียงของประชาชนส่วนใหญ่เป็นตัวแทน...มั้ง) เธอก็คิดอะไรขึ้นมาได้อย่างหนึ่ง โดยเริ่มจากแบ่งเสียง 20 ล้านเสียงซึ่งมีสิทธิโหวตออกเป็น n1 กลุ่ม แต่ละกลุ่มมีคนเท่า ๆ กัน จากนั้นแบ่งคนจากแต่ละกลุ่มออกเป็น n2 กลุ่มย่อย แต่ละกลุ่มย่อยก็มีคนเท่า ๆ กัน และแบ่งแต่ละกลุ่มย่อยออกเป็น n3 กลุ่มย่อยลงไปอีก แบ่งย่อย ๆ แบบนี้ไปเรื่อย ๆ นะครับ โดยกลุ่มย่อยในอันดับที่ i ก็ใช้เสียงข้างมากเป็นตัวแทนกลุ่ม เพื่อเป็นตัวแทนโหวตในอันดับที่ i-1 (ถ้ามีคะแนนเสียงเท่ากันในแต่ละโหวต คุณ y เธอประกาศว่ายอมถือว่าตัวเองแพ้ z ในโหวตนั้น)

คำถามคือ ด้วยวิธีการนี้ y สามารถแบ่งกลุ่ม และกระจายเสียงที่สนับสนุนหล่อน เพื่อเอาชัยในการเลือกตั้งได้มั้ยครับ



โจทย์ข้อนี้เป็นปัญหาคลาสสิกยอดฮิตอีกข้อหนึ่งซึ่งมีคนเขียนเฉลยไว้หลายแบบ แบบหนึ่งที่ตรงไปตรงมา คือ ให้ N เป็นผลคูณของ non-trivial factor

N = Nk = n1 x n2 x n3 x ... x nk

ให้ mi = (ni/2) + 1

จำนวนผู้สนับสนุน Mk = m1 x m2 x m3 x ... x mk ก็เพียงพอให้ชนะการเลือกตั้ง พูดง่าย ๆ คือเราแบ่งคนออกเป็น Nk-1 กลุ่ม แต่ละกลุ่มมีขนาด nk แล้วแบ่งผู้สนับสนุนเป็น Mk-1 กลุ่ม กลุ่มละ mk ก็จะชนะโดยการเหนี่ยวนำขึ้นมาจากระดับ i สู่ i-1 ตัวอย่างตัวเลขจริง 20 ล้าน = 57 x 44 สามารถถูกเหนี่ยวนำโดย 37 x 34 = 177147 ซึ่งน้อยกว่า 1%





Create Date : 03 พฤษภาคม 2551
Last Update : 3 พฤษภาคม 2551 23:30:04 น. 0 comments
Counter : 912 Pageviews.

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