Trò chơi lúc 15 tuổi

26

Trò chơi lúc 15 tuổi
O. T. Dolgov

• Vậy ra đây là bài toán nổi tiếng!
• Giải quyết thế nào?
• Không hẳn! Tình trạng đã được biết,
  và lời giải Tôi không biết…
  Cối xay. Đối thoại

1. Lời gửi Sam Loyd
   Trong «Kvant» Tôi đã nói về cuốn sách “Giải trí toán học” của Martin Gardner («Kvant», 1973, số 6). Chương thứ 33 của “Giải trí” có tên là “Trò chơi của 15 và những câu đố khác”.

Có 15 quân cờ có các số nằm trong một ô vuông phẳng. Sự sắp xếp các quân cờ “thông thường” được thể hiện trong Hình 1. Hình 2 cho thấy một cách sắp xếp khác: các quân cờ số 14 và 15 được sắp xếp lại. Điều cần thiết là bằng cách di chuyển từng quân cờ một để chuyển sự sắp xếp này sang trạng thái “bình thường”. Các quân cờ được chuyển đến một không gian trống liền kề; chúng không được phép lấy ra khỏi hộp.

Trò chơi được phát minh vào thế kỷ 15 bởi Sam Loyd vào những năm bảy mươi. Cơn sốt của anh nhanh chóng lan rộng khắp nước Anh, rồi lan rộng khắp eo biển Manche. Gardner sử dụng một câu trích dẫn của chính Lloyd để kể câu chuyện của mình về điều này:

“Mọi người thực sự phù hợp với câu đố này. Những câu chuyện được truyền miệng nhau về một người chủ cửa hàng quên mở cửa hàng của mình, về một người báo hiệu đứng dưới ngọn đèn đường trong một đêm mùa đông dài với hy vọng nhớ lại cách anh ta giải được bài toán…

Một biên tập viên nổi tiếng ở Baltiym kể rằng có lần ông đi ăn trưa vào buổi trưa và mãi đến khuya mới bị nhân viên báo chí phát hiện đang ngồi bên bàn đẩy qua đẩy lại những miếng bánh nhỏ trên đĩa!

Năm 1879, lý thuyết toán học của trò chơi 15 được xuất bản, sau đó trò chơi này nhanh chóng lỗi thời.

Lý thuyết toán học làm giảm sự quan tâm đến câu đố của Lloyd không được Gardner giải thích trong cuốn sách của ông.

27

trò đùa. Trong khi đó, lý thuyết này rất đơn giản và đáng tôn trọng.

2. Hoán vị chẵn và lẻ
   Hãy sắp xếp các số 1, …, 15 theo thứ tự ngẫu nhiên. Ví dụ như thế này:
   1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11,
   12, 15, 14, 13, (1)
   hoặc như thế này:
   1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11,
   12, 14, 15, 13. (2)

Sự sắp xếp nào trong số này được gọi là hoán vị.
Chúng ta sẽ nói rằng trong một hoán vị cho trước, các số i và j tạo thành một hỗn loạn nếu i > j, nhưng i ở bên trái j trong hoán vị này.
Ví dụ. Số 8 và 6 trong hoán vị (1).
Chúng ta gọi một hoán vị là lẻ (lẻ) nếu nó có số rối loạn chẵn (lẻ).
Ví dụ. Trong hoán vị (1) có chín, và trong hoán vị (2) có tám rối loạn, do đó (1) là hoán vị lẻ và (2) là hoán vị chẵn.

3. Sắp xếp lại và chơi lúc 15
   Hãy vẽ một đường đứt nét trên ô để chơi số 15, như trong Hình 3. Hãy đi theo đường đứt nét này từ góc trên bên trái của ô và viết ra các số của quân cờ mà chúng ta sẽ lần lượt đi qua.
   Ví dụ. Nếu các quân cờ được đặt như Hình 1 thì chúng ta nhận được hoán vị (1); đối với sự sắp xếp trong Hình 2, kết quả là hoán vị (2).
   Đi qua ô trống, chúng ta không viết số nào. Do đó, cùng một hoán vị tương ứng với mười sáu cách sắp xếp quân cờ khác nhau trong hộp. Ví dụ, hoán vị
   1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
   12, 13, 14, 15
   tương ứng với bất kỳ vị trí nào trong Hình 4.
   Khi chơi 15 quân cờ, bạn có thể chơi lại theo chiều ngang và chiều dọc bằng cách đi theo đường liền kề đến ô vuông. Nếu quân cờ được chơi lại theo chiều ngang thì cả vị trí cũ và vị trí mới đều tương ứng với indo, hoán vị giống nhau (Hình 4, a, b). Nếu trình kiểm tra được phát lại theo chiều dọc thì có thể hoán vị không thay đổi (Hình 4, b, b), nhưng vị trí cũ và mới chung tương ứng với các hoán vị khác nhau (Hình 5).
   Tuy nhiên, những hoán vị này luôn có cùng giá trị (cả hai đều chẵn hoặc cả hai số lẻ).
   Trước tiên hãy kiểm tra điều này trong trường hợp được mô tả trong Hình 5. Vị trí trong Hình 5, a tương ứng với hoán vị
   …, 6, 5, 11, 9, 10, …, (a) vị trí trong Hình 5, b - hoán vị
   …, 10, 6, 5, 11, 9, … (b) (dấu chấm lửng thay thế cho khớp trong

28

(a) và (6) số). Khi chuyển từ (a) đến (6), một rối loạn (11, 10) biến mất và ba rối loạn mới (10, 6), (10,5) và (10, 9) xuất hiện. Tổng số rối loạn trả về bằng 2, vì vậy (a) và (6) thực sự có cùng mức chẵn lẻ.

Trong trường hợp chung, khi bộ kiểm tra có số $n$ được chuyển từ ô $A$ sang ô trống $B$ (Hình 6), việc chứng minh được thực hiện theo cách tương tự. Trên đoạn đường đứt nét giữa $A$ và $B$ luôn có số quân cờ chẵn. Giả sử $y$ $m$ trong số chúng có số nhỏ hơn $n$ và $k$ có số lớn hơn $n$; sau đó $m$ tình trạng bất ổn khi di chuyển quân cờ biến mất và $k$ tình trạng bất ổn quay trở lại $k$ - $m$. Đây là số chẵn vì theo điều kiện số $k + m$ là số chẵn. Như vậy, các hoán vị tương ứng với cách sắp xếp cũ và mới nhất thiết phải có tính chẵn lẻ như nhau.

4. Tính không thể giải được của câu đố
   Loyda

Các hoán vị (1) và (2), cách sắp xếp tương ứng của các bộ kiểm tra trong Hình 1 và 2, có các giá trị chẵn lẻ khác nhau. Điều này có nghĩa là những sự sắp xếp này không thể có được từ nhau: Câu đố của Loyd là không thể giải được.

5. Nó sẽ thành công hay nó sẽ không thành công?
   Chà, nếu bạn sắp xếp ngẫu nhiên các quân cờ trong hộp thì sao? Trong trường hợp nào câu đố sẽ hoạt động (trạng thái được đặt thành “bình thường”) và trong trường hợp nào nó sẽ không hoạt động?

Chúng ta đã biết: nếu hoán vị tương ứng với vị trí là số chẵn thì câu đố sẽ không hoàn thành. Nếu nó kỳ quặc thì sao? Sau đó, hóa ra, nó chắc chắn sẽ thành công.

Tuyên bố này có thể được chứng minh theo những cách khác nhau. Dưới đây chúng tôi sẽ thực hiện việc này theo cách gần giống như S. Bobrov trong cuốn sách “Người bạn phép thuật” *).

6. Cách nhảy qua hai quân cờ
   Hãy vẽ một đường khép kín trên hộp dưới dạng chữ P (Hình 7). Dọc theo con đường này, các quân cờ có thể được di chuyển lần lượt, “trong một tệp”. Do đó, chẳng hạn, có thể chuyển đổi dần cách sắp xếp như trong Hình 8, $a$ thành “bình thường” (Hình 8, 6, 8, 2, $\partial$). Điều này rất dễ thực hiện vì thứ tự tương đối của các quân cờ dọc theo đường P (bắt đầu bằng quân cờ 1, theo chiều kim đồng hồ) là như nhau:
   {1, 2, 3, 4, 8, 12, 15, 11, 7, 6, 10, 14, 13, 9, 5}.

Bây giờ chúng ta giả sử rằng đối với một số cách sắp xếp quân cờ thì thứ tự này khác và chúng ta muốn chuyển đổi cách sắp xếp này thành một cách sắp xếp “bình thường”. Để làm được điều này, sẽ rất tốt nếu chúng ta học cách cố tình thay đổi thứ tự các quân cờ dọc theo đường P.

*) Bobrov S. Người bạn kỳ diệu. Detgiz, 1946, tr. 29-41, 89-117.

29

Dưới đây chúng tôi sẽ chỉ ra một kỹ thuật mà điều này có thể được thực hiện.

Để những người kiểm tra có số $i, j$ và $k$ đứng cạnh nhau dọc theo đường dẫn $\Pi$ (Hình 9, a). Bằng cách di chuyển tất cả các quân cờ “trong một tập tin” dọc theo $\Pi$, có thể dễ dàng đảm bảo rằng các quân cờ $i, j, k$ và ô trống $B$ được đặt như trong Hình 9, b. Bây giờ di chuyển quân cờ $i$ sang ô vuông trống $B$, chúng ta nhận được thứ tự $\{..., j, k, i, ...\}$ từ thứ tự $\{..., i, j, k, ...\}$ - quân cờ có số $i$ được “uốn cong” theo chiều kim đồng hồ qua hai quân cờ lân cận: $j$ và $k$.

Thật dễ dàng để làm cho bất kỳ quân cờ nào “nhảy” qua hai quân cờ liền kề ngược chiều kim đồng hồ. Ví dụ: để quân cờ $k$ được “cúi xuống” qua $i$ và $j$ trong Hình 9, trước tiên bạn phải di chuyển quân cờ “trong một tập tin” dọc theo đường dẫn $\Pi$ đến vị trí hiển thị trong Hình 9, sau đó di chuyển quân cờ $k$ đến khoảng trống $B$.

Vì vậy, chúng tôi đã chỉ ra một kỹ thuật mà bạn có thể khiến bất kỳ quân cờ nào “nhảy” qua các quân cờ đang đứng trên đường $\Pi$ bên cạnh nó.

30

7. Tất cả trừ hai đều được đặt đúng chỗ!
   Sử dụng kỹ thuật này, có thể dễ dàng chuyển đổi bất kỳ cách sắp xếp nào của quân cờ thành một trong hai cách sắp xếp như trong Hình 10, a, b.

Trước hết, chúng ta sẽ dẫn quân cờ 2 dọc theo con đường đến quân cờ 1. Nhảy ngược chiều kim đồng hồ qua hai quân cờ nhiều lần nếu cần, chúng ta sẽ đưa nó đến vị trí “của nó” (cạnh “một”) hoặc đến quân cờ lân cận (giữa quân cờ 1 và quân cờ 1 sẽ có một quân cờ nhất định i), - trong cả hai trường hợp, chúng ta sẽ bị bỏ lại vào thời điểm bước nhảy tiếp theo vượt qua quân cờ 1. Nếu giữa “hai” và quân cờ tôi sẽ vẫn là một “một”, hãy làm cho nó nhảy qua hai quân cờ (bao gồm cả qua “hai”) theo chiều kim đồng hồ - khi đó “hai” sẽ bị xóa bên cạnh “một” (và ở phía bên phải).

Sau đó, theo cách tương tự, chúng ta sẽ dẫn “ba” đến “một” và “hai”. Sau đó là “bốn” - đến “một”, “hai” và “ba”. Và cứ thế - cho đến ô kiểm tra 13.

Sau đó, di chuyển tất cả các quân cờ “trong một tập tin” dọc theo P, chúng ta sẽ đến một trong hai vị trí được hiển thị trong Hình 10.

8. Vị trí tốt và bằng phẳng
   Do đó, tất cả các sắp xếp kiểm tra được chia thành hai loại. Vị trí của loại 1 có thể được chuyển đổi giống như trong Hình 10, a, vị trí của loại 2 - như trong Hình 10, b.

Hãy suy nghĩ xem tại sao câu nói trong đoạn 5 lại tiếp nối từ đây và những gì khác tiếp theo từ đây.

Nếu một cách sắp xếp P nhất định có thể được dịch thành cách sắp xếp Q thì ngược lại, Q có thể được dịch thành P. Do đó, tất cả các cách sắp xếp loại 1 đều có thể được dịch sang nhau. Theo đoạn 4, các hoán vị tương ứng có cùng tính chẵn lẻ và số lẻ, vì vị trí trong Hình 10, a tương ứng với một hoán vị lẻ

1, 2, 3, 4, 5, 10, 11, 15, 12, 9, 6, 7, 8, 13, 14 (mười ba rối loạn).

Tất cả các cách sắp xếp của lớp thứ 2 đều được dịch sang nhau theo cùng một cách và thậm chí các hoán vị cũng tương ứng với chúng.

Do đó, vị trí “bình thường” thuộc về loại 1 và vị trí trong Hình 2 – thuộc loại thứ 2. Chúng ta gọi vị trí loại 1 là tốt và vị trí loại 2 là xấu.

Chúng ta hãy tóm tắt những gì đã được chứng minh.

Sự sắp xếp tốt là những và chỉ những sự sắp xếp tương ứng với các hoán vị lẻ, tất cả đều có thể được chuyển thành sự sắp xếp được mô tả trong Hình 1.

Tất cả các cách sắp xếp khác đều phẳng, chúng tương ứng với các hoán vị chẵn, chúng không thể được chuyển sang cách sắp xếp như trong Hình 1 và có thể được chuyển sang cách sắp xếp như trong Hình 2.

Bình luận. Các thông điệp được đưa ra trong đoạn 6 và đoạn 7 sẽ thực sự cho phép

32

bất kỳ hoán vị nào của các số 1, . . ., n, bạn có thể đi đến bất kỳ hoán vị nào khác của cùng các số, đổi chỗ cho chỉ một vài số lân cận.

5. Trò chơi hai tầng trong 31. Trong một hộp có kích thước $2 \times 4 \times 4$, chúng tôi đặt 31 hình khối “ở 2 tầng”: 16 cốc ở dưới cùng, 15 cốc ở trên cùng. Chúng ta sẽ để trống một chỗ trong hộp.

Chúng ta sẽ viết các số trên hình lập phương: 1, . . ., 31, và trên mỗi khối, chúng ta viết số của nó hai lần: ở cạnh trên và dưới.

Chúng ta sẽ làm cho đáy và nắp hộp kín khí và tạo các lỗ ở phía trước mỗi khối lập phương (để các khối không lọt qua mà có thể dễ dàng di chuyển mà không cần lấy ra khỏi hộp). Bây giờ hộp có thể được sắp xếp lại theo ý muốn: nó không còn có “đỉnh cố định” và “đáy cố định” nữa. Các hình khối có thể được trộn lẫn trên mỗi tầng và di chuyển từ tầng này sang tầng khác.

Kết quả là một “trò chơi hai tầng 31”. Phát triển một lý thuyết cho trò chơi này.

6. Chơi 15 trên một hình trụ. Chúng tôi cắt hình trụ rỗng (Hình 12) thành 16 miếng cong, mỗi miếng một miếng, tạo thành 4 vết cắt dọc và 3 vết cắt ngang. Hãy vứt đi một con cờ. Ta đổi các số còn lại 1, . . ., 15 và đặt nó vào một chiếc hộp đặc biệt có hình khoang giữa hai hình trụ. Chúng ta hãy tạo 16 lỗ trên hình trụ có lỗ bên ngoài - “trò chơi 15 lỗ trên hình trụ” đã sẵn sàng (Hình 13).

Như trong một trò chơi thông thường gồm 15 người, các quân cờ được phép di chuyển lần lượt từng quân cờ sang một ô trống liền kề; Ngoài ra, được phép xoay đồng thời 4 quân cờ (Hình 14), giống như vòng bi.

Có thể chuyển đổi bất kỳ cách sắp xếp quân cờ nào thành bất kỳ cách sắp xếp nào khác không?

Bình luận. Không cần thiết phải làm hộp và cờ hình trụ. Bạn có thể sử dụng trò chơi thông thường ở 15, cho phép bổ sung “cdv tuần hoàn của dòng” (Hình 15): ví dụ: “cdv tuần hoàn của dòng 1” chuyển vị trí được hiển thị trong Hình 15, a, sang vị trí được hiển thị trong Hình 15, 6.

Sau đó, sự thay thế sẽ giúp bạn đối phó với điều khiển 6 và giúp chúng ta hình thành bài toán tiếp theo dễ dàng hơn.

33

7. Trò chơi 16 trên hình xuyến. Để tạo hình trụ từ hình chữ nhật, bạn cần dán các cạnh thẳng đứng đối diện lại với nhau. Sau đó, nếu bạn dán các cạnh ngang đối diện lại với nhau (Hình 16), bạn sẽ có được một cây lau nhà (bề mặt bánh rán).

Để thực hiện “trò chơi 16 con trên hình xuyến”, không nhất thiết phải cắt cờ đam từ chiếc bánh rán. Trong một trò chơi thông thường gồm 15, chỉ cần lấp đầy ô trống bằng quân cờ số 16 và cắt “dwg tuần hoàn và các hàng và cột” (Hình 17).

a) Có thể chuyển sự sắp xếp như trong Hình 18, a, sang vị trí như trong Hình 18, b với các dw như vậy không?

b) Bất kỳ vị trí nào có thể được chuyển đổi sang bất kỳ vị trí nào khác?

b) Giải quyết lời hứa bài toán về trò chơi $n^2$ trên hình xuyến.

Bài viết này đã được chuẩn bị xuất bản khi các biên tập viên của «Kvant» nhận được một lá thư về trò chơi năm 15 tuổi từ một cậu học sinh - thứ mười