Xáo hoàn hảo (faro): vì sao 8 lần bộ bài quay về thứ tự cũ

Xáo hoàn hảo, còn gọi là xáo faro, là kiểu xáo bồ câu chia bộ bài đúng hai nửa 26 lá rồi đan xen chính xác từng lá một. Nếu giữ lá trên cùng ở nguyên trên cùng (xáo "ngoài"), bộ bài 52 lá quay về đúng thứ tự ban đầu sau 8 lần. Nếu lá trên cùng bị đẩy xuống vị trí thứ hai (xáo "trong"), phải 52 lần mới quay về, và đúng lần thứ 26 bộ bài bị đảo ngược hoàn toàn.

Xáo hoàn hảo khác xáo bồ câu thường thế nào

Xáo bồ câu thường là động tác có ngẫu nhiên: cắt lệch vài lá, các lá rơi hai ba lá một lần không đều. Chính sự lộn xộn đó làm bộ bài được trộn. Xáo hoàn hảo bỏ hết ngẫu nhiên: cắt đúng 26 và 26, rồi đan một lá trái, một lá phải, không sai một lá nào. Kết quả là một phép hoán vị tất định: cùng bộ bài vào thì luôn ra cùng một thứ tự.

Làm được động tác này bằng tay là một kỹ năng khó, cần luyện rất lâu, thường thực hiện bằng cách ép hai nửa bộ bài vào nhau theo cạnh ngắn. Vì vậy xáo hoàn hảo là chủ đề yêu thích của dân ảo thuật và của các nhà toán học, chứ không phải cách để trộn bài.

Xáo "ngoài" và xáo "trong"

Có hai cách đan, khác nhau ở lá nào rơi lên trên cùng:

• Xáo ngoài (out-shuffle): lá trên cùng của nửa trên vẫn ở trên cùng, lá dưới cùng của nửa dưới vẫn ở dưới cùng. Hai lá ngoài cùng "ở ngoài".
• Xáo trong (in-shuffle): lá trên cùng của nửa dưới chen lên đầu, lá đầu cũ xuống vị trí thứ hai. Hai lá ngoài cùng cũ chui "vào trong".

Hai tên gọi "in" và "out" thường được gắn với nhà ảo thuật người Anh Alex Elmsley, người nghiên cứu kỹ loại xáo này từ giữa thế kỷ 20. Về toán, bài viết đầy đủ nhất là "The Mathematics of Perfect Shuffles" của Persi Diaconis, Ron Graham và William Kantor, đăng năm 1983.

Ví dụ tính tay với 8 lá

Đánh số 8 lá từ trên xuống: 1 2 3 4 5 6 7 8. Nửa trên là 1 2 3 4, nửa dưới là 5 6 7 8.

• Xáo ngoài: 1 5 2 6 3 7 4 8. Lá 1 vẫn trên cùng, lá 8 vẫn dưới cùng.
• Xáo trong: 5 1 6 2 7 3 8 4. Lá 5 lên đầu, lá 4 xuống đáy.

Xáo ngoài thêm lần nữa từ 1 5 2 6 3 7 4 8: nửa trên 1 5 2 6, nửa dưới 3 7 4 8, đan ra 1 3 5 7 2 4 6 8. Lần thứ ba: nửa trên 1 3 5 7, nửa dưới 2 4 6 8, đan ra 1 2 3 4 5 6 7 8. Bộ 8 lá trở về y nguyên sau đúng 3 lần xáo ngoài. Bạn có thể kiểm bằng tám lá bài thật trong vài phút.

Vì sao 52 lá cần đúng 8 lần

Bí mật nằm trong một công thức rất gọn. Đánh số vị trí từ 0 (trên cùng) tới 51 (dưới cùng). Với xáo ngoài, lá ở vị trí i sẽ chuyển tới vị trí 2 × i, lấy phần dư khi chia cho 51, trừ lá dưới cùng luôn đứng yên. Thử: lá ở vị trí 1 (lá thứ hai) chuyển tới vị trí 2; lá ở vị trí 26 (lá đầu của nửa dưới) chuyển tới vị trí 52, chia 51 dư 1, đúng là vị trí thứ hai trong bộ bài mới.

Vậy sau k lần xáo ngoài, lá ở vị trí i đi tới vị trí 2^k × i chia dư cho 51. Bộ bài quay về như cũ khi 2^k chia 51 dư 1. Tính dần: 2, 4, 8, 16, 32, 64 (dư 13), 26, 52 (dư 1). Lần thứ 8 thì 2^8 = 256 = 5 × 51 + 1. Vậy 8 là đáp số.

Với xáo trong, đánh số vị trí từ 1 tới 52, lá ở vị trí i đi tới 2 × i chia dư cho 53. Cần 2^k chia 53 dư 1, và lần đầu tiên điều đó xảy ra là k = 52. Đặc biệt, 2^26 chia 53 dư 52, tức bằng −1: lá ở vị trí i đi tới vị trí 53 − i. Đó chính là bộ bài bị lật ngược thứ tự sau 26 lần xáo trong.

Bảng chu kỳ theo số lá

Cùng công thức, ta tính được số lần cần để quay về với bộ bài chẵn lá bất kỳ: xáo ngoài dùng phép chia dư cho n − 1, xáo trong dùng n + 1.

Bảng cho thấy con số 8 không phải "phép màu" của bộ 52 lá mà là chuyện số học: chỉ cần thêm hai lá Joker, xáo ngoài phải tới 52 lần mới về. Với 64 lá, số lá là lũy thừa của 2, chu kỳ rất ngắn.

Lá nào không bao giờ di chuyển

Khi xáo ngoài 52 lá, ngoài lá trên cùng và dưới cùng, còn một cặp đặc biệt: lá thứ 18 và lá thứ 35 (vị trí 17 và 34 nếu đếm từ 0) đổi chỗ cho nhau mỗi lần, vì 2 × 17 = 34 và 2 × 34 = 68, chia 51 dư 17. Tất cả 48 lá còn lại đi theo sáu vòng, mỗi vòng 8 vị trí. Đây là lý do toàn bộ bộ bài về chỗ cũ sau đúng 8 lần.

Mẹo nhị phân của Elmsley

Ứng dụng nổi tiếng nhất của xáo hoàn hảo là đưa lá trên cùng tới bất kỳ vị trí nào mong muốn chỉ bằng vài lần xáo. Quy tắc gắn với Alex Elmsley:

1. Muốn lá trên cùng xuống dưới đúng k lá (tức nằm ở vị trí k nếu đếm từ 0), viết k dưới dạng nhị phân.
2. Đọc từ trái sang phải: chữ số 1 thì xáo trong, chữ số 0 thì xáo ngoài.

Ví dụ: muốn lá trên cùng nằm dưới 13 lá khác, tức thành lá thứ 14. Số 13 viết nhị phân là 1101. Vậy xáo trong, xáo trong, xáo ngoài, xáo trong. Bốn lần xáo là xong. Lý do: mỗi lần xáo, vị trí của lá đó (đếm từ 0) nhân đôi, cộng thêm 1 nếu là xáo trong, đúng như cách ta ghép từng chữ số nhị phân vào bên phải một số. Mẹo này đã được kiểm trên máy với mọi vị trí từ 0 tới 51.

Xáo hoàn hảo và chuyện trộn bài

Xáo hoàn hảo cho thấy một điều ngược trực giác: một động tác càng chính xác thì càng không trộn. Toàn bộ khả năng trộn của xáo bồ câu đến từ sai số của tay người: cắt lệch vài lá, thả hai ba lá một lần. Bỏ sai số đi, ta chỉ còn một vòng quay số học khép kín.

Nhóm hoán vị sinh ra bởi hai phép xáo trong và xáo ngoài cũng được Diaconis, Graham và Kantor mô tả đầy đủ trong bài năm 1983. Với 52 lá, dù kết hợp hai phép này theo bất kỳ trình tự nào, ta cũng chỉ đạt được một phần cực nhỏ của 52! thứ tự. Lý do dễ thấy: cả hai phép đều giữ đối xứng, lá ở vị trí i và lá ở vị trí đối diện 51 − i luôn đi cùng nhau thành cặp.

Bài học áp dụng được: nếu bạn xáo bồ câu rất đều tay, gần như lá trái lá phải xen kẽ, bộ bài của bạn trộn kém hơn người xáo vụng. Các nghiên cứu về xáo bài cũng ghi nhận như vậy.

Góc nhìn hôm nay: tự thử với bộ bài nhỏ

• Lấy 8 lá, ghi số 1 tới 8 lên giấy ghi chú dán ở mặt sau nếu cần, rồi xáo ngoài bằng cách đặt hai nửa trên bàn và xen từng lá. Ba lần là về.
• Thử xáo trong với 8 lá: sáu lần mới về, và lần thứ ba bộ bài bị đảo ngược hoàn toàn (vì 2^3 = 8 chia 9 dư 8, tức −1).
• Thử mẹo Elmsley với 16 lá: muốn lá đầu nằm ở vị trí 5 (đếm từ 0), viết 5 = 101, xáo trong, xáo ngoài, xáo trong.

Không cần đôi tay của nhà ảo thuật: đặt hai nửa nằm trên bàn và xen từng lá bằng tay là được một xáo hoàn hảo chậm rãi. Cuốn Magical Mathematics (2011) của Diaconis và Graham có hẳn các chương về xáo hoàn hảo, viết cho người đọc phổ thông.