Cho bàn cờ hình chữ nhật \(C\) kích thước \(m\times n\) với \(M\) là tập hợp các vị trí cấm. Đặt \(p=min\left\{m,n\right\}\). Gọi \(r_k\left(M\right)\) là số cách đặt \(k\) quân xe không ăn nhau trên bàn cờ \(M\), chứng minh rằng:

 \(r_k\left(C\backslash M\right)=\sum\limits^k_{l=0}\dfrac{\left(m-l\right)!\left(n-l!\right)}{\left(m-k\right)!\left(n-k\right)!\left(k-l\right)!}r_l\left(M\right)\)

 Cờ vua 1D là trò chơi chiến thuật dành cho 2 người diễn ra trên 1 bàn cờ kích thước 1x8 với vị trí các quân ban đầu như hình vẽ:

 Bên trắng luôn là bên đi trước. Các quân cờ đi theo luật sau:

 1. Quân xe đi ngang với số ô tùy ý nhưng không được đi xuyên qua quân khác, không đi vào ô chứa quân cờ cùng màu nhưng được ăn quân của đối thủ.

 2. Quân mã đi ngang 2 ô và được đi xuyên qua quân khác. Chẳng hạn hình bên dưới, quân mã ở vị trí số 3 có thể nhảy về vị trí 1 hoặc "đi xuyên" qua quân xe đen để đến vị trí 5. Mã cũng không được nhảy vào ô đã có quân cùng màu ở đó nhưng được bắt quân của đối thủ.

 3. Quân vua có thể đi ngang 1 ô nhưng không được đi vào phạm vi tấn công của quân đối phương và hiển nhiên cũng không được đi đến những ô có quân cùng màu ở đó (vẫn được ăn quân đối thủ nếu quân này không được bảo vệ)

 Luật thắng/ thua/ hòa được xác định như sau:

 Thắng/ Thua: Một bên được công nhận là thắng nếu "chiếu" được vua đối phương mà không còn nước đi hợp lệ nào cản phá. Ví dụ trong trường hợp sau, ta thấy mã trắng chiếu vua đen nhưng vua đen không thể di chuyển và mã đen cũng không làm gì được nên bên trắng thắng.

 Hòa: Nếu xảy ra 1 trong các trường hợp sau:

 TH1: Hòa PAT: Xảy ra khi đến lượt 1 bên đi mà họ không còn nước đi nào hợp lệ trong khi vua không bị chiếu. Chẳng hạn như trong hình, đến lượt bên đen đi mà vua đen không bị chiếu nhưng đen chẳng thể di chuyển vua và mã nên ván cờ này được xử hòa.

 TH2: Bất biến 3 lần: Xảy ra khi cả 2 bên lặp lại cùng một thế trận 3 lần (cái này thì dễ hình dung rồi)

 Hỏi từ vị trí ban đầu, với ưu thế của người đi trước thì liệu có chiến thuật thắng nào dành cho bên trắng không? 

 Cho bàn cờ \(C\) bất kỳ gồm \(m\) hàng và \(n\) cột, đa thức quân xe của bàn cờ \(C\) được định nghĩa như sau:

 \(R\left(C,x\right)=r_0\left(C\right)+r_1\left(C\right)x+...+r_k\left(C\right)x^k+...=\sum\limits^{\infty}_{k=0}r_k\left(C\right)x^k\)

 trong đó \(r_k\left(C\right)\) là số cách xếp \(k\) con xe không "ăn nhau" trên bàn cờ \(C\).

  a) Gọi \(C_d,C_c\) là bàn cờ tương ứng có được khi đổi chỗ hai dòng bất kì và hai cột bất kì của \(C\). Chứng minh rằng \(R\left(C,x\right)=R\left(C_d,x\right)=R\left(C_c,x\right)\)

  b) Hai bàn cờ \(A,B\) gọi là hai bàn cờ độc lập nếu không có ô vuông vào của A và B chung hàng hoặc chung cột. VD trong hình thì A và B là hai bàn cờ độc lập:

 Chứng minh rằng nếu A, B là hai bàn cờ độc lập thì \(R\left(A\cup B,x\right)=R\left(A,x\right).R\left(B,x\right)\)

 c) Ta gọi một miền ô vuông \(S\) của \(C\) là block của bàn cờ \(C\) nếu thỏa mãn các điều kiện sau:

 i) Với bất kì hai dòng \(i,i'\) chứa ô của \(S\) và cột \(j\) không chứa ô nào của \(S\) thì hai ô \(\left(i;j\right)\) và \(\left(i';j\right)\) hoặc cùng là ô vuông của \(C\) hoặc không cùng là ô vuông của \(C\).

 ii) Với bất kì hai cột \(j,j'\) chứa ô của \(S\) và dòng \(i\) không chứa ô nào của \(S\) thì hai ô \(\left(i;j\right)\) và \(\left(i;j'\right)\) hoặc cùng là ô vuông của \(C\) hoặc không cùng là ô vuông của \(C\).

 (Lưu ý: Nếu \(C\) là bàn cờ gồm các ô vuông thì mỗi ô vuông của \(C\) được xem là một block của \(C\))

 Ví dụ trong hình thì vùng màu cam là block của bàn cờ \(C\):

 Cho \(C\) là bàn cờ các ô vuông có block S nằm trên \(m\) dòng và \(n\) cột, đặt \(p=min\left\{m,n\right\}\). Với mỗi \(0\le k\le p\), kí hiệu \(D_k\left(S\right)\) là bàn cờ có được từ bàn cờ \(C\) sau khi thực hiện các bước sau:

 1. Bỏ tất cả các ô của \(S\).

 2. Bỏ tất cả các ô thuộc \(k\) dòng tùy ý trong số \(m\) dòng của \(S\).

 3. Bỏ tất cả các ô thuộc \(k\) cột tùy ý trong số \(n\) cột chứa các ô của \(S\).

Chứng minh rằng đa thức quân xe của bàn cờ \(C\) là:

 \(R\left(C,x\right)=\sum\limits^p_{k=0}r_k\left(S\right)x^kR\left(D_k\left(S\right),x\right)\).