Couple trên bảng vuông

Đề bài:
Cho $n$ là một số nguyên dương và bảng vuông $n\times n$. Mỗi đỉnh của hình vuông đơn vị được gọi là một "nút", mỗi đoạn thẳng nối 2 nút có độ dài đơn vị là cạnh của một hình vuông đơn vị được gọi là một "dây", hai dây được gọi là một "couple" nếu hai dây đó có một nút chung và vuông góc với nhau. Hỏi có bao nhiêu cách chia $2n(n+1)$ dây trong bảng vuông đã cho thành $n(n+1)$ couple sao cho mỗi dây thuộc đúng một couple và không có nút nào cùng thuộc vào các dây nằm trong 2 couple phân biệt?

Lời giải:
Ta gọi nút chung của 2 dây thuộc 1 couple là "nút sống", các nút còn lại là "nút chết".
Ta thấy: có $(n+1)^2$ nút trong bảng và có $n(n+1)$ nút sống nên có đúng $n+1$ nút chết trong bảng đã cho.
Ta sẽ chứng minh mỗi dòng và mỗi cột có đúng 1 nút chết.
Thật vậy, giả sử tồn tại 1 dòng có nhiều hơn 2 nút chết nên có không quá $n-1$ nút sống. Mà mỗi dây nằm ngang có 1 trong 2 nút là nút sống và không có 2 dây nằm ngang nào có chung nút sống, vô lý.
Vậy mỗi dòng, mỗi cột có không quá 1 nút chết, mà có đúng $n+1$ nút chết nên mỗi dòng, mỗi cột có đúng 1 nút chết.
Với mỗi dây ta sẽ xác định "chiều" của dây là chiều từ nút chung của dây đó với dây thuộc cùng couple tới nút còn lại của dây đó. Các couple sẽ xác định nếu chiều của các dây là xác định.
Với một bộ $n+1$ nút chết thỏa mãn thì ta xác định các couple như sau: Chiều của các dây là chiều hướng đến nút chết tại dòng (hoặc cột) đó.
Dễ thấy với cách xác định này, ta nhận được 1 cách chia thỏa mãn bài ra.
Ta sẽ chứng minh, đây là cách chia couple duy nhất với mỗi bộ $n+1$ nút chết.
Giả sử tồn tại 1 nút sống $P$ và có chiều của dây từ $P$ không hướng tới nút chết.
Khi đó, ta có thể chỉ ra nút $R$ nằm ở biên của bảng vuông và $PR$ có chiều theo chiều của dây trên là một nút chết.
Từ đó suy ra số cách chia các couple thỏa mãn là: $(n+1)!$.