Hai trò chơi với que diêm

4

HAI TRÒ CHƠI VỚI QUE DIÊM

I. M. Iaglom

Trong bài này chúng tôi sẽ kể cho các bạn về các trò chơi “nim”
và “i-zian-shi-tsy”. Cả “nim” lẫn “i-zian-shi-tsy” đều là những trò chơi dân gian Trung Quốc; “i-zian-shi-tsy” dịch là “chọn đá” (dĩ nhiên, việc thay đá bằng que diêm trong điều kiện của trò chơi không làm thay đổi bản chất của nó). Về sau các trò chơi này đã truyền sang châu Âu; đã có một thời trò chơi “nim” phổ biến ở Tây Âu.

5

Hãy nêu luật của các trò chơi này.

Trò chơi “nim”
Trên bàn có ba đống que diêm. Hai người chơi lần lượt lấy que diêm từ các đống này, và trong một lượt người chơi có thể lấy bất kỳ số que diêm nào từ một (bắt buộc chỉ từ một!) đống. Người lấy que diêm cuối cùng được coi là thắng.

Trò chơi “i-zian-shi-tsy”
Trên bàn có hai đống que diêm. Hai người chơi lần lượt lấy que diêm từ các đống này, và trong một lượt người chơi có thể lấy bất kỳ số que diêm nào từ một đống, hoặc lấy số que diêm bằng nhau (nhưng là bất kỳ số nào!) từ cả hai đống. Người lấy que diêm cuối cùng được coi là thắng.

Bài toán là xác định ở những vị trí ban đầu nào (tức là với số que diêm nào trong mỗi đống) người đi trước có thể thắng, còn ở những vị trí nào thì không, và chỉ ra phương pháp chơi đúng (không thua).

Trên thực tế, rất tiện chơi nim hoặc i-zian-shi-tsy bên bảng lớp — không cần bất kỳ que diêm nào, chỉ với phấn và giẻ lau trong tay. Trên bảng có thể vẽ, chẳng hạn, ba hàng ô kết thúc ở mép phải bảng, và ba quân cờ — mỗi hàng ô một quân (hình 1). Mỗi người chơi, đến lượt mình, lấy một quân cờ và “di chuyển” nó sang phải qua bất kỳ số ô nào (ở đây nói về trò chơi nim); người thực hiện nước đi cuối cùng được coi là thắng. Cũng có thể chơi i-zian-shi-tsy như vậy — chỉ khác là bây giờ bàn chơi có hai hàng

Hình 1.

Hình 2.

7

Đáng tiếc là ở đây cũng không thấy một quy luật xác định nào để lập bảng này.

Không thể viết các bảng I và II theo cách khác được sao?

Chúng ta đã không hiểu được các bảng I và II, trong trường hợp thứ nhất gồm ba, còn trong trường hợp thứ hai gồm hai hàng số, được lập như thế nào. Bây giờ hãy suy nghĩ về những nguyên nhân có thể của thất bại mà chúng ta gặp phải.

Chúng ta đã nói rằng các bảng I và II là những bảng số; chúng được tạo thành từ một dãy số. Các số xuất hiện trong những bảng này, dĩ nhiên, chúng ta đã viết theo cách thông thường, sử dụng hệ thập phân được thừa nhận rộng rãi; chẳng hạn, các số 24 và 39 tạo thành cột cuối cùng của bảng II có nghĩa là: “2 chục và 4 đơn vị” và “3 chục và 9 đơn vị”. Tuy nhiên, bản thân hệ thập phân, mà nguồn gốc của nó gắn với hoàn cảnh ngẫu nhiên là con người có 10 ngón tay, hoàn toàn không liên quan đến các trò chơi đang xét; vì vậy, việc thử viết các bảng của chúng ta theo cách khác có vẻ thích hợp.

Nội dung tiếp theo của bài này liên hệ với bài “Các hệ đếm” (“Kvant” số 6). Chúng ta sẽ cần điều sau đây từ bài đó.

Có thể đề xuất nhiều hệ ghi các số dương bằng một số ít ký hiệu (chữ số). Các hệ đếm theo vị trí (nói chính xác hơn là các hệ ghi số theo vị trí) được xây dựng như sau. Cho trước một cơ số nào đó, hoặc một hệ các số then chốt, là một dãy vô hạn tăng các số nguyên:

$$1 = q_0 < q_1 < q_2 < q_3 \dots$$

Sau đó mỗi số $N$ được biểu diễn dưới dạng tổng các số của cơ số chúng ta, lấy với những hệ số nguyên nào đó:

$$N = a_m q_m + a_{m-1} q_{m-1} + \dots + a_2 q_2 + a_1 q_1 + a_0 q_0;$$

biểu thức này được viết như sau:

$$N = a_m a_{m-1} \dots a_2 a_1 a_0,$$

trong đó $a_m, a_{m-1}, \dots$ là các “chữ số” trong cách viết số $N$.

Ví dụ, nếu hệ các số cơ sở là:

$$1, 2, 3, 5, 7, 11, 13, 17, 19, 23, \dots$$

thì số 27 được viết như sau:

$$27 = 1 \cdot 23 + 0 \cdot 19 + 0 \cdot 17 + 0 \cdot 13 + 0 \cdot 11 + 0 \cdot 7 + 0 \cdot 5 + 1 \cdot 3 + 0 \cdot 2 + 1 \cdot 1 = \text{«1000000101»}.$$

Khi đó, chữ số thứ $k$ $a_k$ trong cách viết của bất kỳ số nào $N$ trong hệ đếm có cơ sở (*) luôn nhỏ hơn tỉ số $q_k + 1/q_k$.

Nếu cơ sở của hệ đếm có dạng:

$$1 = q^0, q = q^1, q^2, q^3, q^4, \dots,$$

trong đó $q$ là một số nguyên nào đó, thì hệ đếm được gọi là “hệ q-chữ số”; trong đó mọi số được biểu diễn bằng tổng các lũy thừa của số $q$ và mọi chữ số trong cách viết số $N$ đều nhỏ hơn $q$ (nhỏ hơn 10 trong trường hợp hệ đếm thập phân thông dụng).

8

Đơn giản nhất trong mọi hệ ghi số nguyên là hệ đếm nhị phân, trong đó mọi số được biểu diễn bằng tổng các lũy thừa của số 2. Nếu dùng hệ đếm này, thì các bảng I và II của chúng ta sẽ có một dạng hoàn toàn khác (các số trong hệ đếm nhị phân sẽ được viết bằng chữ số đỏ):

Bảng Ia

| №№ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| a | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 10 | 0 | 11 | 10 | 1 | 0 | 0 | 1 |
| b | 1 | 10 | 10 | 11 | 100 | 100 | 101 | 100 | 110 | 100 | 101 | 110 | 111 | 1000 | 1000 |
| c | 1 | 10 | 11 | 11 | 100 | 101 | 101 | 110 | 110 | 111 | 111 | 111 | 111 | 1000 | 1001 |

Bảng IIa

| №№ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— |
| a | 1 | 11 | 100 | 110 | 1000 | 1001 | 1011 | 1011 |
| b | 10 | 101 | 111 | 1010 | 1101 | 1111 | 1111 | 1010 |

| №№ | 110 | 1000 | 10001 | 10011 | 10101 | 1101 | 1111 | 10101 | 1010 | 1010 | 1010 | 1010 | 1010 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| 1110 | 10000 | 10001 | 10011 | 10101 | 1101 | 1111 | 1011 | 1011 | 1011 | 1011 | 1011 | 1011 | 1011 |

**Nghiên cứu kỹ bảng Ia cho phép nhận ra trong đó những quy luật hoàn toàn xác định: đúng vậy, các vị trí thua (a, b, c) trong trò chơi “nim” là những vị trí mà tổng các chữ số ở mỗi hàng trong cách viết nhị phân của các số a, b, c là chẵn (nghĩa là bằng 0 hoặc 2)! Tuy nhiên, bảng IIa lại rắc rối hơn: nó chẳng tốt hơn bảng II, và không thể nhận ra từ đó một quy luật xác định nào để lập các cặp thua (a, b).

Nhưng tại sao chính hệ đếm nhị phân lại phải là chìa khóa để chúng ta tìm ra hệ thống chơi không thua trong qiánshízǐ? Đúng là, ta đã thấy rằng hệ này dường như giúp ích trong việc xây dựng lý thuyết trò chơi nim; nhưng qiánshízǐ là một trò chơi hoàn toàn khác, mà chìa khóa mở được một cánh cửa hoàn toàn không nhất thiết phải hợp với cánh cửa khác. Không thể viết lại bảng II theo cách khác hay sao: có lẽ một hệ ghi khác của các số tạo nên hệ này sẽ soi sáng hơn cho cấu trúc của nó?

Nghiên cứu kỹ bảng II cho phép nhận thấy rằng trong đó các số Fibonacci thường xuất hiện, xem chẳng hạn các cột thứ 1, thứ 2, thứ 5 và thứ 13 của bảng *). Điều này, đến lượt nó, có thể gợi cho chúng ta ý nghĩ về sự hợp lý của việc thử viết bảng II trong “hệ đếm Fibonacci”, trong đó mọi số được biểu diễn bằng tổng các số của dãy Fibonacci (các số trong hệ đếm này chúng ta sẽ viết bằng chữ số xanh). Ví dụ, số 100 trong Fibonacci

*) Các số Fibonacci là một dãy số bắt đầu bằng 1 và 2, rồi được xây dựng theo quy luật sau: mỗi số của dãy Fibonacci bằng tổng của hai số đứng trước nó. Các số hạng đầu tiên là: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, … Một cuốn sách nhỏ hay của N. N. Vorobyev, “Các số Fibonacci” (M., “Nauka”, tái bản lần thứ 3, 1969), được dành cho các số Fibonacci.

10

thỏa mãn các điều kiện a) và 6)) đã được nêu ở trên trong trò “nim” là, và chỉ là, các vị trí (a, b, c), trong đó tổng các chữ số tương ứng với cùng một hàng trong cách viết các số a, b, c theo hệ nhị phân là chẵn đối với mọi hàng.

Định lý II. Các vị trí thua trong trò “izyantsy” là, và chỉ là, các vị trí (a, b), trong đó a, khi được viết theo hệ đếm Fibonacci, kết thúc bằng một số chẵn các số không, còn số b nhận được từ số a bằng cách viết thêm một số không ở cuối.

Nhận xét. Từ các định lý I và II suy ra rằng cả hai trò chơi — “nim” và “izyantsy” — theo một nghĩa nào đó đều có lợi cho người bắt đầu: các vị trí thua đối với người bắt đầu (xem bảng I và II) trong chúng khá ít, tức là chúng gặp ít hơn nhiều so với mọi vị trí còn lại (thắng đối với người bắt đầu).

Các chứng minh của những định lý này là nội dung của các bài tập dưới đây. Đáp số cho chúng được cho ở tr. 60 (tuy nhiên, hãy thử tự tìm lời giải). Chúng tôi khuyên trước hết nên hiểu các bài tập 1—4, vì các bài tập 5—7 khó hơn nhiều.

Bài tập

1. Chứng minh rằng nếu vị trí (a, b, c) trong trò “nim” không phải là vị trí thua, tức là không thỏa mãn các điều kiện nêu trong phát biểu định lý I, thì người chơi bằng nước đi của mình có thể biến nó thành vị trí thua.

2. Chứng minh rằng nếu vị trí (a, b, c) trong trò “nim” không phải là vị trí thua, tức là không thỏa mãn các điều kiện nêu trong phát biểu định lý I, thì người chơi bằng nước đi của mình có thể biến nó thành vị trí thua.

3. Hãy chỉ ra cách chơi đúng trong trò “nim” trong trường hợp số đống que diêm là một số bất kỳ cho trước n ≥ 2 (các quy tắc chơi khác giữ nguyên). Cách chơi không thua quy về điều gì trong trường hợp n = 2?

4. Hãy mô tả các vị trí thua (a, b, c) trong trò “nim”, viết các số a, b, c không theo hệ nhị phân mà theo hệ tứ phân (nghĩa là biểu diễn, chẳng hạn, số a dưới dạng a = aₙaₙ₋₁…a₂a₁a₀ = aₙ4ⁿ + aₙ₋₁4ⁿ⁻¹ + … + a₂4² + a₁4 + a₀; ở đây 0 ≤ aᵢ ≤ 3 đối với mọi i = n, n − 1,…, 2, 1, 0 *))

5. Chứng minh rằng với mọi số nguyên dương p, tồn tại một và chỉ một vị trí thua (a, b) trong trò “izyantsy” (tức là vị trí thỏa mãn các điều kiện của định lý II) sao cho b − a = p. Hãy kiểm tra điều này đối với 15 vị trí thua đầu tiên được liệt kê trong bảng II.

6. Chứng minh rằng nếu vị trí (b, a) trong trò “izyantsy” không thỏa mãn các điều kiện của định lý II, thì người chơi bằng nước đi của mình có thể hoặc thắng ngay, hoặc đưa vị trí về vị trí thua.

7. Chứng minh rằng nếu vị trí (a, b) trong trò “izyantsy” là vị trí thua, thì sau bất kỳ nước đi nào của người chơi, nó không còn như vậy nữa.

8. Hãy chỉ ra cách chơi đúng trong trò “izyantsy” nếu số đống là lẻ (mỗi nước đi người chơi có quyền lấy một số bất kỳ que diêm từ một đống nào đó, hoặc lấy bằng nhau — cũng với số bất kỳ! — từ tất cả các đống).

Bài toán. Hãy chỉ ra cách chơi đúng trong trò “izyantsy” nếu số đống bằng bốn.

Tôi muốn cảnh báo độc giả rằng tác giả không biết lời giải của bài toán đã nêu.

*) Gạch trên số cho biết rằng đó là cách viết số bằng các chữ số aₙaₙ₋₁…a₂a₁a₀, chứ không phải tích của các số.