Math Labs

Bài 5

Cho nn và kk là các số nguyên dương sao cho k≥nk \ge n và k−nk - n là số chẵn. Có 2n2n bóng đèn được đánh số 1,2,…,2n1, 2, \ldots, 2n, mỗi bóng có thể bật hoặc tắt. Ban đầu tất cả các bóng đều tắt. Ta xét các dãy thao tác: ở mỗi bước, một bóng đèn được chuyển trạng thái (từ bật sang tắt hoặc từ tắt sang bật). Gọi NN là số dãy gồm kk bước và kết thúc ở trạng thái các bóng từ 11 đến nn đều bật, còn các bóng từ n+1n+1 đến 2n2n đều tắt. Gọi MM là số dãy gồm kk bước, kết thúc ở trạng thái các bóng từ 11 đến nn đều bật và các bóng từ n+1n+1 đến 2n2n đều tắt, nhưng trong suốt quá trình không có bóng nào từ n+1n+1 đến 2n2n từng được bật. Tính NM\dfrac{N}{M}.
Bước 1 trên 3: Đặc trưng các dãy N và M bằng tính chẵn lẻ của số lần chuyển trạng thái
Bước trướcBước tiếp
Hiểu nôm na

Bắt đầu với tất cả bóng đèn đều tắt, một bóng kết thúc ở trạng thái bật khi và chỉ khi nó được chuyển trạng thái một số lần lẻ, và tắt khi và chỉ khi số lần đó chẵn.

A={1,…,n}, B={n+1,…,2n};N:odd on A, even on B;M:odd on A, 0 on BA = \{1,\ldots,n\},\ B = \{n+1,\ldots,2n\}; \quad \mathcal{N}: \text{odd on } A,\ \text{even on } B; \quad \mathcal{M}: \text{odd on } A,\ 0 \text{ on } B
Phân tích chi tiết

Viết một dãy kk bước dưới dạng (a1,…,ak)∈(A∪B)k(a_1,\ldots,a_k) \in (A \cup B)^k, trong đó A={1,…,n}A=\{1,\ldots,n\} và B={n+1,…,2n}B=\{n+1,\ldots,2n\}. Tập N\mathcal{N} (có kích thước NN) gồm các dãy trong đó mỗi i∈Ai \in A xuất hiện số lần lẻ và mỗi n+i∈Bn+i \in B xuất hiện số lần chẵn; tập con M\mathcal{M} (có kích thước MM) gồm các dãy trong đó mỗi i∈Ai \in A xuất hiện số lần lẻ và không có phần tử nào của BB xuất hiện (với M>0M > 0 vì k≥nk \ge n và k−nk - n là số chẵn).