[Câu đố "Meleda" và "Hoa quỷ"]

Bài toán trong câu đố “bông hoa chết tiệt” - tháo vòng dây ra khỏi “bông hoa”. Nếu sợi dây làm ra “bông hoa” đủ mềm, chúng ta chỉ cần rút “thân” cao nhất ra khỏi các bánh xe bao quanh nó (sơ đồ bên dưới), sau đó theo cách tương tự, giải mã tuần tự các “thân” còn lại, và sau đó không có gì cản trở việc bình tĩnh tháo sợi dây. Nhưng “lời giải” như vậy bị cấm bởi các đặc quyền của trò chơi. Sẽ dễ hiểu hơn về cách vòng lặp thực sự được in dấu nếu bạn hiểu phiên bản cổ điển nổi tiếng hơn, người ta có thể nói, của câu đố này - meled (hình A). Ở đây, thay vì một sợi dây, có một vòng dây cứng, và cùng với “bông hoa” có một chuỗi bánh xe di chuyển trên các thanh có thể di chuyển theo chiều dọc.

Mặt trong của vòng giống như trên hình A. Lưu ý rằng chỉ có thể tháo cực thứ $k$ khỏi tàu con thoi khi cực thứ $(k-1)$ cũng đã được luồn vào đó và có thể tháo các cực có số thấp hơn (hình B). Chúng ta sẽ xem xét thao tác luồn một vòng vào con thoi hoặc tháo các bánh xe ra khỏi con thoi chỉ trong một lần di chuyển. Đặt $L_k$ và $M_k$ là số lần di chuyển nhỏ nhất cần thiết để một con thoi có vòng $k$ được móc vào một cực (hình B) và theo đó, vào tất cả các cực (hình A).

1. Chứng minh rằng $L_k=2L_{k-1}+1$, $M_k=M_{k-2}+L_{k-1}+1$.
2. Thể hiện $L_k$ và $M_k$ dưới dạng $k$, viết chuỗi nước đi tương ứng.
3. Làm thế nào để gỡ sợi dây ra khỏi “bông hoa chết tiệt”?

Nhận xét trên sẽ giúp bạn giải các câu bài toán, còn đáp số và gợi ý được đặt ở trang. 79.

V. D.