วงแหวนเว็บ

neizod's speculation

insufficient data for meaningful answer

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

Sunday, September 16, 2007, 02:15 AM

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

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

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

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

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

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

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

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

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

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

เมื่อวิธีที่ผ่านมาล้มเหลว ก็ใช้วิธีพื้นฐาน
คือทดลองหาค่า โดยเริ่มตั่งแต่ 1 ช่อง
ได้ค่าดังนี้

ช่องโน้ต สลับได้ หมายเหตุ
1 0 มีที่เดียว จึงย้ายที่ไม่ได้เลย
2 1 ย้ายที่ได้แค่วิธีเดียว
3 2  
4 9  
5 44 เหนื่อยมาก กว่าจะกระจายหมด
6 265 ข้อนี้ใช้สมการทำนายครับ

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

qn=(n1)(qn1+qn2)

โดย
n เป็นจำนวนเต็ม โดย n3
qn คือ วิธีการที่สลับได้เมื่อมี n ช่อง
ที่ให้ n3 เพราะไม่อยากนิยาม q0, q1
(จะปรากฎเมื่อหา 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=ndn1dn1+(n1)dn2

โดยคราวนี้
n เป็นจำนวนเต็ม โดย n3
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!
(ใช้ได้ที่ n2 นะครับ)

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

…จบ…

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

อ้างอิง :
math forum

neizod

author