Sep 16, 2007

Knowledge "ย้ายที่ทั้งหมดได้กี่วิธี" คำถามนี้สั้นแต่มันไม่หมู

วันนี้เป็นหวัด เลยต้องนอนตั้งแต่เที่ยง
ตื่นขึ้นมาเขียนบทความนี้อย่างเฉื่อยชา
กว่าจะได้โพสต์ก็ดึกซะโน่น...
ก็หวังว่าจะอ่านได้มันส์อยู่นะครับ
(สำนวนมันคงไม่เป็นหวัดด้วยหรอกนะ)

โจทย์ข้อนี้อาจมีที่มาแปลกไปซักหน่อย
เพราะมันเกิดจากการสังเกตเกมที่เล่น
(ซึ่งคนส่วนใหญ่ไม่ได้คิดถึงจุดนี้เลย)
(และข้อสอบก็ไม่ค่อยออกแนวนี้ด้วย)

แต่สำหรับผมแล้ว มันธรรมดามาก
เพราะความรู้นั้น มีอยู่ในทุกสิ่งครับ

โดยผมสังเกตได้จากเกม O2Jam
แล้วก็เกิดคำถามว่า เวลาใส่แหวนเนี่ย
มันสลับโน้ตที่ตกลงมาได้กี่แบบ?

อธิบายเกี่ยวกับตัวเกมซักหน่อย
O2Jam เป็นเกมเพลงที่ใช้นิ้วกดโน้ต
(คล้ายเกมเต้น แต่เปลี่ยนมาใช้นิ้วแทน)
โดย O2Jam มีปุ่มให้กดมากถึง 7 ปุ่ม
(น่าจะเป็นเกมเพลงที่มีปุ่มกดมากที่สุด)

แต่สำหรับพวกเทพแล้ว นี่คงน้อยไป
ก็เลยมีระบบแหวนความสามารถขึ้นมา
เมื่อใส่แหวนแล้ว ตัวโน้ตจะเปลี่ยนไป
เช่น มองไม่เห็นโน้ต, เรียงโน้ตใหม่,
โน้ตอยู่ในกระจก เป็นต้น

ในที่นี้ เราจะสนใจการเรียงโน้ตใหม่
ซึ่งเท่าที่ผมสังเกตมา (อาจสังเกตผิด)
พบว่าโน้ตจะมีการเปลี่ยนที่ตกทุกโน้ต
(ไม่อยู่ในตำแหน่งที่ยังไม่ใส่แหวนเลย)

ทวนโจทย์นะครับ
เวลาใส่แหวน โน้ตจะสลับได้กี่แบบ?
(มี 7 ที่ให้ลง และต้องลงไม่ซ้ำที่เดิม)

ตอนแรก เห็นโจทย์สั้นๆ ก็คิดว่าหมู
เลยตั้งสมการความน่าจะเป็น (พื้นฐาน)
แต่พอดูแซมเปิลเสปส ก็พบว่าผิดไกล

เลยลองดัดแปลงสมการนั้นนิดหน่อย
ใช้เวลาคิดนานมาก แต่ก็แก้ปัญหาไม่ได้
เลยหนีไปฟังเพลงพักสมองหน่อยนึง

เมื่อวิธีที่ผ่านมาล้มเหลว ก็ใช้วิธีพื้นฐาน
คือทดลองหาค่า โดยเริ่มตั่งแต่ 1 ช่อง
ได้ค่าดังนี้
ช่องโน้ตสลับได้หมายเหตุ
10มีที่เดียว จึงย้ายที่ไม่ได้เลย
21ย้ายที่ได้แค่วิธีเดียว
32
49
544เหนื่อยมาก กว่าจะกระจายหมด
6256ข้อนี้ใช้สมการทำนายครับ

โห... มันขึ้นเร็วกว่าที่คิดแฮะ
แต่ตอนกระจาย ก็พบรูปแบบตายตัว
เลยกำหนดสมการออกมาได้ดังนี้

qn = (n-1)(qn-1+qn-2)

โดย
n เป็นจำนวนเต็ม โดย n≥3
qn คือ วิธีการที่สลับได้เมื่อมี n ช่อง
ที่ให้ n≥3 เพราะไม่อยากนิยาม q0, q-1
(จะปรากฎเมื่อหา q1, q2 จากสมการ)
และกำหนดให้ q1 = 0 และ q2 = 1

อธิบายที่มาของสมการ
โดยใช้ตัวอย่างกรณี 5 ช่องนะครับ

ต้นแบบคือ
1 | 2 | 3 | 4 | 5
เมื่อย้าย 1 ไปไว้ที่ 2 และ 2 ไปไว้ที่ 1
2 | 1 | 5 | 3 | 4
2 | 1 | 4 | 5 | 3
เมื่อย้าย 1 ไปไว้ที่ 2 และ 2 ไปไว้ที่อื่น
5 | 1 | 2 | 3 | 4
4 | 1 | 2 | 5 | 3
3 | 1 | 2 | 5 | 4
3 | 1 | 5 | 2 | 4
5 | 1 | 4 | 2 | 3
4 | 1 | 5 | 2 | 3
3 | 1 | 4 | 5 | 2
4 | 1 | 5 | 3 | 2
5 | 1 | 4 | 3 | 2
เมื่อย้าย 1 ไปไว้ที่ตำแหน่งอื่นที่เหลือ
ก็ทำในทำนองเดียวกันกับข้างบน

สรุปคือ
ขั้นตอนแรก สลับ 1 กับ 2
จะทำได้ 2 วิธี ซึ่งเหมือนกับ q3
ขั้นตอนที่สอง เอา 2 ไว้ที่อื่น
จะทำได้ 3 วิธี ซึ่งเหมือนกับ q4
ขั้นตอนสุดท้าย เอา 4 คูณ q4+q3
จึงได้ว่า q5 = 4(q4+q3) = 44 วิธี

ถึงตรงนี้ก็ตอบโจทย์ได้แล้ว
q7 = 6(q6+q5) = 1854

...จบเลยดีมั้ย...

ยังๆๆ
เราต้องไม่พอใจอะไรง่ายๆ สิครับ
เพราะมันเป็นความสัมพันธ์เวียนเกิด
ซึ่งมันใช้ยากหน่อย เช่น จะหา q1000
ก็ต้องหา q999, q998, q997, ...
โครตจะยุ่งยากเลยหละครับ

ถึงแม้ผมจะปลุกปล้ำกับมันอยู่พักใหญ่
ผมก็ไม่สามารถลดรูปทำให้มันง่ายขึ้นได้
เลยเอาตัวอย่างเลขไปหาใน google
(เพราะตัวแปรในสมการนั้นไม่สากล)
(พิมพ์ค้นหาด้วยสมการไปก็ไม่มีชัวร์)

เลขที่ใช้หาใน google คือ 8 พจน์แรก
1 2 9 44 265 1854 14833 133496
และพบว่ามันลดรูปให้เป็นอนุกรมได้
(เค้าใช้การจัดหมู่พิสูจน์ ขี้เกียจอ่าน)
ผมเลยลองทำใหม่อีกรอบนึง
(พิสูจน์สูตรง่ายกว่าหาสูตรตั้งเยอะ)
โดยจัดรูปสมการของผมใหม่เป็น

dn = ndn-1-dn-1+(n-1)dn-2

โดยคราวนี้
n เป็นจำนวนเต็ม โดย n≥3
dn คือ วิธีการที่สลับได้เมื่อมี n ช่อง
และกำหนดให้ d1 = 0 และ d2 = 1
(เปลี่ยนมาใช้ตัว d เพื่อให้เป็นสากล)
(ตอนนั้นคิดยังไงเลือกใช้ตัว q ก็ไม่รู้)

สมการใหม่นี้ พิสูจน์ตรงๆ เข้าใจยาก
เพราะตอนที่จับกลุ่มนั้น งงมากๆ
จึงขอพิสูจน์โดยใช้วิธีแทนค่านะครับ

แนวทางการพิสูจน์นั้น ทำได้โดยการ
เขียนตัวเลขให้ติดแฟกทอเรียลผลหาร
และปล่อยให้ติดแฟกทอเรียลไปเลย
(ไม่ต้องคำนวนออกมาเป็นเลข)

เมื่อแทนค่าไล่ไปเรื่อยๆ จะได้ผลดังนี้
d3 = 3!/2! - 3!/3!
d4 = 4!/2! - 4!/3! + 4!/4!
d5 = 5!/2! - 5!/3! + 5!/4! - 5!/5!
d6 = 6!/2! - 6!/3! + 6!/4! - 6!/5! +6!/6!

จึงสรุปได้ว่า
dn = n!/2! - n!/3! + ... +(-1)nn!/n!
(ใช้ได้ที่ n≥2 นะครับ)

ถ้าพิสูจน์แบบการจัดหมู่ (ตามเว็บ) จะได้
D(n) = n! - n!/1! + n!/2! - n!/3! + ... +(-1)nn!/n!
(มีพจน์ n! - n!/1! โผล่ขึ้นมา)
(และ n เป็นจำนวนเต็มบวกแล้ว)

...จบ...

จบดีกว่าครับ หมดเรื่องที่จะฝอยละ
รักษาสุขภาพกันด้วยนะครับ ^^

อ้างอิง :
http://mathforum.org/library/drmath/view/56185.html