Đây là câu 5, thi HSG quốc gia năm 2012
Lời giải của nó thế này:
đánh
số thứ tự các ghế từ trái sang phải là 1, 2, …,17.
Gọi g1, g2, g3, g4, g5
là vị trí chỗ ngồi của các cô gái G1, G2, G3,
G4, G5 tương ứng.
Khi
đó ta có 1 ≤ g1 < g2 < g3 < g4
< g5 ≤ 17. Ngoài ra ta còn có 3 < g2 – g1
và 1 < g5 – g4 < 6.
Đặt
A = {(g1, g2, g3, g4, g5)|
1 ≤ g1 < g2 < g3 < g4 <
g5 ≤ 17, 3 < g2 – g1, 1 < g5
– g4 < 6} thì ta cần tìm |A|.
Đặt B = {(g1, g2, g3,
g4, g5)| 1 ≤ g1 < g2 < g3
< g4 < g5 ≤ 17, 3 < g2 – g1,
1 < g5 – g4 }
C = {(g1, g2, g3,
g4, g5)| 1 ≤ g1 < g2 < g3
< g4 < g5 ≤ 17, 3 < g2 – g1,
6 ≤ g5 – g4 }
thì
rõ ràng ta có A = B \ C (với C Ì
B), suy ra |A| = |B| - |C|.
Để tính |B|, ta đặt D = {(h1, h2,
h3, h4, h5}| 1 ≤ h1 < h2
< h3 < h4 < h5 ≤ 13} và xét ánh xạ f:
B à
D, f(g1, g2, g3, g4, g5)
à
(g1, g2-3, g3-3,g4-3,g5-4)
thì dễ dàng kiểm chứng được f là một song ánh.
Nhưng
|D| bằng số cách chọn 5 phần tử ra từ 13 phần tử nên ta có $|D| = C^{5}_{13}$. Vậy $|B| = |D| = C^{5}_{13}$.
Một
cách hoàn toàn tương tự, ta tính được $| C | = C^{5}_{9}$. Vậy số cách xếp chỗ cho 15 cô gái bằng $C^{5}_{13}-C^{5}_{9}$ .
Vì
còn có 12 chàng trai có thể hoán đổi vị trí ở 12 chiếc ghế dành cho họ nên số
cách xếp thỏa mãn yêu cầu bài toán là 12! 1161.