ปัญหาสับไพ่ (เฉลย)

วันนี้มาเฉลยปัญหาสับไพ่ที่ให้ไว้เมื่อสัปดาห์ที่แล้วนะครับ

โดยปกติแล้วการจะหาคำตอบของปัญหาคณิตศาสตร์ที่ซับซ้อนนั้น ควรเริ่มจากกรณีที่ง่ายๆ ก่อน (แต่ในบางครั้งถ้าศึกษากรณีที่ง่ายเกินไป ก็อาจทำให้เก็บลักษณะของปัญหาได้ไม่ครบถ้วน) ในที่นี้จะคิดกรณีไพ่ 5 ใบที่มีตัวอักษร A-E สมมติว่าก่อนการสับไพ่ ไพ่เรียงกัน A,B,C,D,E โดยเมื่อสับแล้วจะเรียงเป็น B,E,D,C,A ถ้าสับอีกครั้งจะเป็น E,A,C,D,B (ดูภาพข้างล่าง กระบวนการสับไพ่แสดงด้วยลูกศร โดยวิธีสับเดียวกันก็จะมีระบบลูกศรที่เหมือนกัน)
จากภาพจะเห็นว่าหลังจากสับไป 6 ครั้ง สำรับจะกลับสู่สภาพเริ่มต้น หากลองดูกระบวนการสับในรายละเอียด จะเห็นว่าไพ่ A จะย้ายจากตำแหน่งที่ 1→5→2→1→5→2→1 หากดูไพ่อื่นๆ ในทำนองเดียวกัน ก็จะเห็นว่าไพ่ B,E จะเคลื่อนที่เป็นวัฎจักรคล้ายๆ กับไพ่ A ส่วน C,D ก็จะมีวัฎจักรของมันคือ 3→4→3→4→3→4→3 วัฎจักรนี้เปรียบได้กับเก้าอี้ดนตรีที่ A,B,E จะสลับเปลี่ยนที่กันไปเป็นวงกลม ข้อสังเกตุนี้นำมาสรุปได้ว่า ไพ่แต่ละใบจะวนไปตามวัฎจักรของมัน โดยจะกลับสู่ตำแหน่งเดิมทุกๆ N ครั้ง เมื่อ N เป็นจำนวนของไพ่ในวัฎจักร ถ้าดูจากตัวอย่างข้าวบนไพ่ A,B,E จะกลับสู่ตำแหน่งเดิมทุกๆ 3 ครั้ง และไพ่ C,D จะกลับสู่ตำแหน่งเดิมทุกๆ 2 ครั้ง ดังนั้นหากเราหาค่า ค.ร.น. (คูณร่วมน้อย) ของความยาวของทุกวัฎจักร ก็จะได้จำนวนครั้งที่ไพ่ในทุกๆ วัฎจักรจะกลับสู่ตำแหน่งเริ่มต้นของมัน นั่นคือสำรับทั้งสำรับกลับสู่สภาพเริ่มต้น (ตัวอย่างข้างบน ค.ร.น. ของ 2 กับ 3 เป็น 6 จึงกลับสู่ตำแหน่งเดิมทุกๆ 6 ครั้ง)

แต่เนื่องจากไม่รู้ว่าการสับของเครื่องแบ่งเป็นวัฎจักรได้อย่างไร จึงต้องคำณวนเผื่อเอาไว้ เรารู้แน่ๆ ว่าวัฎจักรนั้นยาวอย่างมากที่สุดแค่ 52 ใบ (จำนวนไพ่ในสำรับ) เพราะฉะนั้นถ้าเราหา ค.ร.น. ของ 1-52 ก็จะครอบคลุมค่าความยาวของวัฎจักรที่เป็นไปได้ทั้งหมด ซึ่งมีค่าประมาณ 3×10²¹ (ผู้อ่านลองคิดดูนะครับว่าคำณวนออกมายังไง)

อีกแง่หนึ่งถ้าถามแค่ว่าสับไปเรื่อยๆ อย่างนี้ จะกลับคืนสู่สภาพเริ่มต้นมั้ย? (โดยไม่ต้องรู้ชัดว่าจะกลับสภาพเริ่มต้นหลังจากครั้งที่เท่าไหร่นะครับ) ก็มีคำตอบง่ายๆ นั่นคือ เรารู้ว่ารูปแบบการเรียงไพ่ 52 ใบที่เป็นไปได้ทั้งหมดนั้นมีจำกัด (เท่ากับ 52!=52×51×⋯×2×1 วิธี) เพราะฉะนั้นถ้าเราสับไปเรื่อยๆ มันต้องซ้ำกับสภาพที่ผ่านมาแน่นอน (อันนี้ถ้าพูดทางเทคนิคหน่อยก็คืออาศัยกฎรังนกนะครับ) ปัญหาคือเป็นไปได้ไหมที่มันจะซ้ำแต่ไม่ซ้ำกับสภาพเริ่มต้นเลย? คำตอบคือเป็นไปไม่ได้ เพราะการสับเราเป็นฟังก์ชันหนึ่งต่อหนึ่ง (นั่นคือถ้ารู้สภาพก่อนสับ ก็มีสภาพหลังสับได้แบบเดียวเท่านั้น และจากสภาพหลังสับก็สามารถย้อนไปหาสภาพก่อนสับได้แบบเดียวเช่นกัน) เพราะฉะนั้นเป็นไปไม่ได้ที่จะซ้ำกับสภาพอื่นก่อนที่จะซ้ำกับสภาพเริ่มต้น

งงมั้ยครับ? เขียนเองก็งงเอง ลองยกตัวอย่างละกัน ขอตั้งชื่อสภาพเริ่มต้นของสำรับว่า Deck 1 ละกันทีนี้พอสับไปเรื่อยๆ ก็จะเกิดสภาพสำรับ Deck 2, Deck 3, ... ทีนี้สมมติว่ามีการซ้ำเกิดขึ้นครั้งแรกที่ Deck 52 โดยไปซ้ำกับ Deck 7 เราจะแสดงว่ากรณีนี้ไม่สามารถเกิดขึ้นได้ ซึ่งในทางคณิตศาสตร์แล้วเรียกวิธีพิสูจน์แบบนี้ว่าการพิสูจน์โดย contradiction นั่นคือ "สมมติ" ว่ามีเหตุการณ์ที่ไม่ต้องการเกิดขึ้น แล้วหากสมมติฐานนั้นนำไปสู่ข้อขัดแย้งกับความจริงอื่นๆ ก็แสดงว่าเหตุการณ์ในสมมติฐานนั้นไม่สามารถเกิดขึ้นได้

ลองมาดูการใช้จริงกันดีกว่า ในที่นี้เราสมมติว่าการซ้ำครั้งแรกเกิดเมื่อ Deck 52 ซ้ำกับ Deck 7 แต่อย่างที่เกริ่นไว้แล้วว่าการสับเราเป็นฟังก์ชันหนึ่งต่อหนึ่ง นั่นคือหากเราเริ่มจาก Deck 7 หรือ Deck 52 (ซึ่งในสมมติฐานเราบอกว่ามันเหมือนกัน) แล้วย้อนกลับไปหนึ่งขั้น สำรับที่ได้ก็ต้องเหมือนกัน นั่นคือ Deck 6 ต้องเหมือนกับ Deck 51 ซึ่งขัดกับสมมติฐานที่ว่าเกิดการซ้ำครั้งแรกที่ Deck 52 (เพราะอย่างน้อยๆ มันก็มีการซ้ำที่ Deck 51) นี่คือข้อขัดแย้ง (contradiction) เพราะฉะนั้นเราจึงสรุปได้ว่าเป็นไปไม่ได้ที่จะเกิดการซ้ำกับสำรับอื่นๆ ก่อนที่จะซ้ำกับสำรับแรก (ดังนั้นหากคิดจะเขียนโปรแกรมตรวจหาจุดซ้ำ ก็ตรวจแค่ว่าซ้ำกับ Deck 1 ก็พอ เพราะถ้าจะซ้ำก็จะซ้ำกับ Deck 1 ก่อน) จะสังเกตว่าตรรกะนี้สามารถเปลี่ยน Deck 7 เป็นสำรับใดๆ ก็ได้ยกเว้น Deck 1 เพราะจาก Deck 1 เราไม่สามารถย้อนกลับไปได้แล้ว

โม้ไปโม้มา รู้สึกว่าจะยาวกว่าที่ตั้งใจไว้เยอะ จะสังเกตว่าวิธีที่สองนั้นมีหลักการง่ายๆ โดยไม่ต้องสังเกตถึงวัฎจักรของการสับ หรือหาค่า ค.ร.น. ให้ยุ่งยาก แต่ก็ได้คำตอบที่ไม่ชัดเจน คือรู้เพียงแค่ว่าถ้าสับไป 52!=8×10⁶⁷ ครั้งก็ต้องเจอที่ซ้ำกับครั้งแรกแหละ ในขณะที่วิธีแรกเรารู้แน่นอนว่าถ้าสับไปเท่านี้ครั้ง จะกลับสู่สภาพแรกเริ่มได้ (และจำนวนครั้งที่คิดได้ในวิธีแรกก็น้อยกว่ามาก)

เอาเป็นว่าเฉลยแค่นี้ละกัน เดี๋ยวผู้อ่านจะเบื่อ หรือหนีกันหมด สำหรับผู้อ่านที่สนใจจะคิดต่อก็ให้ปัญหา (ค่อนข้างยากครับ) ไปคิดกันต่อละกัน (ไม่เฉลยนะครับ :P)

1. ค่า ค.ร.น.ที่หาได้ในวิธีแรกนั้น สามารถรับประกันได้ว่าไม่ว่าเครื่องสับจะสับอย่างไร หลังจากสับไปตามค่านี้แล้วสภาพสำรับสุดท้ายจะเหมือนสภาพสำรับเริ่มต้นอย่างแน่นอน หากไม่สนใจว่าสภาพสุดท้ายจะต้องตรงกับสภาพแรก แต่ในระหว่างที่สับนั้นต้องผ่านสภาพเริ่มต้นอย่างน้อยหนึ่งครั้ง ถามว่าต้องสับอย่างน้อยกี่ครั้ง?


2. ถ้าดูคำตอบจากตอนแรก (ค่าค.ร.น.) หรือถ้าให้ดีคำตอบจากปัญหาเสริม จะมีค่าน้อยกว่าวิธีการสับที่เป็นไปได้ทั้งหมด (วิธีการสับทั้งหมด = 52!) ซึ่งแสดงว่าถ้าใช้เครื่องสับที่มีการสับแบบเดียว จะไม่สามารถสับไพ่ให้ครบทุกรูปแบบที่เป็นไปได้ได้ (เพราะก่อนจะครบ 52! วิธีจะซ้ำกับสภาพแรกก่อน) ถามว่าต้องใช้เครื่องสับกี่เครื่อง (กำหนดวิธีสับของเครื่องได้ตามต้องการ) ซึ่งเมื่อใช้ร่วมกันแล้ว (เช่น สับเครื่องแรก 2 ครั้ง ตามด้วยเครื่องที่สอง 3 ครั้ง) จะสามารถสับได้ครบทุกรูปแบบ?


3. ต่อเนื่องจากข้อที่แล้ว ถ้าไม่สามารถกำหนดวิธีสับของเครื่องได้ แต่รู้ว่าทุกเครื่องมีวิธีสับที่แตกต่างกัน ต้องมีอย่างน้อยกี่เครื่องจึงจะมั่นใจได้ว่าสามารถสร้างการสับได้ทุกรูปแบบ?

การสับไพ่นั้นในทางคณิตศาสตร์ถือเป็นการเรียงสับเปลี่ยน (permutation) ซึ่งมีการศึกษาโครงสร้างกันอย่างลึกซึ้ง และถือเป็นส่วนหนึ่งของวิชา Group Theory ซึ่งศึกษาโครงสร้างของ "กลุ่ม" สิ่งของที่มีคุณสมบัติต่างๆ เช่น ศึกษาวัฎจักรในกลุ่ม หาวิธีสร้างสิ่งของทุกอย่างในกลุ่มขึ้นจากสิ่งของเพียงไม่กี่อย่าง (เช่นในปัญหาเสริมข้อสอง) ผลงานเด่นอย่างหนึ่งในแขนงนี้คือ ใช้โครงสร้างของการเรียงสับเปลี่ยนเพื่อพิสูจน์ว่า สมการกำลัง 5 ขึ้นไปในหนึ่งตัวแปร ไม่มีสูตรที่สามารถใช้หาคำตอบได้ (สูตรสมการกำลังสองที่ใช้กันอย่างแพร่หลายคือ x=(−b±√b²−4ac)/2a) หวังว่าผู้อ่านคงได้สัมผัสถึงความล้ำลึกของกิจกรรมทั่วๆ ไป (การสับไพ่) นี้นะครับ เพราะถ้ามองดีๆ แล้วก็มีปัญหาที่น่าคิดมากมายเกิดขึ้นในชีวิตประจำวันของเรา ลองหาดูดีๆ นะครับ :-)