Cuộc hành trình dài của nhà vua

39

VÒNG TRÒN TOÁN HỌC

Cuộc hành trình dài của nhà vua

N. BELUKHOV (BULGARIA)

Bảng “trắng” của Welch thành bảng “đen” hoặc ngược lại. Do đó, lộ trình của bất kỳ vị vua nào cũng được thể hiện dưới dạng đường đi của một quân xe khập khiễng đi qua hai bàn cờ của xứ Wales, nhảy từ bàn cờ này sang bàn cờ khác khi nhà vua thực hiện một bước đi ngắn. Số lần nhảy bằng số nước đi ngắn của vua. Vì mục tiêu của chúng ta là số lần di chuyển nhỏ nhất, nên chúng ta sẽ tìm một tuyến xe què dọc theo một bảng Welch, bao gồm số phần liên tục nhỏ nhất. Hãy tô màu bảng Welch theo mẫu bàn cờ, như minh họa trong hình 2. Trên bất kỳ phần nào trên đường đi của quân xe của chúng ta, màu trắng

Dành riêng cho Evgeniy Gik

TRONG “QUANTUM” số 3 CHO NĂM 2000, MỘT ghi chú NHỎ của I. Akulich “Walks of the King” ĐƯỢC IN. Trong đó, tác giả đã đặt ra một số câu hỏi mở thú vị, trong đó có câu hỏi này: Độ dài lớn nhất có thể có của một con đường khép kín để quân vua đi quanh bàn cờ $8 \times 8$ là bao nhiêu? Chính xác hơn, hãy để vua đi vòng quanh bàn cờ, thăm từng ô một lần và với nước đi cuối cùng sẽ quay trở lại ô ban đầu. Nếu bạn nối tâm của các trường mà anh ta lần lượt đi qua các đoạn, bạn sẽ có được một đường đứt nét khép kín (rất có thể là tự giao nhau). Độ dài lớn nhất có thể có của đường đứt nét này là bao nhiêu? Rõ ràng là đường gãy bao gồm các đoạn gồm hai loại - ngắn (dài 1) và dài (dài 2). Vì vậy, chỉ cần tìm số nước đi ngắn tối thiểu có thể có cho vua là đủ. Đây là những gì chúng tôi sẽ làm. Trên thực tế, chúng ta sẽ giải bài toán trong trường hợp tổng quát - đối với các bảng $2 n \times 2 n$ (bài toán đối với các bảng có độ dài cạnh lẻ được giải khá đơn giản, như chúng ta sẽ sớm thấy). Xét bàn cờ $2 n \times 2 n$ và dựng một bàn cờ phụ gọi là bàn cờ Welch. Để thực hiện việc này, hãy xóa tất cả các ô cùng màu khỏi bảng ban đầu và thay thế mỗi ô có màu khác bằng một hình vuông có cạnh dài hơn 2 lần, được xoay $45^\circ$ quanh tâm ô (hình1).

Hình 1

Trong khi vua thực hiện các bước đi dài, tức là di chuyển theo đường chéo, nó vẫn ở trên các ô cùng màu. Hơn nữa, những nước đi như vậy của vua tương ứng với sự di chuyển của một quân “què” trên bàn cờ Welch (một quân què di chuyển như quân bình thường, nhưng chỉ di chuyển đến các ô liền kề trong khi di chuyển). Nếu chúng ta giả sử rằng có hai bàn cờ Welch - mỗi bàn cờ đại diện cho các ô trắng và đen của bàn cờ ban đầu, thì mỗi nước đi ngắn của vua có thể được hiểu là một quân xe nhảy từ

Hình 2

và các ô màu đen xen kẽ nhau nên sự chênh lệch giữa số của ô này và ô kia trên bất kỳ phần nào không vượt quá 1. Nếu bàn cờ ban đầu có kích thước $( 2 n + 1 ) \times ( 2 n + 1 )$, thì trên một trong các bảng Welch có màu sẽ có nhiều ô cùng màu hơn ô kia và không nhỏ hơn 2n + 1. Điều này có nghĩa là sẽ mất ít nhất 2n + 1 đoạn đường đi liên tục để thăm hết các ô của một bảng. Do đó, sẽ có ít nhất 4n + 2 lần nhảy từ bảng này sang bảng khác (hai lần nhảy cho mỗi đoạn đường). Vì vậy, nếu bàn cờ có kích thước lẻ thì vua đi vòng quanh bàn cờ theo một đường kín sẽ thực hiện ít nhất 4n + 2 nước đi ngắn. Đây là một con số đủ lớn để việc xây dựng một đường dẫn ví dụ tương ứng không quá khó khăn.

Bài tập. Làm đi.

Nếu bàn cờ có kích thước chẵn thì mỗi bàn cờ Welch chứa số ô vuông màu trắng và ô đen bằng nhau. Nhưng vị trí của họ sẽ cho chúng ta manh mối về lời giải. Để quân xe khi di chuyển dọc theo bàn cờ Welch, để lại dấu vết - đường nối tâm các ô mà quân xe lần lượt ghé thăm. Khi quân xe nhảy (sang bảng khác), hàng bị gián đoạn, nhưng sau đó một hàng mới sẽ bắt đầu. Nếu quân xe đã đi qua tất cả các ô, thì một số đường như vậy sẽ “bao phủ” toàn bộ bàn cờ. Chúng ta hãy tưởng tượng cắt tấm bảng ở hình 2 thành hai phần giống hệt nhau dọc theo đoạn AB. Đoạn này chia một số dòng thành nhiều phần. Lưu ý rằng nửa dưới của bảng có nhiều ô đen hơn n ô trắng. Điều này có nghĩa là có ít nhất n dòng hoặc n phần của nó bắt đầu và kết thúc trong một ô màu đen. Tương tự, nhìn vào nửa trên, chúng ta thấy có ít nhất n dòng hoặc phần của nó bắt đầu và kết thúc bằng một hình vuông màu trắng. Tổng cộng có ít nhất 2n dòng hoặc các phần của chúng. Nhưng việc dán các phần của các đường dọc theo đoạn AB sẽ làm giảm số lượng của chúng không quá n (rốt cuộc chỉ có thể có n vị trí dán).