|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
||||
|
||||
งานเลี้ยงโต๊ะจีนอลวน
งานเลี้ยงโต๊ะจีนอลวน
เหมือนเป็นปัญหาต่อเนื่องจากปัญหาจดหมายผิดซอง เพราะหลังจากมีผู้แก้ปัญหานั้นได้แล้วอีกราว 200 ปีต่อมา จึงมีผู้เสนอปัญหาเกี่ยวกับการจับคู่ที่ซับซ้อนยิ่งขึ้น นัยว่าคราวที่แล้วเป็นการส่งจดหมายไปนัดแขกมาร่วมงานเลี้ยงและเล๊ะเป็นโจ๊กไปแล้ว คราวนี้ถึงเวลาจัดตำแหน่งที่นั่งงานเลี้ยงโต๊ะจีนให้แขก ซึ่งเป็นสามีภรรยา $n$ คู่ ยังจัดที่นั่งให้สามีนั่งไม่ติดกับภรรยาของตนเลยสักคู่เดียว ปัญหาของเราคราวนี้จึงเป็น จงหาจำนวนวิธีทั้งหมดในการจัดที่นั่งรอบโต๊ะกลมให้กับ สามีภรรยา $n$ คู่ โดยนั่งชายสลับหญิง และสามีจะนั่งไม่ติดกับภรรยาของตน ปัญหานี้เป็นที่รู้จักกันในชื่อ Married Couples หากใครจำหลักการแก้ปัญหาแบบเรียงสับเปลี่ยนคราวที่แล้วได้ คงพอจะมองออกแล้วว่าควรจะเริ่มแก้ปัญหาข้อนี้อย่างไรดี กำหนดให้ $c_i$ คือ สามีภรรยาคู่ที่ $i$ นั่งติดกัน รอบโต๊ะกลม $M(k,n)$ คือ จำนวนวิธีจัดที่นั่งให้ สามีภรรยานั่งติดกัน $k$ คู่ โดยสามีภรรยา $n-k$ คู่ที่เหลือจะนั่งติดกันหรือไม่ก็ได้ รอบโต๊ะกลม จากหลักการรวมเข้าและหักออกจะได้ว่า $\begin{array}{rcl} N(\bar c_1 \bar c_2 \cdots \bar c_n) & = & \displaystyle{N - \sum_{i = 1}^{n} N(c_i) + \sum_{\substack{i,j= 1 \\ i \not= j}}^{n} N(c_i c_j) - \sum_{\substack{i,j,k= 1 \\ i \not= j \not= k}}^{n} N(c_i c_j c_k) + \cdots + (-1)^n N(c_1 c_2 \dots c_n) }\\ & = & N - M(1,n) + M(2,n) - M(3,n) + \cdots + (-1)^n M(n,n) \end{array}$ เอ แล้วทำยังไงต่อดีละ กำหนดให้ $M_i$ คือสามีของ $F_i$ $F_i$ คือภรรยาของ $M_i$ เอ๊ะยังไง $M_x$ คือสามีของใครก็ไม่รู้ละ $F_x$ คือภรรยาของใครก็ไม่รู้ละ หลักการเรียงของบนวงกลมแบบหนึ่งคือ $จำนวนการจัดแบบวงกลม = \frac{จำนวนการจัดแบบเส้นตรง}{จำนวนรูปแบบที่ซ้ำ}$ การจัดแบบเส้นตรงในที่นี้ไม่ได้หมายความว่า ตัดความคิดเรื่องวงกลมออกไปหมดเลยนะครับ แต่จัดเป็นเส้นตรงเพื่อให้ง่ายและคุ้นเคยในการพิจารณากรณีต่างๆ โดยคนหัวแถวกับท้ายแถวยังมีความสัมพันธ์ว่าอยู่ติดกันด้วยนะครับ เช่น จัดแบบเส้นตรง 100% $\color{red}{M_1} F_x M_2 F_x \cdots M_n \color{red}{F_y}$ เรามองว่า $M_1$ และ $F_y$ นั่งไม่ติดกัน จัดแบบวงกลมโดยมองให้เป็นเส้นตรง $\color{red}{M_1} F_x M_2 F_x \cdots M_n \color{red}{F_y}$ เรามองว่า $M_1$ และ $F_y$ นั่งติดกัน เริ่มจากหาค่า $N$ (จำนวนวิธีจัดที่นั่งชายสลับหญิงรอบโต๊ะกลม) จัดแบบวงกลมโดยมองให้เป็นเส้นตรง
จำนวนรูปแบบที่ซ้ำ เนื่องจากรูปแบบการนั่งแบบนี้จะซ้ำกันเมื่อนั่งเป็นวงกลม $\left.\begin{array}{ccccccccc} M_1 & F_x & M_2 & F_x & \cdots & M_{n-1} & F_x & M_n & F_x \\ F_x & M_1 & F_x & M_2 & \cdots & F_x & M_{n-1} & F_x & M_n \\ M_n & F_x & M_1 & F_x & \cdots & M_{n-2} & F_x & M_{n-1} & F_x \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ M_2 & F_x & M_3 & F_x & \cdots & M_n & F_x & M_1 & F_x \\ F_x & M_2 & F_x & M_3 & \cdots & F_x & M_n & F_x & M_1 \end{array}\right\} 2n\ \text{แบบ} $ $\therefore N = \frac{2(n!)^2}{2n} = (n-1)!n!$ หาค่า $M(n,k)$ (จำนวนวิธีจัดที่นั่ง ให้สามีภรรยานั่งติดกัน $k$ คู่ โดยสามีภรรยา $n-k$ คู่ที่เหลือจะนั่งติดกันหรือไม่ก็ได้ รอบโต๊ะกลม) จัดแบบวงกลมโดยมองให้เป็นเส้นตรง
เพื่อให้ง่ายขึ้น ลองพิจารณาการเลือกที่นั่งคู่ $k$ คู่ ที่ไม่ยอมให้เลือกที่นั่งคู่คร่อมตรงตำแหน่ง หัวแถวกับท้ายแถว ส่วนตำแหน่งอื่นจะเลือกยังไงก็ได้ ว่าทำได้กี่วิธี ปัญหานี้จะเหมือนกับ การหาจำนวนวิธีวางตัวโดมิโนขนาด $1 \times 2$ จำนวน $k$ ตัว ทับบนตัวเลข $1 - n$ ที่เขียนเรียงลำดับกันในแนวเส้นตรง โดยวางตัวโดมิโนซ้อนกันไม่ได้ ตัวอย่างเช่น การวางตัวโดมิโนขนาด $1 \times 2$ จำนวน $2$ ตัว ทับลงบนตัวเลข $1 - 6$ ที่เขียนเรียงลำดับกันในแนวเส้นตรง ทำได้ 6 วิธีดังนี้ $\bbox[border:1px black solid,2pt]{1 \quad 2} \quad \bbox[border:1px black solid,2pt]{3 \quad 4} \quad 5 \quad 6$ $\bbox[border:1px black solid,2pt]{1 \quad 2} \quad 3 \quad \bbox[border:1px black solid,2pt]{4 \quad 5} \quad 6$ $\bbox[border:1px black solid,2pt]{1 \quad 2} \quad 3 \quad 4 \quad \bbox[border:1px black solid,2pt]{5 \quad 6}$ $1 \quad \bbox[border:1px black solid,2pt]{2 \quad 3} \quad \bbox[border:1px black solid,2pt]{4 \quad 5} \quad 6$ $1 \quad \bbox[border:1px black solid,2pt]{2 \quad 3} \quad 4 \quad \bbox[border:1px black solid,2pt]{5 \quad 6}$ $1 \quad 2 \quad \bbox[border:1px black solid,2pt]{3 \quad 4} \quad \bbox[border:1px black solid,2pt]{5 \quad 6}$ ถ้าเราไม่นั่งนับทีละแบบ เราจะมีวิธีหาจำนวนวิธีวางตัวโดมิโนได้อย่างไร หากเราแทนตัวโดมิโนด้วยอักษร "a" และแทนตัวเลขที่ไม่โดนโดมิโนวางทับด้วยตัวอักษร "b" ทั้ง 6 วิธีนั้นจะเป็นคำต่อไปนี้ "aabb" , "abab" , "abba" , "baab" , "baba" , "bbaa" คุ้นกับปัญหานี้ไหมครับ มันก็คือจำนวนวิธีทั้งหมดในการเีรียง a 2 ตัว และ b 2 ตัว ให้เป็นคำใหม่นั่นเอง ได้จำนวนวิธีทั้งหมดคือ $\frac{4!}{2!2!} = 6$ วิธี ดังนั้น จำนวนวิธีวางตัวโดมิโนขนาด $1 \times 2$ จำนวน $k$ ตัว ทับบนตัวเลข $1 - n$ ที่เขียนเรียงลำดับกันในแนวเส้นตรง โดยวางตัวโดมิโนซ้อนกันไม่ได้ ทำได้ทั้งสิ้น $\displaystyle{\frac{(n - k)!}{k! (n - 2k)!} = \binom{n - k}{k}}$ วิธี แล้วถ้าเราเขียนตัวเลข $1 -n$ ในแนววงกลมละ จะมีจำนวนวิธีวางตัวโดมิโนทับได้กี่วิธี เราแก้ปัญหานี้ด้วยการแบ่งเป็น 2 กรณีคือ
เราจึงได้ จำนวนวิธีเลือกที่นั่งคู่ให้ สามีภรรยานั่งติดกัน $k$ คู่ จากที่นั่งทั้งหมด $2n$ ตำแหน่ง รอบโต๊ะกลม โดยมองให้เป็นเส้นตรง ได้ทั้งหมด $\displaystyle{\frac{2n}{2n - k}\binom{2n - k}{k}}$ วิธี จำนวนรูปแบบที่ซ้ำ มีค่าเป็น $2n$ ครับโดยพิจารณาแบบเดียวกับกรณีทั้งหมด ดังนั้นเราจะได้ จำนวนวิธีจัดที่นั่ง ให้สามีภรรยานั่งติดกัน $k$ คู่ โดยสามีภรรยา $n-k$ คู่ที่เหลือจะนั่งติดกันหรือไม่ก็ได้ รอบโต๊ะกลม $\begin{array}{rcl} M(k,n) & = &\displaystyle{\binom{n}{k} \cdot \frac{2n}{2n - k}\binom{2n - k}{k} \cdot 2 \cdot k! \cdot ((n - k)!)^2 \cdot \frac{1}{2n}} \\ & = & \displaystyle{2(n!) \binom{2n - k}{k} \frac{(n - k)!}{2n - k}} \end{array}$ และเนื่องจาก $M(0,n) = (n-1)!n! = N$ จริง ดังนั้น $\begin{array}{rcl} N(\bar c_1 \bar c_2 \cdots \bar c_n) & = & N - M(1,n) + M(2,n) - M(3,n) + \cdots + (-1)^n M(n,n) \\ & = & \displaystyle{2(n!) \sum_{k = 0}^{n} (-1)^k \binom{2n - k}{k} \frac{(n - k)!}{2n - k}} \end{array}$ หมายเหตุ: คำตอบของปัญหานี้ที่พบได้ทั่วไป จะไม่สนใจว่าเกิดรูปแบบซ้ำขึ้น จึงมีคำตอบเป็น $\displaystyle{2(n!) \sum_{k = 0}^{n} (-1)^k \frac{2n}{2n - k} \binom{2n - k}{k} (n - k)!}$
__________________
The difference between school and life? In school, you're taught a lesson and then given a test. In life, you're given a test that teaches you a lesson. 16 กุมภาพันธ์ 2008 14:24 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ TOP |
#2
|
||||
|
||||
อืมสุดยอดคับ
|
#3
|
||||
|
||||
.+.+.++.+
ขอบคุณคร้าบบบ
|
#4
|
||||
|
||||
*0* สุดยอด
|
#5
|
|||
|
|||
ผมว่าแค่คิดไม่ให้ภรรยานั่งติดกัยสามีก็ยากอยู่แล้ว คงต้องหาเหตุผลมากกว่าจำนนวนวิธีข้างต้นซะอีก
__________________
มาหาความรู้ไว้ติวหลาน แต่หลานไม่เอาเลขแล้ว เข้ามาทำเลขเอามันอย่างเดียว ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก รู้อะไรไม่สู้ รู้จักพอ (ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี) (แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด) |
|
|