Câu đố logic kinh điển: qua sông, cân đĩa, qua cầu và Tháp Hà Nội

Bốn câu đố logic kinh điển hay xuất hiện trong sách, lớp học và cả phòng thoát hiểm là: chở sói, dê và bắp cải qua sông; tìm đồng xu giả bằng cân đĩa; đưa bốn người qua cầu với một ngọn đèn; và Tháp Hà Nội. Câu đố qua sông có từ thế kỷ 8–9 trong sách của Alcuin xứ York; Tháp Hà Nội do nhà toán học Pháp Édouard Lucas giới thiệu năm 1883. Điểm chung của chúng: không cần kiến thức đặc biệt, chỉ cần suy luận chặt chẽ.

1. Chở sói, dê và bắp cải qua sông

Đề bài

Một người nông dân cần đưa một con sói, một con dê và một cây bắp cải qua sông. Thuyền nhỏ, mỗi lần chỉ chở được người và một thứ. Nếu để sói và dê lại một mình, sói sẽ ăn dê; để dê và bắp cải lại một mình, dê sẽ ăn bắp cải. Làm sao đưa cả ba qua sông an toàn?

Lời giải (7 lượt)

1. Chở dê sang bờ bên kia.
2. Quay về một mình.
3. Chở sói sang.
4. Chở dê quay về (đây là bước then chốt).
5. Chở bắp cải sang, để cạnh sói.
6. Quay về một mình.
7. Chở dê sang.

Bước thứ tư làm nhiều người bất ngờ: phải mang một thứ quay lại bờ cũ. Bài học của câu đố là đôi khi phải lùi một bước để tiến hai bước. Câu đố này xuất hiện trong tập "Propositiones ad acuendos juvenes" (Bài toán rèn trí tuệ cho người trẻ) gắn với tên Alcuin xứ York, học giả trong triều đình Charlemagne cuối thế kỷ 8 – đầu thế kỷ 9. Nhiều nền văn hoá ở châu Phi, châu Á có những biến thể tương tự.

2. Tìm đồng xu giả bằng cân đĩa

Bản dễ: 9 đồng, 2 lần cân

Có 9 đồng xu giống hệt nhau, trong đó có một đồng giả nặng hơn. Dùng một cân đĩa (chỉ so sánh hai bên, không có số đo), cân hai lần để tìm đồng giả.

1. Chia 9 đồng thành ba nhóm 3. Đặt hai nhóm lên hai đĩa.
2. Nếu một bên nặng hơn, đồng giả ở nhóm ấy; nếu cân bằng, đồng giả ở nhóm còn lại.
3. Lấy nhóm 3 đồng nghi ngờ, đặt mỗi đĩa một đồng. Bên nặng là đồng giả; nếu cân bằng, đồng giả là đồng còn lại.

Ý tưởng then chốt: mỗi lần cân cho ba kết quả (trái nặng, phải nặng, cân bằng), nên chia thành ba nhóm chứ không phải hai.

Bản khó: 12 đồng, 3 lần cân, không biết giả nặng hay nhẹ

Có 12 đồng, một đồng giả có thể nặng hơn hoặc nhẹ hơn. Cân ba lần để tìm ra đồng giả và biết nó nặng hay nhẹ. Bài này giải được, bằng cách chia thành ba nhóm 4 và khéo léo đổi chỗ đồng xu giữa các lần cân để mỗi lần cân thu được tối đa thông tin. Ba lần cân cho tối đa 27 kết quả, đủ để phân biệt 24 khả năng (12 đồng × nặng hoặc nhẹ). Đây là bài đáng thử tự giải trước khi tra lời giải.

3. Bốn người qua cầu với một ngọn đèn

Đề bài

Bốn người cần qua một cây cầu hẹp trong đêm. Cầu chỉ chịu được hai người một lúc, và phải có đèn mới đi được. Chỉ có một chiếc đèn. Bốn người đi qua cầu mất lần lượt 1, 2, 5 và 10 phút; hai người đi cùng thì đi theo tốc độ người chậm hơn. Ít nhất bao nhiêu phút để cả bốn qua cầu?

Lời giải: 17 phút

Cách nghĩ thông thường là để người nhanh nhất đưa đèn qua lại cho từng người, ra 19 phút. Mẹo nằm ở lượt 3: cho hai người chậm nhất đi cùng nhau, để "thời gian chậm" chỉ bị tính một lần.

4. Tháp Hà Nội

Đề bài

Có ba cọc và một chồng đĩa kích thước giảm dần xếp trên cọc thứ nhất, đĩa lớn nhất ở dưới. Cần chuyển cả chồng sang cọc thứ ba, theo luật: mỗi lần chỉ chuyển một đĩa trên cùng, và không bao giờ đặt đĩa lớn lên trên đĩa nhỏ.

Nguồn gốc

Câu đố được nhà toán học Pháp Édouard Lucas giới thiệu năm 1883, dưới bút danh "N. Claus de Siam" (đảo chữ của "Lucas d'Amiens"), kèm một truyền thuyết tự đặt về những vị tăng ở một đền thờ chuyển 64 chiếc đĩa vàng, và khi chuyển xong thì thế giới kết thúc. Tên "Tháp Hà Nội" là do Lucas đặt, có lẽ vì cảm hứng phương Đông thời ấy; không có bằng chứng nào cho thấy câu đố xuất phát từ Hà Nội.

Lời giải và con số

Lời giải dùng tư duy đệ quy: để chuyển n đĩa từ cọc A sang cọc C, hãy chuyển n−1 đĩa trên cùng sang cọc B, chuyển đĩa lớn nhất sang C, rồi chuyển n−1 đĩa từ B sang C. Số lần chuyển ít nhất là 2 mũ n trừ 1 (2^n − 1).

• 3 đĩa: 7 lần chuyển.
• 5 đĩa: 31 lần.
• 10 đĩa: 1.023 lần.
• 64 đĩa: khoảng 1,8 × 10^19 lần. Nếu mỗi giây chuyển một đĩa, sẽ mất khoảng 585 tỉ năm, lâu hơn nhiều so với tuổi vũ trụ hiện nay theo ước tính khoa học (khoảng 13,8 tỉ năm).

Tháp Hà Nội là bài tập kinh điển trong các khoá học lập trình để dạy đệ quy.

Vì sao những câu đố này sống lâu

• Đề ngắn, ai cũng hiểu: không cần công thức.
• Có "bẫy" trực giác: cách nghĩ đầu tiên thường sai (không mang dê về, không cho hai người chậm đi cùng).
• Lời giải đẹp: khi thấy rồi, nó hiển nhiên.
• Dạy một ý tưởng lớn: lùi để tiến, chia ba thay vì chia hai, gộp chi phí, đệ quy.

Góc nhìn hôm nay

Những câu đố này là "cánh cửa" vào tư duy toán học cho rất nhiều thế hệ. Cách hay nhất để dùng chúng với trẻ em là không đưa lời giải ngay: cho trẻ dùng đồ vật thật (ba đồng xu, mấy mảnh giấy làm sói, dê, bắp cải, ba cái cốc làm cọc tháp), để trẻ tự thử, tự sai, tự sửa. Khoảnh khắc trẻ tự tìm ra bước "mang dê về" đáng giá hơn mọi lời giải in sẵn.