ลองจินตนาการชายฉกรรฉ์ 22 คนที่ไฟแรงพยายามแบ่งข้างเล่นฟุตบอล แต่ด้วยเพราะตกลงกันไม่ได้ว่าจะแบ่งยังไงให้ยุติธรรม เลยตัดสินใจใช้วิธีโอน้อยออก เริ่มจากกลุ่มคนที่ปรารถนาอย่างแรงกล้าที่จะเล่นฟุตบอล เมื่อการโอน้อยออกผ่านไป 38 ครั้งไม่สำเร็จซักที ก็ชักเริ่มสงบ “กูไม่เล่นก็ได้” “กูกลับไปนอนบ้านดีกว่า”
มันคือสัญญากับตัวเองว่าจะเขียนบทความนี้ “การโอน้อยออกหลักสูตรใหม่” หรือแบบใหม่นั่นเอง แต่ก็ปล่อยให้เวลาผ่านไปสิบกว่าปี เท่าที่จำได้ผมสอนเรื่องนี้กับลูกศิษย์ในวิชา computational mathematics คณิตศาสตร์การคณนา (ซึ่งแปลเป็นไทยแล้วไม่ช่วยอะไรเท่าไหร่) รุ่นแรกในปลายปี 2552 ต่อต้นปี 2553 แล้วก็สอนเรื่องนี้ในวิชานี้ทุกรุ่นจนถึงปัจจุบัน
เรื่องมันมีอยู่ว่าตอนเล่นบาสเก็ตบอลสมัยที่เรียน ป.เอกที่อเมริกาผมได้หาวิธีปรับปรุงวิธีการโอน้อยออกเพื่อแบ่งข้างคน 10 คน โดยให้เอาใครก็ได้ออกมารอคนหนึ่ง แล้วให้อีก 9 คนที่เหลือแบ่งข้างให้ได้ 4 กับ 5 ซึ่งมันมีโอกาสแบ่งข้างสำเร็จมากว่าเพราะจะเป็นคว่ำมือ 4 คนหรือคว่ำมือ 5 คนก็ได้ แล้วก็ให้กลุ่ม 4 คนไปรวมกับคนที่ออกมารอ แต่ตอนนั้นก็มีคนไม่ค่อยเชื่อว่ามันจะไม่เอนเอียงให้ใครไปอยู่กับคนที่ออกมารอ ตอนนั้นประมาณปี 2539-2541 จำไม่ได้ชัดๆว่าปีไหนกันแน่ ต้องถามคนไทยที่ไปเรียนที่ U. of Illinois at Urbana-Champaign ด้วยกัน
ในวันนี้ที่ผ่านไปแล้วเกือบ 20 ปี ก็ได้เวลาอันควรในการเขียนวิเคราะห์เรื่องนี้กันอย่างชัดเจน และขอส่งเสริมให้นำไปใช้กัน จะเป็นประโยชน์อย่างมาก
ลองจินตนาการชายฉกรรฉ์ 22 คนที่ไฟแรงพยายามแบ่งข้างเล่นฟุตบอล แต่ด้วยเพราะตกลงกันไม่ได้ว่าจะแบ่งยังไงให้ยุติธรรม เลยตัดสินใจใช้วิธีโอน้อยออก เริ่มจากกลุ่มคนที่ปรารถนาอย่างแรงกล้าที่จะเล่นฟุตบอล เมื่อการโอน้อยออกผ่านไป 38 ครั้งไม่สำเร็จซักที ก็ชักเริ่มสงบ “กูไม่เล่นก็ได้” “กูกลับไปนอนบ้านดีกว่า”
เพื่อให้เห็นชัดว่าการแบ่งข้างด้วยวิธีใหม่นี้มีประสิทธิภาพมากขึ้น เราต้องใช้การวิเคราะห์โอกาส(ซึ่งมีชื่อเป็นทางการยาวๆว่า”ความน่าจะเป็น”)มาช่วย เช่นการเป่ายิงฉุบเป็นสิ่งมาตรฐานที่ใช้กันเพราะโอกาสสำเร็จมันมีถึง 2 ใน 3 โดยแค่ 1 ใน 3 จะออกเหมือนกัน ตัวเลขที่เราใช้โดยสากลก็คือให้โอกาสมีค่าอยู่ระหว่าง 0 ถึง 1 เช่นการโยนเหรืยญสองหน้าก็จะมีโอกาสเป็นหัว 0.5 (หรือ 1 ใน 2)
เมื่อคน 10 คนใช้วิธีโอน้อยออก เป้าหมายคือการมีคนคว่ำมือ 5 คนและหงายมือ 5 คน เราจะคำนวณโอกาสโดยนับรูปแบบที่เป็นไปได้ทั้งหมด และรูปแบบที่เป็นเป้าหมายของเรา ตรงนี้ต้องใช้ความรู้เรื่องการนับ(สมัยผมเรียนเขาเรียกกันว่า”การเรียงสับเปลี่ยน”) คน 10 คนคว่ำหงายมือได้แบบไหนบ้างนั้นต้องเริ่มดูทีละคน ก็อาจเร่ิมจากการแปะเบอร์ผู้ร่วมกิจกรรมเป็น 1 2 3 ไปเรื่อยๆถึง 10 คนที่ 1 ก็สามารถออกมือได้ 2 แบบ คนที่ 2 ก็เช่นกัน เป็นแบบนี้ไปทั้ง 10 คน ก็จะได้ว่ามีการออกมือได้ทั้งหมด 2^10 = 1024 แบบ ทีนี้ก็มาดูแบบที่เราสนใจ คือมีคนคว่ำมือ 5 คน(หรือจะคิดว่าหงายมือ 5 คนก็ได้) สัญลักษณ์ที่เราเคยเห็นตอนเรียนเรื่องนี้ก็คือ C(n,r) หรือคือจำนวนแบบทั้งหมดในการเลือกของ r ชิ้นจากทั้งหมด n ชิ้น ซึ่งมีค่า n!/(r!(n-r)!) ทำให้ได้ว่าจำนวนแบบที่เราสนใจคือ C(10,5) = 10!/(5!5!) = 252 ทำให้โอกาสโอน้อยออก 10 คนสำเร็จคือ 252/1024 = 0.2461
ทีนี้ลองมาดูโอกาสสำเร็จเมื่อใช้วิธีใหม่ เร่ิมจากดึงออกหนึ่งคน แล้วให้ 9 คนโอน้อยออกให้ได้คว่ำ 4 หรือ 5 คน เราเริ่มเหมือนเดิมคือมาดูว่าคน 9 คนออกมือมาได้กี่แบบ ซึ่งการคำนวณก็คล้ายเดิมและได้จำนวนแบบคือ 2^9 = 512 ทีนี้ก็มาดูจำนวนแบบที่จะได้คว่ำมือ 4 คน ซึ่งก็คือ C(9,4) = 126 และจำนวนแบบที่จะได้คว่ำมือ 5 คนเป็น C(9,5) = 126 ทำให้จำนวนแบบที่สำเร็จเป็น 252 สรุปได้ว่าโอกาสโอน้อยออกสำเร็จเป็น 252/512 = 0.4922 ซึ่งมีค่าถึง 2 เท่าของวิธีเดิม
เมื่อเราวิเคราะห์กับกรณีของชายฉกรรฉ์บ้าฟุตบอล 22 คน ก็จะพบว่าโอกาสสำเร็จด้วยวิธีปกติคือ C(22,11)/2^22 = 0.1682 แต่หากใช้วิธีใหม่จะมีโอกาสถึง (C(21,10)+C(21,11))/2^21 = 0.3364 ก็จะช่วยให้เหล่าชายฉกรรฉ์สามารถใช้พลังงานไปกับการเล่นฟุตบอลได้ดังปรารถนา
ทีนี้ก็จะมาดูว่าการแบ่งข้างแบบใหม่นี้มันอิสระจริงไหม ข้อครหาที่เกิดขึ้นก็อาจเป็นว่าการเลือกคนที่ออกมารอมันมีผลไหมถ้าจะเลือกใคร คำตอบก็เป็นว่าไม่มีผล เพราะอีก 9 คนที่เหลือก็อยู่ในสถานการณ์เท่าเทียมกัน ไม่มีใครมีโอกาสเป็นพิเศษที่จะได้อยู่ข้างเดียวกับคนที่ออกมารอ หรือจะดูให้ละเอียดก็มาดูว่าหากเราเป็นหนึ่งใน 9 คนนั้น เราจะมีโอกาสอยู่กลุ่ม 4 คนต่างจากโอกาสไปอยู่กลุ่ม 5 คนไหม เราดูได้จากการที่ 8 คนที่เหลือ(เมื่อไม่นับเรา)จะต้องแบ่งเป็น 4 กับ 4 คือมีคนคว่ำมือ 4 คนและหงายมือ 4 คน ส่วนเราก็มีโอกาส 50-50 ว่าจะคว่ำหรือหงายมือ ก็จะไปอยู่กลุ่มใดกลุ่มหนึ่งด้วยโอกาสเท่ากัน จึงทำให้เรามีโอกาสไปอยู่กับคนที่ออกมารอเป็น 50-50 เหมือนกันนั่นเอง
ตอนจบผมก็จะพิสูจน์เพิ่มเติมดังที่หลายคนอาจสังเกตุเห็นว่าโอกาสแบ่งข้างด้วยวิธีใหม่เป็นสองเท่าของวิธีเก่าเสมอหรือไม่ คำตอบคือใช่ โดยจะพิสูจน์ดังนี้ สมมุติมีคน 2k คน ด้วยวิธีเก่ามีโอกาสแบ่งข้างสำเร็จเป็น C(2k,k)/2^(2k) แต่ด้วยวิธีใหม่จะได้โอกาสเป็น (C(2k-1,k-1)+C(2k-1,k))/2^(2k-1) เราสามารถจัดรูปของพจน์หลังเป็น 2C(2k-1,k-1)/2^(2k-1) เพราะสูตรพื้นฐานว่า C(n,r)=C(n,n-r) และกระจายออกมาในรูปแฟคทอเรียลก็จะจัดรูปได้มีค่าเป็นครึ่งหนึ่งของพจน์แรกได้อย่างง่ายดาย
ถึงตอนนี้ก็เป็นหน้าที่สำหรับพวกเราที่จะไปบอกชาวโลกให้ลองใช้วิธีนี้ จะได้ประหยัดเวลาในการโอน้อยออกกันมากขึ้น แต่ก็ต้องดูดีๆนะครับ อย่าเผลอไปใช้กับชายฉกรรฉ์ที่ไม่เชื่อในคณิตศาสตร์ อาจโดนรุมกระทืบได้
wacharin wichiramala
ที่มา http://www.vcharkarn.com/varticle/506014
ไม่มีความคิดเห็น:
แสดงความคิดเห็น