Như mọi khi, tôi quan tâm đến bài tổ hợp trong đề năm nay:
Let n and k be positive integers with k ≥ n and k−n an even number. Let 2n lamps labelled 1, 2, . . . , 2n be given, each of which can be either on or off. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on).
Let N be the number of such sequences consisting of k steps and resulting in the state where lamps 1 through n are all on, and lamps n + 1 through 2n are all off.
Let M be the number of such sequences consisting of k steps, resulting in the state where lamps 1 through n are all on, and lamps n + 1 through 2n are all off, but where none of the lamps n + 1 through 2n is ever switched on.
Determine the ratio N/M.
Bài này dễ một cách đáng ngạc nhiên so với bài tổ hợp năm ngoái. Bản thân câu hỏi đã gợi ý hướng suy nghĩ: tính N/M có nghĩa là ta nên xét tương quan giữa các chuỗi on/off loại 1 và các chuỗi on/off loại 2. Nôm na, N - tổng số các chuỗi loại 1 - là tổng số các chuỗi có k phần tử thuộc tập {1, 2, …, 2n} sao cho mỗi phần tử trong {1, …, n} xuất hiện một số lẻ lần, và mỗi phần tử trong {n+1, …, 2n} xuất hiện một số chẵn lần. Còn M - tổng số chuỗi loại 2 - là tổng số các chuỗi giống như loại 1 nhưng các phần tử trong {n+1, …, 2n} không xuất hiện lần nào.
Phản ứng đầu tiên của tôi là: lấy một chuỗi loại 2 và xây dựng từ đó một số X chuỗi loại 1. Nếu mỗi chuỗi loại 2 tương ứng với chính xác X chuỗi loại 1 (one-to-many mapping), và các bộ X phần tử này không giao nhau, và mỗi phần tử loại 1 đều nằm trong một bộ X chuỗi nào đó, thì ta kết luận N/M = X. Phần còn lại để cho các bạn đọc. [Cần một fact đơn giản sau: cho một tập S kích thước y, tổng số tập con của S với lực lượng chẵn là 2 lũy thừa (y-1).]
Bài này rất có tinh thần “định trị một đại lượng bằng hai cách“. Do tập các chuỗi loại 2 là tập con của tập các chuỗi loại 1, cũng có thể hiểu rằng ta phân hoạch tập các chuỗi loại 1 ra làm các tập con có kích thước X, sao cho mỗi tập có chính xác một chuỗi loại 2. Cách hiểu thứ hai này tuy có vẻ dễ dàng hơn trong ngữ cảnh của bài toán này, nhưng tôi không thích nó vì nó không “tổng quát” bằng. Nếu cách xây dựng như trên không thỏa mãn điều kiện “không giao nhau” (disjointness) thì ta phải xây dựng một “many-to-one map” ngược lại từ loại 1 vào loại 2 rồi tính tỉ lệ.
Chủ đề: Combinatorics | Bình luận (1) »
Bản để in