Ghi chú cờ vua và toán học

49

Nữ hoàng—người canh gác

Trong phần trước của ghi chú*) chúng tôi đã xác định rằng quân mã có thể di chuyển xung quanh tất cả các ô của bàn cờ 8x8, chỉ nâng một lần trên mỗi ô.

Bài toán đi ngang một bàn cờ thông thường với các quân cờ khác được giải quyết đơn giản hơn nhiều. Ví dụ: đối với Lada, tuyến đường như vậy được hiển thị trong Hình 1. Ở đây

Cơm. 1.

Xe được thêm vào mục tiêu của nó, thực hiện 14 lượt trên đường đi. Chứng minh rằng số này không thể giảm được.

Con đường được chỉ định (nhân tiện, nó cũng phù hợp với nữ hoàng và vua) không bị đóng. Tuy nhiên, chúng ta có thể

*) Xem «Kvant», số 8, 9.

Cũng có thể đề xuất một tuyến đường khép kín (Hình 2). Xe đang ở đây

Cơm. 2.

mong muốn từ trường cuối cùng trong hành trình của họ - a2 có thể quay trở lại trường ban đầu - a1. Hãy tự mình nhận thấy rằng trên một bảng số lẻ (ví dụ: 7x7 hoặc 9x9), một đường dẫn kín cho phím đàn không còn tồn tại nữa.

Rõ ràng là đối với quân tượng bài toán không được đặt chính xác trong trường hợp chung ( quân tượng chỉ có thể di chuyển trên các ô vuông cùng màu), nhưng nếu chúng ta chỉ giới hạn ở các ô vuông màu trắng hoặc đen thì cũng có thể dễ dàng giải quyết được.

Bây giờ chúng ta chuyển sang một trong những vật liệu phổ biến nhất -

matic bài toán trên bàn cờ. Những bài toán này được liên kết với nhiều cách sắp xếp hình khác nhau, vì vậy chúng thường được gọi là tổ hợp. Xin thưa, nổi tiếng nhất trong số đó là “bài toán về tám quân hậu” sau đây, do nhà toán học vĩ đại người Đức F. Gauss đặt ra vào năm 1850.

Nhìn 8 quân hậu trên bàn cờ

Cơm. 3.

để không có hai người nào chạm vào nhau*).

Hình 3 cho thấy một trong những khả năng

*) Tất nhiên, theo quan điểm cờ vua, hai quân cùng màu không thể đe dọa nhau, nhưng chúng ta hiểu theo thuật ngữ truyền thống.

50

có thể lời giải bài toán, tổng cộng có 92 cái. Người ta cũng đã chứng minh rằng tất cả chúng đều có được từ 12 vị trí cơ bản bằng cách sử dụng phản xạ gương và xoay bảng 90°, 180° và 270°. Ví dụ: phản ánh vị trí gương (so với đường chấm) của phép thu gọn, chúng ta thu được một vị trí khác xác lập chúng ta (Hình 4) *).

Điều tò mò là chính Gauss ban đầu đã tưởng tượng rằng bài toán chỉ cho phép 72 lời giải, và nghi ngờ tính đúng đắn của số 92. Ở chúng tôi, bài toán này và những số khác tương tự sẽ được giải quyết trong vài phút. Chỉ cần soạn một số chương trình và nhập chúng vào máy tính là đủ, và chẳng bao lâu nữa tất cả 92 vị trí sẽ được in.

Chúng ta hãy đặt ra hai câu hỏi tương ứng dẫn chúng ta đến hai lớp tổ hợp đa dạng bài toán.

*) Điều bài toán này được giải quyết chi tiết trong cuốn sách của L. Ya. Okunev “Tổ hợp bài toán trên bàn cờ” (ONTI NKTP Liên Xô, 1936)

1. Số quân giống hệt nhau tối đa (quân hậu, quân xe, quân mã, quân tượng và quân hậu) có thể được xem xét trên bàn cờ là bao nhiêu để không có hai quân nào triệt tiêu lẫn nhau?

2. Có thể xếp tối đa bao nhiêu quân giống hệt nhau trên bàn cờ để không có hai quân nào triệt tiêu nhau?

Số đầu tiên trong lý thuyết đồ thị được gọi là số ổn định bên trong và số thứ hai là số ổn định bên ngoài. Những khái niệm này không hề trừu tượng và đóng một vai trò quan trọng trong nhiều vấn đề toán học. Một ví dụ là nổi tiếng sau đây

Bài tập về đồng hồ. Trong nhà tù thành phố N, bạn có thể thấy mỗi phòng giam đều có lính gác. Ở tại một trong các phòng giam, người canh gác cũng nhìn thấy những gì đang xảy ra ở một số phòng giam khác, từ đó hành lang dẫn đến phòng giam này. Số lượng lính canh tối đa cần thiết để giám sát tất cả các camera là bao nhiêu?

Nếu bàn cờ được coi như một nhà tù (xin người chơi cờ tha thứ cho chúng ta về sự tương tự như vậy), và các ô của nó được coi là ô, còn các chiều dọc, ngang và chéo là hành lang, thì “lính gác” là điều tự nhiên nhất để bổ nhiệm các quân cờ có thể dẫn đầu cuộc tấn công theo bất kỳ hướng nào.

Hóa ra 5 quân hậu hoàn toàn có khả năng đương đầu với toàn bộ “nhà tù” cờ vua (Hình 5). Về cơ bản, chúng tôi đã xác định số lượng ổn định bên ngoài của các nữ hoàng là bằng 5 (không khó để chỉ ra rằng vẫn chưa đạt được bốn giờ). Người ta đã chứng minh rằng có 4860 phương pháp có thể được xem xét

Cơm. 5.

5 nữ hoàng canh gác. Nhân tiện, trong ví dụ của chúng tôi, các nữ hoàng có một đặc tính thú vị khác: bản thân họ không cắt đứt lẫn nhau.

Từ trên cho thấy, để một quân hậu đơn độc của kẻ thù xuất hiện (không có quân vua nào trên bàn cờ) thì chỉ cần có 5 quân hậu là đủ. Tuy nhiên, người ta biết rằng trong cờ đam, 3 bộ giảm chấn có thể đối phó với một (nếu nó không ở trên “đường cao tốc”), mặc dù chúng không thể giữ tất cả các ô vuông màu đen của bàn cờ cùng một lúc. Thật thú vị khi tìm hiểu xem liệu có thể tạo ra một quân hậu đối phương với ít hơn năm quân hậu hay không.

51

Nếu đặt 9 quân hậu lên bàn cờ thì ít nhất hai trong số đó sẽ nằm cùng chiều dọc hoặc ngang, tức là chúng sẽ đe dọa lẫn nhau. Như vậy, số lượng ổn định bên trong của quân hậu là 8 (Hình 3, 4) và tổng số vị trí phù hợp là 92.

Đặc biệt dễ dàng tìm thấy bài toán để giải quyết cho quân xe - có lẽ, tính đơn giản của nó đã thể hiện rõ. Bạn phải có lính gác

Cơm. 6.

8, chỉ cần đặt chúng dọc hoặc ngang bất kỳ là đủ. Cũng dễ dàng chứng minh rằng số ổn định nội tại của một quân xe là 8 và có 8 vị trí tương ứng! — số hoán vị của 8 phần tử *) (n!=1·2·····n). Vị trí trên Hình 6 thỏa mãn yêu cầu chung.

Chứng minh rằng nếu các quân xe được xếp bằng nhau, tức là khác nhau thì cần phải xác định vị trí

*) Ví dụ, xem bài viết của N. Ya. Vilenkin “Tổ hợp” («Kvant» Số 1, 1971).

đã có (8!) ². Trên một tấm bảng có kích thước n×n, các số này lần lượt bằng n! và (n!) 2.

Để đối phó với toàn bộ bàn cờ, chỉ cần có số quân tượng bằng quân xe là đủ - 8 (Hình 7). Tuy nhiên, có thể đặt nhiều quân tượng lên bàn cờ để chúng không đe dọa nhau hơn số lượng 14 quân (Hình 8). Để chứng minh khoảng cách, các đường chéo đi lên từ trái sang phải (trong Hình 8 chúng được chấm), tổng cộng có 15 đường chéo như vậy. Mỗi người trong số họ không thể có nhiều hơn một giám mục, vì các giám mục không được đe dọa lẫn nhau. Do đó, tổng số giám mục không vượt quá 15. Cũng không thể sắp xếp chính xác 15 giám mục: phần ngoài cùng của các đường chéo của chúng ta sẽ được tạo thành từ một hình vuông duy nhất. Do đó, số yêu cầu không quá 14. Tuy nhiên, từ lời giải được hiển thị trong Hình 8. Các tính toán tương tự cho thấy rằng trên một bảng có kích thước n×n, bạn có thể đặt không quá 2n - 2 giám mục.

Chứng minh rằng số lượng các thỏa thuận giám mục được chấp nhận trên một cơ sở tùy ý

Cơm. 7.

Cơm. 8.

bảng bằng bình phương của một số nhất định.

Bây giờ chúng ta hãy chuyển sang ngựa. Bằng cách đặt 32 hiệp sĩ vào một ô trắng hoặc một ô đen, chúng ta sẽ tìm ra cách sắp xếp sao cho họ không đe dọa lẫn nhau. Hãy chứng minh rằng 32 là con số ổn định nội tại của các hiệp sĩ. Để làm điều này, chúng ta sẽ chia bảng thành 8 hình chữ nhật bằng nhau (Hình 9). Dễ dàng nhận thấy con ngựa được đặt

Một hình chữ nhật tấn công chính xác một hình vuông của cùng một hình chữ nhật và đối với bất kỳ hai hiệp sĩ nào như vậy, các trường mà chúng tấn công là khác nhau. Vì mỗi hình chữ nhật có 8 ô vuông nên có thể đặt tối đa 4 hiệp sĩ bên trong nó mà không đe dọa lẫn nhau và tổng số không vượt quá $4 \times 8 = 32$. Chứng minh rằng chỉ có hai cách sắp xếp được đề cập - quân mã chỉ đứng trên ô trắng hoặc chỉ trên ô đen.

Số lượng ổn định bên ngoài cho ngựa là 12 (Hình 10). Bây giờ chúng ta hãy đối phó với các vị vua. Dễ dàng kiểm tra rằng không thể xếp nhiều hơn 16 vị vua không liền kề nhau (tức là không đe dọa lẫn nhau) (Hình 11).

Số ổn định bên ngoài cho các vị vua

Cơm. 9.

bên phải 9 (Hình 12). Mỗi trong số 9 hình chữ nhật được tô sáng ở Hình 12 có một hình vuông chỉ có thể bị đe dọa bởi một vị vua đứng trên hình vuông của cùng một hình chữ nhật. Vì vậy, để tất cả các ô đều có nguy cơ thì mỗi ô trong số 9 phần phải có ít nhất một quân Vua, số yêu cầu là 9.

Cơm. 11.

Cơm. 12.

Rõ ràng, hai con tốt không thể đe dọa lẫn nhau cùng một lúc. Tuy nhiên, nếu ở câu hỏi 1 (tr. 50) thay từ “nhau” bằng từ “ít nhất một cái khác” và các hang động được phép đứng trên đường ngang đầu tiên thì câu hỏi 1 và 2 cũng đúng đối với các hang động. Đáp số là số 32 và vị trí của các quân Tốt ở Hình 12.

Cơm. 13.

Sunke 13 đáp ứng được yêu cầu chung.

Kết quả nghiên cứu của chúng tôi có thể được tóm tắt bằng cách điền vào bảng (xem trang 51).

Bạn phải tái tạo lại bằng chứng còn thiếu, tìm số vị trí tương ứng và rút ra kết luận từ bảng. Với tư cách là thang đo dịch vụ bài toán, chúng tôi có thể đề xuất tất cả những thang đo chúng tôi đã sử dụng, nhưng trên bảng có kích thước $n \times n$*). Lưu ý rằng một số trong số chúng có trọng số phức tạp, trong khi một số khác thì lời giải vẫn chưa được tìm thấy. Ví dụ, số lượng ổn định bên ngoài của nữ hoàng vẫn chưa được biết. Nói cách khác, vấn đề sau vẫn chưa được giải quyết.

Vấn đề. Số lượng quân hậu nhỏ nhất có thể đặt trên một bàn cờ có kích thước $n \times n$ sao cho tất cả các ô trống của nó đều bị đe dọa?

*) Một số bài toán như vậy được phân phối trong cuốn sách của A. M. Yaglom và I. M. Yaglom “Không sơ cấp bài toán trong bài thuyết trình tiểu học”, M., Fizmatgiz, 1954.