Dãy số 1, 2, 4, 8, 16 và cú lừa ở số thứ sáu

Trò chơi bắt đầu rất đơn giản. Đánh dấu vài điểm trên một đường tròn, nối mọi cặp điểm bằng một đoạn thẳng, rồi đếm xem hình tròn bị chia thành bao nhiêu miền.
Một điểm thì chưa có gì để nối, hình tròn vẫn là 1 miền. Hai điểm cho 2 miền. Ba điểm cho 4 miền. Bốn điểm cho 8 miền. Năm điểm cho 16 miền.
Dãy số 1, 2, 4, 8, 16 gần như tự đọc đáp án của nó lên thành tiếng: gấp đôi, gấp đôi nữa, số thứ sáu phải là 32. Hầu hết mọi người gặp bài toán này lần đầu đều trả lời như vậy, rất nhanh và rất chắc chắn. Đáp án đúng là 31.
Bài toán này được gọi là bài toán Moser, theo tên nhà toán học Leo Moser. Nó nổi tiếng không phải vì khó, mà vì cái cách nó lừa được gần như tất cả mọi người ở ngay bước thứ sáu. Bài viết này đi qua ba việc: đếm lại thật ở trường hợp 6 điểm, tìm công thức đúng bằng tổ hợp, và giải thích vì sao 5 số đầu tiên lại trùng khớp với lũy thừa của 2 hoàn hảo đến thế.
Đếm lại trường hợp 6 điểm cho chắc
Trước hết cần nói rõ đề bài hỏi số miền tối đa. Muốn đạt tối đa, các điểm phải nằm ở vị trí đủ tổng quát, nghĩa là không có 3 đường chéo nào cùng đi qua một điểm ở trong hình tròn. Nếu 3 đường chéo đồng quy, chúng chia sẻ một giao điểm thay vì tạo ra các giao điểm riêng, và số miền giảm đi.
Với 6 điểm ở vị trí tổng quát, đếm cẩn thận trên hình cho ra 31 miền. Con số này rất khó đếm đúng bằng mắt thường: hình có 15 đoạn nối và 15 giao điểm ở trong, các miền nhỏ gần tâm dễ bị bỏ qua hoặc đếm trùng. Nhiều người đếm đi đếm lại vẫn ra 30 hoặc 32.
Một đối chứng đáng nhớ là trường hợp 6 điểm tạo thành lục giác đều. Hình lúc này đẹp và cân đối, nhưng ba đường chéo chính cùng đi qua tâm, và số miền chỉ còn 30. Cùng một đề bài, chỉ đổi vị trí các điểm là đáp án đã khác. Toán Khó đã kiểm chứng cả hai con số 31 và 30 bằng cách dựng đồ thị phẳng của hình và áp dụng công thức Euler, thay vì tin vào việc đếm bằng mắt.
Công thức đúng đếm bằng tổ hợp
Thay vì đếm từng miền, hãy đếm cấu trúc tạo ra chúng. Vẽ các đoạn nối lần lượt từng cái một. Khi một đoạn nối mới được vẽ, các giao điểm nằm trên nó chia nó thành nhiều đoạn con, và mỗi đoạn con cắt một miền đang có thành hai miền. Vậy số miền tăng thêm đúng bằng số đoạn con của dây vừa vẽ.
Cộng dồn qua tất cả các dây, mỗi dây đóng góp phần cơ số của nó, và mỗi giao điểm trong đóng góp thêm đúng một miền nữa (giao điểm chỉ được tính một lần, vào lúc dây thứ hai trong hai dây cắt nhau được vẽ). Kết quả là:
$$R(n) = 1 + \text{(số dây)} + \text{(số giao điểm trong)}$$
Số dây thì dễ: mỗi cặp điểm cho một dây, nên có $\binom{n}{2}$ dây. Số giao điểm trong tinh tế hơn một chút: cứ chọn 4 điểm bất kỳ trên đường tròn, tứ giác tạo bởi chúng có hai đường chéo cắt nhau tại đúng một điểm ở trong, và mọi giao điểm trong đều xuất phát từ một bộ 4 điểm như vậy. Vậy số giao điểm là $\binom{n}{4}$, và công thức cuối cùng là:
$$R(n) = 1 + \binom{n}{2} + \binom{n}{4}$$
Thay số vào: với $n = 6$, ta được $1 + 15 + 15 = 31$. Với $n = 7$ là 57, $n = 8$ là 99, $n = 9$ là 163, $n = 10$ là 256. Con số 256 ở $n = 10$ nhìn cũng rất giống lũy thừa của 2, nhưng nó là $2^8$, trong khi quy luật gấp đôi dự đoán $2^9 = 512$ – lệch hẳn một nửa.
Dãy số là chương mở đầu của nhiều cuốn sách bồi dưỡng học sinh giỏi, và ai muốn đi sâu theo hướng này có thể tham khảo cuốn Bồi dưỡng học sinh giỏi chuyên khảo dãy số của Nguyễn Tài Chung trên trang sách của Toán Khó.

Vì sao năm số đầu lại là lũy thừa của 2
Phần hay nhất của bài toán nằm ở đây. Công thức tổ hợp ở trên có thể viết lại dưới một dạng khác:
$$R(n) = \binom{n-1}{0} + \binom{n-1}{1} + \binom{n-1}{2} + \binom{n-1}{3} + \binom{n-1}{4}$$
Tức là $R(n)$ bằng tổng của 5 phần tử đầu tiên trong hàng thứ $n – 1$ của tam giác Pascal. Mà tổng của toàn bộ hàng thứ $m$ trong tam giác Pascal thì bằng $2^m$ – đây là kiến thức quen thuộc.
Khi $n$ còn nhỏ, cụ thể là $n \leq 5$, hàng thứ $n – 1$ có không quá 5 phần tử. Lúc đó “5 phần tử đầu tiên” chính là toàn bộ hàng, nên $R(n) = 2^{n-1}$ thật, không có gì giả ở đây cả. Sang $n = 6$, hàng thứ 5 có 6 phần tử là 1, 5, 10, 10, 5, 1. Công thức chỉ lấy 5 phần tử đầu và bỏ lại phần tử cuối cùng bằng 1, nên kết quả là $32 – 1 = 31$.
Vậy sự trùng hợp có nguyên nhân rõ ràng. Hai công thức khác nhau cho cùng một kết quả chừng nào các số còn đủ nhỏ để phần bị cắt bỏ chưa kịp xuất hiện. Cái “quy luật” mà trực giác nhìn thấy thực ra là cái bóng của một công thức khác, chiếu trùng khít trong 5 trường hợp đầu.
Moser cảnh báo từ năm 1949, Guy đặt tên cho hiện tượng
Leo Moser đã dùng ví dụ này từ năm 1949, trong một bài viết về sự nguy hiểm của suy luận quy nạp đăng trên tạp chí Mathematics Magazine. Tựa đề bài viết của ông nói thẳng vấn đề: “On the danger of induction” – về mối nguy của phép quy nạp. Đây là tư liệu xuất bản rõ ràng, không phải giai thoại truyền miệng.
Gần bốn mươi năm sau, năm 1988, nhà toán học Richard K. Guy gom hàng loạt ví dụ tương tự vào một bài báo trên tạp chí American Mathematical Monthly và đặt cho hiện tượng này cái tên “luật mạnh của các số nhỏ” (Strong Law of Small Numbers). Câu mở đầu của ông được trích dẫn lại rất nhiều: “There aren’t enough small numbers to meet the many demands made of them” – tạm dịch là các số nhỏ không đủ nhiều để đáp ứng hết những vai trò người ta bắt chúng đóng. Bài báo này về sau nhận giải thưởng Lester R. Ford năm 1989.
Ý của Guy là các con số nhỏ xuất hiện trong quá nhiều bối cảnh khác nhau, nên chúng hay “đóng trùng vai” của nhau. Hai quy luật hoàn toàn khác bản chất cho ra cùng vài giá trị đầu là chuyện bình thường trong toán học, và dãy số của Moser là ví dụ gọn nhất cho điều đó.
Ba chỗ dễ ngã khi làm việc với dãy số
Kết luận sau vài số hạng đầu. Năm số hạng khớp với một công thức không chứng minh được điều gì về số hạng thứ sáu. Trong bài toán này, cái giá của kết luận vội chỉ là lệch đi 1 đơn vị, 31 thay vì 32 – đủ nhỏ để nhiều người tưởng mình đếm nhầm, và đủ thật để đáp án sai hẳn.
Tin vào hình vẽ đẹp. Hình càng đối xứng càng dễ xuất hiện điểm đồng quy bất ngờ, và đáp án đổi theo, như trường hợp lục giác đều tụt từ 31 xuống 30. Hình vẽ giúp trực giác, nhưng câu hỏi “các điểm có đang ở vị trí tổng quát không” phải được trả lời bằng lập luận, không bằng cảm giác.
Đếm bằng mắt trên cấu trúc phức tạp. Mới ở mức 6 điểm, hình đã có 15 dây và 15 giao điểm. Đếm miền trực tiếp gần như chắc chắn sót. Cách đếm đáng tin là đếm gián tiếp qua cấu trúc tạo ra chúng – số dây và số giao điểm – như công thức ở phần trên.
Toán Khó từng đăng một bài theo chiều ngược lại: 0,999… = 1, một đẳng thức trông vô lý nhưng đúng. Bài toán Moser là mặt còn lại của cùng một bài học: một quy luật trông hiển nhiên nhưng sai. Cả hai đều nhắc rằng cảm giác “rõ ràng là thế” không phải một bước lập luận.
Câu hỏi thường gặp
Vì sao số thứ sáu không phải 32? Vì số miền tối đa bằng $1 + \binom{n}{2} + \binom{n}{4}$, thay $n = 6$ cho ra 31. Quy luật lũy thừa của 2 chỉ là trùng hợp ở 5 số đầu, khi tổng 5 phần tử đầu của hàng Pascal còn trùng với tổng toàn hàng.
Công thức tổng quát tính số miền là gì? Là $R(n) = 1 + \binom{n}{2} + \binom{n}{4}$, áp dụng khi không có 3 đường chéo nào đồng quy bên trong hình tròn. Theo công thức này, $n = 7$ cho 57 miền và $n = 8$ cho 99 miền.
Vẽ 6 điểm thành lục giác đều thì có bao nhiêu miền? Có 30 miền. Ba đường chéo chính của lục giác đều cùng đi qua tâm, làm tổng số giao điểm bên trong giảm từ 15 xuống 13, và số miền giảm theo xuống 30 thay vì 31.
Bài viết cho bạn của Toán Khó. Nếu muốn bài viết về chủ đề nào, hãy liên hệ với chúng mình nhé!
[…] Khó từng kể một cú lừa trực giác họ hàng: dãy số 1, 2, 4, 8, 16 của bài toán Moser, nơi đáp án “hiển nhiên” 32 hóa ra là 31. Nghịch lý sinh nhật là cùng […]
[…] Nếu bạn thích kiểu bài toán mà trực giác đánh lừa người giải, thử tiếp bài về dãy số 1, 2, 4, 8, 16 và cú lừa ở số thứ sáu – ở đó quy luật tưởng như hiển nhiên sụp đổ ngay tại số hạng tiếp […]
[…] đẹp đến mức khó tin. Cùng tinh thần kiểm chứng mẫu hình đó, xem thêm bài dãy số 1, 2, 4, 8, 16 rồi 31 và nghịch lý […]