Câu đố 15 ô số là khung vuông 4 × 4 chứa 15 miếng số từ 1 đến 15 và một ô trống; người giải trượt các miếng vào ô trống để xếp lại theo thứ tự. Nó được làm ra ở Mỹ khoảng năm 1874 và gây ra một cơn sốt khắp Mỹ và châu Âu năm 1880. Câu đố nổi tiếng nhất của thời đó — đổi chỗ hai miếng 14 và 15 — hoá ra không thể giải được, và điều này được chứng minh bằng toán học năm 1879. Câu đố tưởng là đồ chơi ấy trở thành một ví dụ kinh điển về tính chẵn lẻ của hoán vị và về tìm đường ngắn nhất trong máy tính.
Ai làm ra câu đố 15
Trong nhiều năm, người ta tin rằng Sam Loyd, nhà sáng tác câu đố nổi tiếng người Mỹ, là tác giả — chính ông cũng tự nhận như vậy về sau. Nhưng các nhà sử học câu đố Jerry Slocum và Dic Sonneveld, trong cuốn The 15 Puzzle (2006), đã chỉ ra rằng người làm ra câu đố là Noyes Palmer Chapman, một nhân viên bưu điện ở Canandaigua, bang New York, khoảng năm 1874. Chapman làm các khối gỗ có số cho bạn bè; câu đố lan dần tới các trường học, rồi tới Boston, nơi các nhà làm đồ thủ công bắt đầu sản xuất hàng loạt.
Cơn sốt năm 1880
Đầu năm 1880, câu đố 15 bùng nổ. Báo chí Mỹ và châu Âu viết về những người mê mẩn tới mức bỏ việc, những chủ cửa hàng treo biển cấm nhân viên mang câu đố tới chỗ làm, những cuộc thi giải câu đố. Ở Đức, Pháp, Anh, câu đố cũng gây sốt. Có báo so sánh nó với một "dịch bệnh".
Phiên bản gây chú ý nhất là khi các miếng được xếp theo thứ tự, trừ hai miếng 14 và 15 bị đổi chỗ cho nhau. Người ta treo giải thưởng cho ai đưa được về đúng thứ tự. Sam Loyd về sau kể rằng ông đã treo giải 1.000 đô la cho thử thách này — một câu chuyện mà các nhà sử học nghi ngờ có thật hay không, vì Loyd nổi tiếng hay tô vẽ. Dù sao thì không ai lĩnh được giải, vì một lý do đơn giản: câu đố ấy không có lời giải.
Vì sao không thể đổi chỗ 14 và 15
Năm 1879, hai nhà toán học Mỹ William Woolsey Johnson và William Edward Story công bố trên tạp chí American Journal of Mathematics một chứng minh: với câu đố 15, đúng một nửa số cách xếp ban đầu có thể đưa về thứ tự, nửa còn lại thì không bao giờ.
Ý tưởng chẵn lẻ, giải thích dễ hiểu
- Đọc các miếng số theo thứ tự từng hàng từ trái sang phải, từ trên xuống dưới (bỏ qua ô trống), ta được một dãy 15 số.
- Đếm số "cặp ngược": cặp hai số mà số lớn đứng trước số nhỏ. Ví dụ trong dãy đã xếp đúng, có 0 cặp ngược. Khi chỉ đổi chỗ 14 và 15, có đúng 1 cặp ngược.
- Xét mỗi nước trượt:
- Trượt ngang (sang trái, phải): thứ tự đọc của các miếng không đổi, số cặp ngược không đổi.
- Trượt dọc (lên, xuống): một miếng nhảy qua đúng 3 miếng khác trong thứ tự đọc. Số cặp ngược thay đổi một số lẻ (1 hoặc 3), tức tính chẵn lẻ của số cặp ngược đổi.
- Đồng thời, mỗi lần trượt dọc, ô trống đổi hàng. Vậy "tính chẵn lẻ của số cặp ngược" cộng với "số hàng của ô trống" là một đại lượng không bao giờ đổi qua mọi nước đi.
- Trạng thái đích (xếp đúng, ô trống ở góc dưới phải) và trạng thái "đổi 14 với 15" (ô trống cũng ở góc dưới phải) có tính chẵn lẻ khác nhau. Không có chuỗi nước đi nào nối chúng.
Đây là ví dụ đẹp của một bất biến: một đại lượng không đổi dù làm gì, dùng để chứng minh một điều là không thể. Kỹ thuật này dùng rất nhiều trong toán học thi đấu và trong khoa học máy tính.
Câu đố 15 và đường ngắn nhất
Với những cách xếp giải được, cần bao nhiêu nước đi? Số trạng thái có thể có của câu đố 15 là 16!/2 ≈ 10,5 nghìn tỷ (16 giai thừa chia đôi vì chỉ một nửa là đến được). Quá nhiều để duyệt bằng tay, nhưng với máy tính hiện đại thì khả thi.
- Năm 1999 và 2000, các nhà nghiên cứu dùng máy tính duyệt toàn bộ không gian trạng thái và xác nhận: mọi cách xếp giải được đều có thể đưa về thứ tự trong tối đa 80 nước (tính mỗi lần trượt một miếng là một nước).
- Chỉ một số rất ít cách xếp cần đúng 80 nước.
- Phiên bản nhỏ hơn, câu đố 8 ô (3 × 3), có 181.440 trạng thái giải được, tối đa 31 nước.
Câu đố 15 trở thành "bài tập chuẩn" trong ngành trí tuệ nhân tạo để thử nghiệm các thuật toán tìm kiếm như A* (bài tìm đường ngắn nhất), vì nó đủ lớn để khó mà vẫn đủ đơn giản để hiểu.
Bảng so sánh các phiên bản
| Phiên bản | Khung | Số trạng thái giải được | Số nước tối đa của lời giải tối ưu |
|---|---|---|---|
| Câu đố 8 | 3 × 3 | 181.440 | 31 |
| Câu đố 15 | 4 × 4 | khoảng 10,5 nghìn tỷ | 80 |
| Câu đố 24 | 5 × 5 | khoảng 7,8 × 10²⁴ | Chưa biết chính xác |
Mẹo giải bằng tay
- Giải từng hàng từ trên xuống: xếp xong hàng 1 (1, 2, 3, 4), rồi hàng 2 (5, 6, 7, 8), rồi không đụng tới chúng nữa.
- Hai miếng cuối hàng khó nhất: đưa miếng 3 vào vị trí của 4 trước, rồi đưa 4 xuống ngay dưới, sau đó xoay cả cặp vào đúng chỗ.
- Hai hàng cuối: giải theo cột từ trái sang phải (9 và 13, rồi 10 và 14), cuối cùng là khối 2 × 2 còn lại.
- Nếu cuối cùng còn 14 và 15 bị đổi chỗ: kiểm tra lại, có thể ai đó đã tháo miếng ra lắp lại — câu đố đã thành không giải được.
Người giải nhanh có thể giải một câu đố 15 ngẫu nhiên trong vài giây, dù không đi theo đường ngắn nhất.
Góc nhìn hôm nay: một bài học về cái "không thể"
Câu chuyện câu đố 15 dạy một điều quan trọng: đôi khi câu trả lời đúng là "không có lời giải", và chứng minh điều đó cũng là một lời giải. Sau khi thử, hãy cùng trẻ làm câu đố 15 bằng giấy: cắt 15 ô vuông giấy đánh số, đặt trong một khung 4 × 4 vẽ trên giấy. Thử đổi chỗ hai ô bất kỳ rồi giải, đếm số cặp ngược trước khi giải để đoán trước có giải được không.
Câu hỏi thường gặp
Câu đố 15 ô số là gì?
Là khung 4 × 4 chứa 15 miếng số từ 1 đến 15 và một ô trống. Người giải trượt các miếng kề ô trống vào ô trống để xếp lại theo thứ tự. Câu đố ra đời ở Mỹ khoảng năm 1874 và gây sốt năm 1880.
Ai phát minh câu đố 15?
Theo nghiên cứu của các nhà sử học câu đố Jerry Slocum và Dic Sonneveld, người làm ra câu đố là Noyes Palmer Chapman, nhân viên bưu điện ở bang New York, khoảng năm 1874. Sam Loyd từng tự nhận là tác giả nhưng điều đó không đúng.
Vì sao không thể đổi chỗ 14 và 15?
Vì mọi nước đi đều giữ nguyên một đại lượng bất biến gồm tính chẵn lẻ của số cặp ngược và hàng của ô trống. Trạng thái đổi 14 với 15 có tính chẵn lẻ khác trạng thái đích, nên không chuỗi nước đi nào nối được. Johnson và Story chứng minh năm 1879.
Giải câu đố 15 cần tối đa bao nhiêu nước?
Nhờ máy tính duyệt toàn bộ không gian trạng thái, người ta xác nhận mọi cách xếp giải được đều đưa về thứ tự trong tối đa 80 nước, tính mỗi lần trượt một miếng là một nước.
Làm sao biết một cách xếp câu đố 15 có giải được không?
Đếm số cặp ngược khi đọc các miếng theo hàng, rồi xét hàng của ô trống. Nếu tính chẵn lẻ của tổng hợp hai đại lượng này giống với trạng thái đích thì giải được, khác thì không giải được.