[minhtuyb]

Nguyên văn bởi bboy114crew

Câu 4: Có 19 người xếp thành hàng vào xem một buổi biểu diễn ảo thuật .Phòng biểu diễn có đúng 19 chiếc ghế được xếp thành hàng ngang và ảo thuật gia đánh sô chúng từ 1 đến 19 theo thứ tự từ trái qua phải . Sau đó anh ta phát cho mỗi ngừoi đến xem 1 tấm vé có ghi một số từ 1 đến 19 . Các vị khách được mời vào phòng biểu diễn theo thứ tự xếp hàng . Mỗi ngừoi đi vào sẽ đi thẳng đến chiếc ghế có số ghi trên tấm vé của mình. Nếu chiếc ghế này còn trống họ sẽ ngồi vào đó , nếu không họ sẽ đi tiếp và ngồi vào chiếc ghế đầu tiên vê bên phải chưa có người ngồi . Khi một vị khách đi đến chiếc ghế cuối cùng mà vẫn chưa có ghế để ngồi , họ sẽ bỏ về . Hỏi ảo thuật gia có bao nhiêu cách phát vé để cả 19 vị khách sẽ ở lại xem buổi biểu diễn ?

- Ta cho thêm một ghế số $0$ và xếp các ghế $0,1,2,...,19$ thành vòng tròn (như hình vẽ). Cho phép vị khách đi tiếp theo chiều kim đồng hồ cho đến khi nào có ghế trống thì ngồi $\Rightarrow$ Các vị khách luôn có chỗ ngồi.

- Cho phép nhà ảo thuật phát vé số $0\Rightarrow$ Có $20^{19}$ cách phát vé cho $19$ người (kể cả phát vé số $0$ )

- N/xét: Một cách phát vé thỏa mãn yêu cầu bài toán tương đương với cách xếp mới thì cách phát vé này không phát vé số $0$ (ghế số $0$ trống)
-Quy ước $a_i\equiv a_j$ nếu $i\equiv j \ (\mod 20);\ j\in \left\{1,...,19\right\} $. Ta xét cách phát vé $(a_1;a_2;...;a_{18}; a_{19})$ có ghế trống $a$ thì:
+) Cách phát vé $(a_2;a_3;...;a_{19};a_1)$ có ghế trống $a+1$
+) Cách phát vé $(a_3;a_4;...;a_1;a_2)$ có ghế trống $a+2$
...
+) Cách phát vé $(a_{1+k};a_{2+k};...;a_{18+k};a_{19+k})$ có ghế trống $a+k$

Nhóm thành $20$ cách phát vé:
$(a_1;a_2;...;a_{18}; a_{19});(a_2;a_3;...;a_{19}; a_{1});...;(a_{19};a_{1};...;a_{17}; a_{18})$
Rõ ràng các các phát vé trên là phân biệt và có ghế trống phân biệt.
Trong 20 cách phát vé trên có đúng 1 cách có ghế trống là ghế số $0$ (cách phát vé thỏa mãn đề bài)
$\Rightarrow$ Số cách phát vé thỏa mãn bài toán là: $\dfrac{20^{19}}{20}=20^{18}$ (cách) $\square$

P/s: Bài này là cách phát biểu khác của Parking Function .
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]