Cửu liên hoàn là câu đố gồm chín vòng kim loại xâu trên một khung dài; mục tiêu là tháo hết chín vòng ra khỏi khung, theo hai luật: vòng đầu tiên luôn tháo hoặc lắp được, còn vòng bất kỳ khác chỉ tháo hoặc lắp được khi vòng ngay trước nó đang ở trên khung và mọi vòng trước đó đã ở ngoài. Với chín vòng, lời giải ngắn nhất theo cách đếm phổ biến cần 341 bước.
Câu đố này có lịch sử lâu đời ở Trung Hoa và đã được mô tả trong sách vở châu Âu từ khoảng thế kỷ 16. Điều làm nó hấp dẫn với người thích toán là lời giải mang đúng cấu trúc đệ quy và gắn với một cách đếm nhị phân đặc biệt. Bài giải thích luật, dạy cách giải từ ba vòng lên chín vòng, và mở rộng sang họ câu đố gỡ dây, gỡ móc kim loại.
Cấu tạo và hai luật duy nhất
Câu đố gồm ba phần: một thanh đế có chín cọc nhỏ, mỗi cọc nối với một vòng; một khung dài hình thoi hoặc hình chữ U kéo dài, gọi là khung hay kiếm; và chín vòng xâu quanh khung. Mỗi cọc đi xuyên qua vòng của cọc kế tiếp, nên các vòng ràng buộc lẫn nhau. Vòng gần đầu mở của khung nhất gọi là vòng thứ nhất.
Từ cấu tạo đó sinh ra hai luật. Luật một: vòng thứ nhất có thể tháo ra hoặc lắp vào bất kỳ lúc nào, vì không có vòng nào chặn nó. Luật hai: vòng thứ k, với k lớn hơn một, chỉ tháo hoặc lắp được khi vòng thứ k trừ một đang ở trên khung và tất cả các vòng nhỏ hơn k trừ một đều đã ở ngoài khung. Ngoài hai luật này không có cách nào khác; mọi thao tác ép khác đều làm cong vòng.
Luật hai nghe trừu tượng, nhưng cầm câu đố lên bạn sẽ thấy ngay: để thả vòng thứ tư qua đầu khung, vòng thứ ba phải đang nằm trên khung để giữ cọc ở đúng chỗ, còn vòng thứ nhất và thứ hai phải ở ngoài để không chặn đường.
Giải ba vòng từng bước
Cách tốt nhất để hiểu là giải bản nhỏ. Bảng dưới ghi trạng thái ba vòng theo thứ tự vòng ba, vòng hai, vòng một; số 1 là vòng ở trên khung, số 0 là đã tháo ra.
| Bước | Thao tác | Trạng thái sau bước | Vì sao được phép |
|---|---|---|---|
| Bắt đầu | Không | 1 1 1 | Cả ba vòng ở trên khung |
| 1 | Tháo vòng một | 1 1 0 | Vòng một luôn tháo được |
| 2 | Tháo vòng ba | 0 1 0 | Vòng hai đang trên khung, vòng một đã ra |
| 3 | Lắp vòng một | 0 1 1 | Vòng một luôn lắp được |
| 4 | Tháo vòng hai | 0 0 1 | Vòng một đang trên khung, không còn vòng nào nhỏ hơn |
| 5 | Tháo vòng một | 0 0 0 | Hoàn thành |
Bạn để ý bước 3: phải lắp lại vòng một mà mình vừa tháo. Đây là điểm làm người mới bối rối nhất: lời giải liên tục lắp vào rồi tháo ra, nên cảm giác như đi lùi. Thật ra không có cách nào ngắn hơn.
Lời giải đệ quy: tháo n vòng nghĩa là gì
Muốn tháo vòng lớn nhất, phải dọn đường trước. Để tháo vòng n, vòng n trừ một phải ở trên khung còn mọi vòng nhỏ hơn phải ra ngoài. Vậy bước đầu là tháo n trừ hai vòng đầu, giữ nguyên vòng n trừ một.
Tháo vòng lớn nhất. Lúc này luật hai cho phép, vòng n rời khung và không cần đụng tới nữa.
Lắp lại để tháo tiếp. Còn lại n trừ một vòng nhưng vòng n trừ một vẫn trên khung, trong khi các vòng nhỏ hơn đã ra ngoài. Muốn tháo nó, bạn phải lắp lại n trừ hai vòng đầu, rồi coi như bài toán tháo n trừ một vòng.
Mỗi tầng gọi lại chính nó. Bài toán n vòng quy về bài toán n trừ hai vòng và n trừ một vòng. Đó là đệ quy, giống bài tháp Hà Nội quen thuộc trong sách tin học. Số bước tăng gần gấp đôi mỗi khi thêm một vòng.
Số bước theo số vòng
Áp công thức đệ quy, số bước ngắn nhất (tính mỗi lần tháo hoặc lắp một vòng là một bước) cho vài trường hợp như sau:
- Một vòng: 1 bước.
- Hai vòng: 2 bước.
- Ba vòng: 5 bước, như bảng ở trên.
- Bốn vòng: 10 bước.
- Năm vòng: 21 bước.
- Bảy vòng: 85 bước.
- Chín vòng: 341 bước.
Nhiều người thao tác thạo cho phép đưa vòng một và vòng hai lên xuống cùng lúc khi điều kiện cho phép, tính là một bước; khi đó số bước cho chín vòng giảm đáng kể. Vì vậy các tài liệu ghi con số khác nhau, tùy cách đếm.
Dãy trạng thái đi qua trong lời giải có tính chất đặc biệt: hai trạng thái liền nhau chỉ khác nhau đúng một vòng. Đọc dãy đó như những số nhị phân, ta được một cách đếm gọi là mã Gray, trong đó mỗi lần đếm chỉ đổi một chữ số. Mã Gray được dùng thật trong kỹ thuật, chẳng hạn ở các bộ mã hoá góc quay, để tránh lỗi khi nhiều chữ số đổi cùng lúc.
Mẹo thao tác tay cho đỡ rối
Lý thuyết là một chuyện, cầm chín vòng kim loại lên lại là chuyện khác. Mẹo đầu tiên là cầm khung nằm ngang, đầu mở hướng ra ngoài, tay trái giữ thanh đế. Khi tháo một vòng, kéo vòng lên khỏi khung rồi thả xuống lọt qua khe giữa hai thanh khung; khi lắp, làm ngược lại: luồn vòng lên từ dưới khe qua đầu khung.
Mẹo thứ hai là luôn nói ra trạng thái, hoặc ghi giấy, theo dạng dãy số một và không như trong bảng. Chín vòng đủ dài để bạn mất dấu giữa chừng; khi đó cách cứu duy nhất là nhìn từ vòng lớn nhất xuống, xác định vòng lớn nhất còn trên khung, và tính lại từ đó.
Mẹo thứ ba là luyện riêng các đoạn ngắn. Tháo hai vòng đầu và lắp lại hai vòng đầu là thao tác lặp lại nhiều nhất trong cả lời giải; làm thạo đoạn này là giảm phần lớn thời gian. Nhiều người mất cả buổi ở lần đầu, nhưng sau vài lần thì tháo chín vòng trong vài phút.
Câu đố gỡ dây, gỡ móc: cùng một họ
Cửu liên hoàn thuộc một họ lớn hơn: câu đố gỡ, trong đó một vật bị vướng vào vật khác và bạn phải tách chúng ra mà không cắt, không bẻ. Dạng phổ biến ở Việt Nam là hai móc sắt uốn cong móc vào nhau, hoặc một sợi dây có hạt bị luồn qua thanh gỗ có lỗ. Nhìn qua tưởng không tách được, nhưng nhà làm luôn bảo đảm có đường đi.
Nguyên lý chung của họ này đến từ tô pô, ngành toán học về hình dạng khi được kéo giãn: nếu hai vật thật sự móc vào nhau như hai mắt xích hàn kín thì không tách được; còn nếu có khe hở hoặc vòng dây có thể kéo giãn, thì luôn có một con đường. Cách giải là tìm chỗ hở, theo dấu đường đi của vật từ chỗ hở đó, và nhiều khi phải kéo vật đi xa hơn trước khi tách được.
Với câu đố móc sắt, nguyên tắc vàng là không dùng sức. Vật đã được thiết kế để lọt qua đúng góc nghiêng nào đó; nếu cần bẻ, bạn đang đi sai đường. Với câu đố dây, hãy nới dây thật lỏng trước khi bắt đầu, vì dây căng che mất đường đi.
Câu đố có từ bao giờ
Nguồn gốc chính xác của cửu liên hoàn không rõ. Nhiều tài liệu cho rằng câu đố đã lưu hành ở Trung Hoa từ rất lâu, với các truyền thuyết gắn nó với những nhân vật nổi tiếng về mưu trí; những chuyện này nên được hiểu là truyền thuyết, không phải sử liệu. Điều có thể kiểm chứng hơn là sách toán ở châu Âu đã mô tả câu đố từ khoảng thế kỷ 16, và đến thế kỷ 19 đã có phân tích toán học về số bước giải.
Ở nhiều vùng, câu đố từng được dùng như món đồ thử độ kiên nhẫn, làm bằng sắt hay đồng do thợ rèn tự uốn. Ở Việt Nam, cửu liên hoàn được bán ở các cửa hàng đồ thủ công và đồ dùng giáo dục, thường đi cùng các câu đố kim loại khác như móc sắt, vòng lồng. Bạn có thể gặp bản bằng gỗ với các vòng là dây kim loại, nguyên lý vẫn như nhau.
Phần toán học quanh câu đố, đặc biệt mối liên hệ với mã Gray và đệ quy, ngày nay được dùng trong một số giáo trình tin học như ví dụ trực quan. Đó là điểm chung thú vị với tháp Hà Nội: một câu đố cầm tay minh hoạ được một ý tưởng thuật toán.
Dùng cửu liên hoàn trong lớp học và nấc tiến bộ
Với giáo viên toán hoặc tin học, cửu liên hoàn là đồ dùng trực quan rất tốt cho ý đệ quy và đếm nhị phân. Một số gợi ý, kèm cột mốc tự đặt cho người tự luyện:
- Cho học sinh giải bản ba vòng bằng tay, ghi trạng thái theo dãy một và không, rồi tự đếm số bước.
- Đặt câu hỏi: nếu thêm một vòng thì số bước tăng thế nào; để học sinh tự đoán quy luật trước khi đưa công thức.
- Với lớp tin học, viết thủ tục đệ quy in ra dãy thao tác cho n vòng và đối chiếu với bảng ở trên.
- Cột mốc cho người tự luyện: tháo xong ba vòng; tháo xong năm vòng không ghi giấy; tháo và lắp lại đủ chín vòng; giải lại được sau một tháng không đụng tới.
- Không chấm điểm hay so thời gian giữa học sinh; mỗi em ghi cột mốc của mình vào sổ riêng.
Một hoạt động hay cho nhóm: chia lời giải chín vòng thành nhiều đoạn, mỗi bạn đảm nhận một đoạn và chuyền câu đố cho bạn kế tiếp. Cả nhóm phải thống nhất trạng thái lúc bàn giao, giống như ghi chép trong một quy trình kỹ thuật.
Câu hỏi thường gặp
Cửu liên hoàn có bao nhiêu bước?
Theo cách đếm mỗi lần tháo hoặc lắp một vòng là một bước, chín vòng cần 341 bước. Nếu cho phép đưa hai vòng đầu lên xuống cùng lúc và tính là một bước, số bước ít hơn đáng kể. Vì vậy các nguồn ghi số khác nhau.
Vì sao phải lắp lại vòng vừa tháo?
Vì luật chỉ cho tháo vòng lớn khi vòng ngay trước nó còn trên khung. Để tháo vòng ngay trước đó, bạn lại cần các vòng nhỏ hơn ở đúng trạng thái, nên phải lắp lại. Đây là bản chất đệ quy của câu đố, không phải do bạn làm sai.
Có cửu liên hoàn ít vòng hơn không?
Có. Nhiều bộ có năm, bảy vòng, thậm chí ba, bốn vòng để luyện. Người mới nên bắt đầu bằng ba vòng, ghi trạng thái theo dãy một và không, rồi mới sang bản đầy đủ.
Đang giải giữa chừng bị rối thì làm sao?
Nhìn từ vòng lớn nhất xuống, tìm vòng lớn nhất còn trên khung. Nhiệm vụ trước mắt là tháo vòng đó, nên bạn cần vòng ngay trước nó trên khung và các vòng nhỏ hơn ra ngoài. Tính lại từ đó, không cần làm lại từ đầu.
Cửu liên hoàn có hợp với trẻ em không?
Trẻ lớn tiểu học trở lên có thể làm bản ba đến năm vòng cùng người lớn. Câu đố là cách vui để trẻ gặp ý đệ quy. Nên chọn loại vòng nhẵn, không cạnh sắc, và ghi nhận việc trẻ tự tháo được, không bấm giờ.
Câu đố hai móc sắt có mẹo chung không?
Mẹo chung là tìm chỗ hở trên mỗi móc, xoay hai móc sao cho chỗ hở của móc này đi theo đường cong của móc kia, và không dùng sức. Nếu thấy phải bẻ, hãy đổi hướng xoay hoặc thử lật một móc.