Bài toán (VMO 2012) Cho một nhóm gồm 5 cô gái xếp từ trái sang phải, kí hiệu là G_1, G_2, G_3, G_4, G_5 và 12 chàng trai. Có 17 chiếc ghế sắp thành một hàng ngang. Người ta xếp nhóm người đã ngồi vào các chiếc ghế đó sao cho:
1. Mỗi ghế có đúng một người ngồi.
2. Giữa G_1 và G_2 có ít nhất 3 chàng trai.
3. Giữa G_4 và G_5 có ít nhất 1 chàng trai và không quá 4 chàng trai.
Hỏi có bao nhiêu cách xếp như vậy.
Lời giải :
Kí hiệu x_i là vị trí ngồi của bạn gái thứ i, thế thì: \begin{cases}1\le x_1<x_2<x_3<x_4<x_5\le 17\\x_2-x_1>3, 1<x_4-x_3\le 5\end{cases} Từ điều kiện x_2-x_1>3\Rightarrow x_2-3>x_1, khi đó, ta có: 1\le x_1<x_2-3<x_3-3<x_4-3<x_5-3<14 Đặt x_1=y_1, y_i=x_i-3, i=\{2,3,4,5\} Ta được: \begin{cases}1\le y_1<y_2<y_3<y_4<y_5<14\\y_4-y_3=\{2, 3, 4, 5\}\end{cases} Tới đây, ta có 4 trường hợp:
Trường hợp 1: y_4-y_3=2, khi đó: 1\le y_1<y_2<y_3<y_5-2\le 12 Ở trường hợp này có C_{12}^4 cách xếp.
Trường hợp 2: y_4-y_3=3, khi đó: 1\le y_1<y_2<y_3<y_5-3\le 11 Trường hợp này có C_{11}^4 cách xếp.
Trường hợp 3: y_4-y_3=4, khi đó: 1\le y_1<y_2<_3<y_5-4\le 10 Trường hợp này có C_{10}^4 cách xếp.
Trường hợp 4: y_4-y_3=5, khi đó: 1\le y_1<y_2<y_3<y_5-5\le 9 Trường hợp này có C_{9}^4 cách xếp.
Như vậy ta thu được C_{9}^4+C_{10}^4+C_{11}^4+C_{12}^4=1161 cách. Tới đây, ta chú ý rằng 12 chàng trai có thể hoán vị cho nhau. Như vậy, kết quả bài toán là: 12!.1161
No comments:
Post a Comment