Math Labs

Bài 5

Cho nn là một số nguyên dương. Có n(n+1)n(n+1) phòng được xếp thành một lưới (n+1)×n(n+1)\times n. Giữa hai phòng kề nhau có một cửa. Tìm số cách chọn một tập con các cửa và khóa chúng sao cho tồn tại hai phòng SS và GG thỏa mãn: (i) SS ở hàng thứ nhất và GG ở hàng thứ (n+1)(n+1). (ii) có thể đi từ SS đến GG chỉ bằng các cửa chưa khóa.
Bước 1 trên 5: Đưa về bài đếm tính liên thông trên đồ thị
Bước trướcBước tiếp
collapse row 1→A, row n+1→B;∣E(G)∣=n2+(n−1)2,free doors=2(n−1)\text{collapse row }1\to A,\ \text{row }n{+}1\to B;\quad |E(G)|=n^2+(n-1)^2,\quad \text{free doors}=2(n-1)
Phân tích chi tiết

Vì SS có thể là bất kỳ phòng nào ở hàng đầu và GG bất kỳ phòng nào ở hàng cuối, việc tồn tại một cặp phù hợp không phụ thuộc vào việc n−1n-1 cửa nối các phòng trong hàng đầu, hay n−1n-1 cửa trong hàng cuối, có bị khóa hay không; tổng cộng có 2(n−1)2(n-1) cửa tự do như vậy. Thu gọn hàng đầu thành một đỉnh AA và hàng cuối thành một đỉnh BB, các phòng và cửa còn lại tạo thành một đồ thị G\mathcal{G} với n2+(n−1)2n^2+(n-1)^2 cạnh, và bài toán quy về đếm các tập con HH của các cạnh này sao cho AA và BB liên thông trong HH.