Một bộ bài 52 lá có 52 giai thừa cách sắp xếp, tức 52 × 51 × 50 × … × 2 × 1, xấp xỉ 8,07 × 10 mũ 67, một con số có 68 chữ số. Con số này lớn đến mức nếu mọi người trên Trái Đất cùng xáo bài mỗi giây một lần từ thuở vũ trụ hình thành tới nay, tổng số lần xáo vẫn chưa bằng một phần tỷ tỷ tỷ của nó. Vì vậy một lần xáo thật kỹ gần như chắc chắn cho ra một thứ tự chưa từng xuất hiện trong lịch sử.
Chữ "thật kỹ" rất quan trọng. Một bộ bài mới bóc hộp được sắp sẵn theo thứ tự, và vài lần xáo vụng không đủ để phá trật tự ấy. Các nhà toán học đã tính được cần khoảng bảy lần xáo kiểu riffle (chia đôi bộ bài rồi thả xen kẽ) để bộ bài trở nên gần như ngẫu nhiên. Bài này giải thích cả hai con số.
Giai thừa: đếm số cách xếp hàng
Bắt đầu từ ví dụ nhỏ. Có ba người A, B, C xếp hàng. Người đứng đầu có 3 lựa chọn, người thứ hai còn 2, người cuối chỉ còn 1, tổng cộng 3 × 2 × 1 = 6 cách: ABC, ACB, BAC, BCA, CAB, CBA. Phép nhân liên tiếp từ n xuống 1 được gọi là n giai thừa, viết là n!. Mỗi cách xếp gọi là một hoán vị.
Giai thừa tăng nhanh đến mức đáng sợ. 5! = 120, 10! = 3.628.800, tức mười học sinh có hơn 3,6 triệu cách xếp hàng. 13! đã vượt 6 tỷ, 20! vào khoảng 2,4 × 10 mũ 18. Tới 52! thì con số có 68 chữ số, bắt đầu bằng 80.658.175 và kết thúc bằng mười hai chữ số 0, vì trong tích có rất nhiều cặp 2 × 5.
So với lũy thừa của 2 mà ta thấy ở các bài toán gấp đôi, giai thừa còn tăng nhanh hơn. 2 mũ 52 chỉ khoảng 4,5 × 10 mũ 15, trong khi 52! lớn hơn tới khoảng 10 mũ 52 lần. Lý do là ở phép gấp đôi, mỗi bước nhân với 2; còn ở giai thừa, mỗi bước nhân với một số ngày càng lớn.
52! lớn cỡ nào: vài phép so sánh
Những phép so sánh dưới đây dùng các ước tính thường được công bố; mục đích là thấy bậc độ lớn, không phải con số chính xác tuyệt đối:
- Tuổi vũ trụ tính bằng giây: khoảng 13,8 tỷ năm, tức chừng 4,4 × 10 mũ 17 giây. 52! lớn hơn con số này khoảng 10 mũ 50 lần.
- Mọi người cùng xáo: giả định 8 tỷ người, mỗi người xáo một lần mỗi giây, liên tục suốt 13,8 tỷ năm, tổng cộng khoảng 3,5 × 10 mũ 27 lần xáo. Con số đó vẫn nhỏ hơn 52! khoảng 2 × 10 mũ 40 lần.
- Số nguyên tử của Trái Đất: thường được ước khoảng 10 mũ 50. 52! lớn hơn số nguyên tử của cả hành tinh tới hàng trăm triệu tỷ lần.
- Rubik 3×3: khối Rubik có khoảng 4,3 × 10 mũ 19 trạng thái, đã là con số khổng lồ, nhưng chỉ là hạt bụi so với 52!.
Có thể kiểm tra khả năng hai lần xáo ngẫu nhiên trùng nhau bằng cách tính giống bài toán trùng ngày sinh: với 3,5 × 10 mũ 27 lần xáo, xác suất có ít nhất một cặp trùng thứ tự vào khoảng một phần mười nghìn tỷ. Nói "gần như chắc chắn chưa từng có" là nói rất thận trọng.
Xáo bao nhiêu lần thì đủ: con số 7
Năm 1992, hai nhà toán học Dave Bayer và Persi Diaconis công bố một bài báo phân tích kiểu xáo riffle, cách chia bộ bài thành hai nửa rồi thả các lá đan xen vào nhau. Họ dùng một mô hình toán học khá sát với cách người thật xáo bài, và đo xem sau k lần xáo, bộ bài còn cách trạng thái hoàn toàn ngẫu nhiên bao xa.
Kết quả nổi tiếng: với bộ 52 lá, sau 4 hay 5 lần xáo bộ bài vẫn còn rất "có trật tự", gần như chưa thay đổi về mặt thống kê. Tới khoảng lần thứ 6 và 7, khoảng cách tới ngẫu nhiên giảm đột ngột; sau 7 lần, bộ bài đã đủ gần ngẫu nhiên cho hầu hết mục đích. Xáo thêm vẫn giúp, nhưng mỗi lần chỉ cải thiện thêm một ít. Hiện tượng "đứng yên rồi sụp nhanh" này được gọi là hiệu ứng ngưỡng (cutoff phenomenon).
Persi Diaconis từng là ảo thuật gia chuyên nghiệp trước khi thành nhà toán học, nên ông hiểu rõ những ảo thuật gia lợi dụng các bộ bài xáo chưa đủ như thế nào. Một số trò ảo thuật chỉ chạy được vì khán giả xáo hai, ba lần rồi tin rằng bộ bài đã lộn xộn hoàn toàn, trong khi phần lớn trật tự ban đầu vẫn còn nguyên.
Vì sao 4 hay 5 lần xáo chưa đủ: chuỗi tăng dần
Có một cách hiểu trực quan lý do phải cần khoảng bảy lần. Hãy đánh số các lá từ 1 đến 52 theo thứ tự ban đầu. Sau một lần riffle, bộ bài là hai dãy con đan vào nhau, mỗi dãy vẫn giữ thứ tự tăng dần: nếu bạn rút riêng các lá 1, 2, 3… theo thứ tự xuất hiện, chúng tạo thành tối đa hai chuỗi tăng dần. Mỗi lần riffle tiếp theo nhiều nhất chỉ làm số chuỗi này tăng gấp đôi: sau 2 lần tối đa 4 chuỗi, sau 3 lần tối đa 8, sau 4 lần tối đa 16, sau 5 lần tối đa 32.
Trong khi đó, một bộ bài xếp hoàn toàn ngẫu nhiên có trung bình khoảng 26 chuỗi tăng dần, và thường dao động quanh con số này. Sau 4 lần riffle, bộ bài không thể có quá 16 chuỗi, nên một người có kinh nghiệm hoặc một phép kiểm thống kê đơn giản vẫn nhận ra dấu vết thứ tự cũ. Sau 5 lần, giới hạn 32 bắt đầu chạm vùng của bộ bài ngẫu nhiên, sau 6 và 7 lần thì vượt hẳn, nên dấu vết mờ đi nhanh. Chính phép đếm chuỗi tăng dần là công cụ cốt lõi trong phân tích của Bayer và Diaconis.
Các kiểu xáo bài khác nhau ngẫu nhiên đến đâu
Không phải cách xáo nào cũng hiệu quả như nhau. Tổng hợp những gì toán học về xáo bài cho biết:
| Kiểu xáo | Cách làm | Mức độ trộn |
|---|---|---|
| Riffle (thả xen) | Chia đôi, thả hai nửa đan vào nhau | Khoảng 7 lần là đủ cho bộ 52 lá |
| Overhand (tuồn tay) | Rút từng nắm nhỏ từ tay này sang tay kia | Rất kém; cần hàng nghìn lần mới tương đương |
| Trải bàn (xào bài) | Trải úp bài ra bàn và đảo đều bằng hai tay | Tốt nếu đảo đủ lâu, khoảng một phút |
| Xáo hoàn hảo (faro) | Chia đúng hai nửa 26 lá, xen kẽ đúng từng lá một | Không ngẫu nhiên chút nào; 8 lần quay về thứ tự cũ |
Dòng cuối là chi tiết thú vị nhất. Một lần xáo hoàn hảo kiểu giữ lá trên cùng ở trên (out-shuffle) là một phép sắp xếp hoàn toàn xác định. Lặp lại đúng 8 lần, bộ 52 lá trở về đúng thứ tự ban đầu. Những người luyện được kỹ thuật này dùng nó để biểu diễn, chứ không phải để trộn bài.
Bài học rút ra: "xáo đều tay" theo nghĩa khéo léo hoàn hảo lại là cách kém ngẫu nhiên nhất. Sự ngẫu nhiên đến từ chính những sai lệch nhỏ của bàn tay người.
Máy tính xáo bài thế nào
Khi chơi bài trên điện thoại hay máy tính, việc xáo được làm bằng thuật toán. Thuật toán chuẩn được gọi là xáo Fisher–Yates (mô tả lần đầu năm 1938, được Richard Durstenfeld đưa vào máy tính năm 1964 và Donald Knuth phổ biến): đi từ lá cuối lên đầu, mỗi bước đổi chỗ lá hiện tại với một lá chọn ngẫu nhiên trong phần chưa xử lý. Nếu nguồn số ngẫu nhiên tốt, mọi thứ tự trong 52! đều có cơ hội như nhau.
Vấn đề nằm ở chữ "nếu". Máy tính thường dùng bộ sinh số giả ngẫu nhiên, khởi đầu từ một "hạt giống". Nếu hạt giống chỉ có 32 bit, tức khoảng 4,3 tỷ giá trị, thì phần mềm chỉ tạo được tối đa 4,3 tỷ thứ tự khác nhau, một phần rất nhỏ của 52!. Muốn với tới mọi thứ tự, nguồn ngẫu nhiên cần ít nhất khoảng 226 bit, vì 2 mũ 226 mới vượt 52!.
Trong lịch sử phần mềm đã có những trường hợp chương trình xáo bài dùng hạt giống quá nhỏ hoặc lấy từ đồng hồ hệ thống, khiến người hiểu kỹ thuật có thể đoán trước thứ tự bài. Đây là ví dụ điển hình cho thấy con số 52! không chỉ là chuyện tò mò, mà còn là yêu cầu kỹ thuật thật khi làm phần mềm cần sự công bằng.
Hiểu nhầm hay gặp về xáo bài
"Xáo càng nhiều càng tốt, không có giới hạn." Xáo thêm luôn có ích, nhưng sau khoảng 7 lần riffle, lợi ích của mỗi lần thêm rất nhỏ. Xáo 20 lần không ngẫu nhiên hơn đáng kể so với 10 lần.
"Bộ bài mới mua đã ngẫu nhiên sẵn." Ngược lại, bộ bài mới thường được sắp theo chất và theo thứ tự từ át tới già. Đây là điểm xuất phát có trật tự nhất, cần xáo kỹ nhất.
"Tráo kiểu tuồn tay nhanh là đủ." Kiểu tuồn tay chỉ dịch chuyển các nhóm lá liền nhau, nên trật tự bị phá rất chậm. Các phân tích toán học ước rằng cần số lần lớn hơn rất nhiều so với riffle để đạt cùng mức trộn.
"Thứ tự đặc biệt như từng chất liền nhau khó xuất hiện hơn." Sau khi xáo thật ngẫu nhiên, thứ tự xếp gọn từng chất có xác suất đúng bằng mọi thứ tự cụ thể khác: 1 trên 52!. Ta thấy nó "đặc biệt" chỉ vì ta có tên gọi cho nó.
Câu hỏi thường gặp
52 giai thừa chính xác là bao nhiêu?
52! là một số có 68 chữ số, xấp xỉ 8,0658 × 10 mũ 67, bắt đầu bằng các chữ số 80658175170943878571 và kết thúc bằng mười hai chữ số 0. Mười hai số 0 ở cuối đến từ các cặp thừa số 2 và 5 trong tích, ví dụ 10, 20, 25, 50 đóng góp nhiều nhất.
Vì sao 0 giai thừa lại bằng 1?
Theo quy ước, 0! = 1 vì chỉ có đúng một cách sắp xếp một tập rỗng: không làm gì cả. Quy ước này cũng giữ cho công thức n! = n × (n − 1)! đúng khi n = 1, và giúp các công thức tổ hợp không phải thêm trường hợp ngoại lệ.
Có thể xáo bài bằng tay đạt ngẫu nhiên hoàn toàn không?
Không có cách nào đạt ngẫu nhiên tuyệt đối, nhưng có thể gần tới mức không phân biệt được. Theo phân tích của Bayer và Diaconis, khoảng 7 lần riffle cho bộ 52 lá đã đủ cho hầu hết mục đích. Kết hợp thêm một lần trải bài ra bàn đảo đều là cách các nhà toán học hay khuyên.
Bộ bài 54 lá có thêm hai lá phụ thì số cách xếp tăng bao nhiêu?
Số cách xếp là 54!, bằng 52! nhân với 53 nhân 54, tức lớn hơn 52! khoảng 2.862 lần. Chỉ thêm hai lá mà số cách xếp tăng gần ba nghìn lần, cho thấy giai thừa tăng nhanh như thế nào khi số đối tượng tăng lên.
Giai thừa được dùng ở đâu ngoài bài?
Giai thừa xuất hiện mỗi khi cần đếm số cách sắp xếp: lịch thi đấu, thứ tự giao hàng qua nhiều điểm, mật khẩu không lặp ký tự, xếp chỗ ngồi. Bài toán người giao hàng đi qua n điểm có số lộ trình tăng theo giai thừa, nên với vài chục điểm, máy tính không thể thử hết từng lộ trình.
Vì sao xáo hoàn hảo 8 lần lại trở về thứ tự cũ?
Mỗi lần xáo hoàn hảo đưa lá ở vị trí thứ k tới một vị trí xác định theo một quy tắc số học cố định. Với bộ 52 lá, quy tắc ấy lặp lại sau đúng 8 bước vì 2 mũ 8 = 256 chia cho 51 dư 1. Bộ bài có số lá khác sẽ có chu kỳ khác.