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 คนจัดอันดับหนุ่ม ๆ ในดวงใจ n คน หนุ่ม ๆ ทั้ง n คน ก็จัดอันดับสาว ๆ เช่นเดียวกัน David Gale กับ Lloyd Shapley นักคณิตศาสตร์เศรษฐศาสตร์ชาวอเมริกัน บอกเราว่าสามารถสร้างคู่ที่สมดุล (Stable) สำหรับทุกคนได้เสมอ คู่สมดุลหมายถึงคู่ที่ไม่มีคู่ใดแตกจากคู่ปัจจุบันเพื่อไปสร้างคู่ใหม่ เช่นมี 2 คู่ A-B กับ C-D แต่ B อยากจับคู่กับ C มากกว่า A และ C อยากจับคู่กับ B มากกว่า D แบบนี้ไม่สมดุล เพราะสุดท้ายคนที่รักกันก็ต้องวิ่งเข้าหากันจับคู่ B-C สำหรับ A-D ถึงแม้ A อยากคู่กับ B มากกว่า D แต่การจับคู่ A-D ก็ถือว่าสมดุล เพราะในกรณีที่มีกันอยู่ 4 คน A-D ไม่สามารถฉีกคู่ไปจับกับใครได้อีก ทฤษฎีที่อธิบายการมีคู่สมดุลนี้เรียก Stable Marriage Theorem หรือ Gale-Shapley Marriage Theorem

หลักการเรียบง่ายแต่ทรงพลัง คุณคงเคยดูซีรีย์เกาหลีเรื่อง Coffee Prince นะ สมมติว่าหนุ่มน้อยชเว ฮัน คยูล หมายปองศิลปินสาวสวยฮัน ยู จู และหล่อนเองก็ยังไม่มีคู่ เราจับคู่นี้เข้าด้วยกันก่อน (ยู จู, ฮัน คยูล) ปล่อยให้เขาดูใจกัน แต่ถ้าฮัน ยู จู มีคู่อยู่แล้วคือโปรดิวเซอร์ดนตรีสุดหล่อชเว ฮัน ซอง (ยู จู, ฮัน ซอง) ก็ต้องดูว่ายู จู เลือกใคร คนพี่ฮัน ซอง หรือคนน้องฮัน คยูล ถ้าเธอเลือกฮัน คยูล ก็จับคู่ใหม่ (ยู จู, ฮัน คยูล) นายฮัน ซอง ต้องตัดใจขีดฆ่าชื่อยู จู ออกจากลิสต์ แต่ถ้าเธอเลือกฮัน ซอง โดยการปฏิเสธอย่างนุ่มนวลกับฮัน คยูล ว่า "เราเป็นเพื่อนกันนะดีแล้ว" ให้คงคู่เดิมไว้ หนุ่มน้อยฮัน คยูล ก็ต้องตัดใจขีดฆ่าชื่อยู จู ออกจากลิสต์แล้วหันมามองเด็กข้างตัวอย่างโก อึน ชัน แทน



จากรูปลูกศรชี้จาก X พุ่งไปยัง Y หมายถึง Y คือคนที่ X หมายปอง เส้นทึบตีความว่าเป็นที่หมายปองมากกว่าเส้นประ สำหรับคนที่ไม่เคยดู Coffee Prince (ผมตั้งสมมติฐานไว้ 2 สาเหตุ 1. แก่จนพ้นวัยซีรีย์เกาหลี 2. ไม่มีแฟนบังคับให้ดู) ขอแนะนำตัวละครจากซ้ายไปขวา ฮัน ยู จู, ชเว ฮัน ซอง, ชเว ฮัน คยูล และ โก อึน ชัน คู่สมดลเขาก็ยืนเคียงกันตามรูปแล้วนะครับ

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

คำถามทางคณิตศาสตร์ที่น่าสนใจคือประเพณีเลือกคู่หนุ่มสาวนี้มีวันสิ้นสุดหรือไม่ ถ้ามี ผลสุดท้ายได้คู่ที่สมดุลจริงหรือ

พิสูจน์ได้ไม่ยากครับ สมมติว่าขณะนี้ได้พ้นวินาทีสุดท้ายในวันสุดท้ายของช่วงเวลาหาคู่เดทไปเรียบร้อยแล้ว และเหลือหนุ่มน้อยหนึ่งคนที่อยู่อย่างโดดเดี่ยวไม่ได้แต่งงาน หมายความว่าเขาขีดฆ่าชื่อผู้หญิงทุกคนในลิสต์หมดแล้ว แต่เป็นไปไม่ได้ที่ชายจำนวน n-1 คนจะแต่งงานแบบตัวต่อตัวกับหญิง n คน ฉะนั้นต้องมีหญิง 1 คนที่ยังไม่มีคู่ และหญิงคนนั้นย่อมไม่ส่งสายตา “ช่างไม่เจียม” ให้กับใครก็ตามที่เข้ามาจีบ (กรณีไร้คู่หล่อนต้องเจียมหากมีตัวเลือกแค่เพียงหนึ่ง) ขัดแย้งกับตอนต้นที่ว่าหนุ่มน้อยขีดฆ่าชื่อผู้หญิงทุกคนในลิสต์ ดังนั้นเป็นไปไม่ได้ที่จะพ้นวินาทีสุดท้ายในวันสุดท้ายของการเลือกคู่โดยที่ยังเหลือคนไม่มีคู่ สรุปประเพณีเลือกคู่หนุ่มสาวนี้มีวันสิ้นสุด ได้แต่งงานกันทั้ง n คู่ สมมติคู่แต่งงาน n คู่ มี 2 คู่คือ X-x กับ Y-y เป็นไปได้หรือไม่ที่ X-x กับ Y-y จะไม่สมดุลเพราะมีคู่ X-y ที่เหมาะสมกว่า คำตอบคือเป็นไปไม่ได้ครับ เพราะหาก X ต้องการแต่งงานกับ y เขาก็ต้องเลือก y ก่อน x แต่ที่ไม่มีคู่แต่งงาน X-y เป็นเพราะ y ปฏิเสธ X หรืออาจจะเคยเลือก X แต่ทิ้ง X ในรอบที่ Z เดินเข้ามา ดังนั้นคู่แต่งงานทุกคู่เป็นคู่ที่สมดุล

ประเพณีหาคู่เดทหนุ่ม-สาวเพื่อให้ได้คู่สมดุลเขียน Pseudo Code แล้วหน้าตาออกมาเป็นแบบนี้



ในเมื่อเราพูดเรื่องจับคู่แล้ว เพื่อความเป็นธรรมลองพิจารณากรณีคู่ชายรักชาย หญิงรักหญิง หรือคู่หญิงก็ได้ชายก็ดีดูกันหน่อยดีไหม ปัญหาคือในกลุ่มที่ไม่สนใจเพศ n คน เมื่อ n เป็นจำนวนคู่ สามารถมีคู่ที่สมดุลได้เช่นเดียวกับคู่หนุ่มสาวหรือไม่

ตัวอย่างรักใคร่ในร้าน Coffee Prince (เหตุการณ์สมมติของเหตุการณ์สมมตินะครับ ใครปลื้มเรื่องนี้มาก อย่าเคืองผมก็แล้วกัน) พนักงานหนุ่ม 3 คนชิน ฮา ริม, โร ซุน กี กับ วาง มิน ยอบ และเจ้านายชเว ฮัน คยูล แอบปิ๊งปั๊งกันเอง แต่ละคนก็มีอันดับหนุ่มฮ็อตของตัวเองอยู่ในใจ ผมให้เจ้านายฮัน คยูลมีเรตติ้งต่ำสุดก็แล้วกั



ตัวเลขที่อยู่ใกล้ใครหมายถึงคนนั้นจัดอันดับให้คนที่ลูกศรชี้เป็นลำดับที่เท่าไร เช่น ฮัน คยูล (ผูกเนคไท) เลือกฮา ริม (อ้าปาก) เป็นหมายเลข 1 ซุน กี (ผูกผม) เป็นหมายเลข 2 และมิน ยอบ (ผมสั้น) เป็นหมายเลข 3 แต่ทั้งสามคนเลือกฮัน คยูล เป็นคนสุดท้าย และทั้ง 3 คนก็สร้างความสัมพันธ์รักแบบงูกินหาง ฮา ริม แอบชอบ ซุน กี ซุน กี แอบชอบ มิน ยอบ มิน ยอบ แอบชอบ ฮา ริม ตัวอย่างนี้แสดงให้เห็นว่าไม่มีคู่สมดุล (ไม่มี Stable Buddy Matching)

พิสูจน์ได้โดยใช้ความขัดแย้ง ถ้ามีคู่สมดุลจากการจับคู่ไม่สนใจเพศ และมีคู่สมดุลจากรักสามเหลี่ยมงูกินหาง สมมติว่าฮา ริม กับ ซุน กี ดังนั้นสองคนที่เหลือคือมิน ยอบ กับ ฮัน คยูล ก็ต้องเป็นคู่กัน แต่มิน ยอบ กับ ฮัน คยูล ไม่อาจเป็นคู่สมดุล เพราะ ซุน กี ต้องการมิน ยอบ มากกว่าฮา ริม และมิน ยอบ เองก็ต้องการซุน กี มากกว่าฮัน คยูล ไม่ว่าเราจะใช้คู่ใดในรักสามเหลี่ยมงูกินหางเป็นคู่ที่สมดุล คุณจะพบว่าสุดท้ายแล้วมันไม่สมดุล ตรงนี้ไม่เหมือน “รัก|สาม|เศร้า” ของยุทธเลิศที่มีทั้งความมีน้ำใจและน้ำเน่าแบบไทย ๆ สามเพื่อนรัก ฟ้า น้ำ พายุ มีความสัมพันธ์ น้ำแอบรักพายุ พายุแอบรักฟ้า เมื่อฟ้าเปิดใจให้พายุ พบว่าพายุคือคนที่น้ำรัก ตัวเองก็หลบฉากไปเพราะยังไง ๆ ตัวเองก็ป่วยใกล้ตาย กลยุทธ์แบบนี้เสียหายทั้ง 3 ฝ่าย ทั้ง ๆ ที่มันมีคู่สมดุลคือฟ้ากับพายุ ยิ่งพบว่าตัวเองใกล้ตายยิ่งต้องรีบแต่งงานเป็นคู่สมดุลแรก พอตายไปเดี๋ยวเราจะได้คู่สมดุลที่สองคือพายุกับน้ำ Happy Ending ครับ แต่ในกรณีรักสามเหลี่ยมงูกินหางเกิดเพราะแต่ละเหลี่ยมแต่ละคนงัดกลยุทธ์เด่นมาเล่นกัน แต่ละคนจะมีทั้งคนที่เรารักและคนที่รักเราอยู่ในสามเหลี่ยม (และคนที่เรารักน้อยที่สุดอยู่นอกสามเหลี่ยม) นั่นคือเมื่อไรก็ตามที่มีคู่เกิดจากสามเหลี่ยม อีกคนสามารถทำลายคู่นั้นได้โดยยื่นข้อเสนอให้คนที่รักเราแทนที่จะยื่นข้อเสนอให้คนที่เรารัก




Create Date : 31 กรกฎาคม 2551
Last Update : 12 กันยายน 2551 12:25:31 น. 4 comments
Counter : 1605 Pageviews.

 
แวะมาเจิมสงกาสัยว่าดวงคู่คงทนเราไม่มีแน่ๆ
อิอิอิ


โดย: อุ้มสี วันที่: 1 สิงหาคม 2551 เวลา:0:33:55 น.  

 
เข้าใจเอา coffee prince มา
5555 แต่พรายทรายอ่านแล้วงงเต๊กเลย
หือ หือ

เอาทฤษฎีจับคู่แบบนี้
ไปให้หนูเภตราที่บล็อกพี่อ้อ น่าจะเหมาะ
เอ หรือว่าให้นายเมษาดีละนี คู่คงทนแบบนี้
นายนี่จะเลือกใครแน่

โอ๊ย พยายามอ่านอิกทีก็งงยิ่งมาก
เฮ้อออออ ไม่มีหัวขมองทางคณิตศาสตร์จริง ๆ เล้ยยย


โดย: พรายทราย วันที่: 1 สิงหาคม 2551 เวลา:18:16:34 น.  

 
มาปวดหัวอีกรอบ
แต่ถ้ามี 3 คู่ 6 คน แล้วจะทำยังไง


โดย: พรายทราย วันที่: 2 สิงหาคม 2551 เวลา:19:48:30 น.  

 
ปวดหัวตลอดอ่ะ


โดย: เจ้าชายไร้เงา วันที่: 20 สิงหาคม 2551 เวลา:16:21:15 น.  

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