Tại sao bị lạc trên Đào Hoa Đảo

(Bản gốc của bài viết có biên tập này đã được đăng trên Blog KHMT.)

Nói tới đảo Đào Hoa là nói tới Hoàng Dược Sư, cha của Hoàng Dung và là nhạc phụ của Quách Tỉnh. Trong bộ Xạ Điêu Anh Hùng Truyện, Kim Dung tả rằng vòng ngoài của đảo trồng rất nhiều hoa đào, được sắp xếp theo trận đồ, người nào không có bản đồ thì không thể nào đi qua khu rừng đào ấy được. Về sau, Âu Dương Khắc nhờ có bản đồ của Hoàng Dược Sư nên mới cùng Âu Dương Phong và Dương Khang vào được bên trong, hạ sát mấy vị sư phụ của Quách Tỉnh, gây nên hiểu lầm khiến “trâu nước” không thèm nhìn ngó gì đến Hoàng Dung.

Rừng đào của Hoàng Dược Sư có lẽ là một dạng trận đồ (maze), đường đi quanh co khúc khuỷu làm người ta đã vào thì không biết đường ra, đi một lát thì chẳng biết mình đang ở đâu. Dưới góc nhìn toán học thì trận đồ này cũng như một đồ thị, mỗi giao lộ là một đỉnh, lối đi là các cạnh nối các đỉnh với nhau. Nếu ta xuất phát từ một điểm và rẽ một cách ngẫu nhiên (cũng như người bị lạc đang đi lung tung trong trận đồ ) thì sau một hồi, ta thực hiện được một random walk. Lý thuyết về chuỗi Markov (Markov chain) chứng minh được rằng nếu đi một lúc đủ lâu thì khả năng ta đứng ở bất kỳ một giao lộ nào cũng là bằng nhau (trong điều kiện các giao lộ đều có cùng số đường ở đâm vào). Nghĩa là ta không thể biết được rằng ta sẽ ở chỗ nào. Vì thế, nếu mọi giao lộ, mọi lối đi đều như nhau thì ta thậm chí còn không biết mình đang ở đâu, chứ chưa nói đến chuyện biết đường nào để thoát khỏi trận.

Bây giờ giả sử Âu Dương Khắc muốn tiếp cận, ve vãn Hoàng Dung. Biết rằng Hoàng Dung ở gian nhà gỗ giữa đảo, Âu Dương Khắc xuất phát từ vòng ngoài đảo, cũng vượt qua rừng đào bằng kiểu đi ngẫu nhiên. Vậy trước khi đi, Âu Dương Khắc phải chắc phải tự hỏi mình cần đi khoảng chừng bao lâu thì sẽ đến được nơi có Hoàng Dung. Nếu đi mãn đời cũng không đến nơi được thì khỏi đi làm gì cho phí sức! Đây là bài toán “thời gian tiếp cận” (hitting time) trong lý thuyết của “bước ngẫu nhiên trên đồ thị”. (Xin lưu ý: dịch “hitting time” là “thời gian tiếp cận” là một cố gắng miễn cưỡng để phù hợp với “hitting” trong “she is hitting on me”🙂 ).

Một bài toán khác cũng có thể được xét bằng bước ngẫu nhiên trên đồ thị là “Bài toán xào bài”. Giả sử ta có một bộ bài còn mới nguyên. Và để cho đơn giản thì giả sử ta xào bài bằng cách tách bộ bài ra làm 2 phần rồi đem phần dưới để lên trên, đem phần trên bỏ xuống dưới. (Các cao thủ bài bạc đang đọc bài này chắc chắn sẽ có nhiều cách xào bài hơn, chẳng hạn như xào từ giữa bộ bài, chẻ bài v.v…). Vậy ta phải xào bao nhiêu lần thì được một bộ 52 lá bài ngẫu nhiên? Nếu xem mỗi thứ tự của 52 lá bài là một đỉnh của đồ thị, cạnh của đồ thị nối với 2 đỉnh khi thứ tự này đạt được từ thứ tự kia sau một lần xào bài, thì quá trình xào bài chính là một random walk trên đồ thị đó. Tương tự như trên, ta biết rằng nếu xào bài đủ lâu thì ta không biết được 52 lá bài đang cầm trên tay là theo thứ tự nào.

Lưu ý rằng sau một hồi xào bài, 52 lá bài có thể có thứ tự bốn quân K, rồi đến 4 quân Q, rồi 4 quân J.v.v… Sao kỳ vậy, vì như vậy đâu có là ngẫu nhiên ?? Ở đây ta phải hiểu “ngẫu nhiên” là ở chỗ ta không biết được thứ tự của các lá bài cầm trên tay là như thế nào, hay nói theo toán học là ta có một phân bố đều (uniform distribution), chứ không phải thứ tự các lá bài không theo một nguyên tắc nào (no pattern). Để đạt được các thứ tự “phù hợp với nguyện vọng của người chơi” (các lá bài càng lộn xộn càng tốt), ta phải xét bài toán “thời gian tiếp cận”, xem phải xào bài trong bao lâu thì đạt được một trong những thứ tự nhất định.

Đã có những định lý rất hay về vấn đề này, nhưng chuyên môn của tôi rất hạn chế, không thể bình luận gì được🙂. Bài này được viết ra sau một buổi học rất hứng thú. Bài toán xào bài là một phần trong bài giảng đó.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: