Chứng minh: trong cuộc sống luôn có ai đó không hạnh phúc!

Trước hết, xin nói rõ đây không phải là một truyện cười. Ngược lại, có lẽ bạn sẽ cần phải tập trung một chút để hiểu cách chứng minh (và một khi đã hiểu, tớ tin bạn sẽ cảm thấy rất thú vị!). Chẳng là vừa qua, đọc một chương đầu trong cuốn sách giáo khoa (Algorithm Design, tác giả Jon Kleinberg và Éva Tardos, NXB Pearson), thấy nó thảo luận về một số vấn đề về các thuật toán quá hay, lại rất gần với cuộc sống với rất nhiều những chi tiết thú vị (và cả buồn cười) nên muốn viết lại chia sẽ với các bạn. Mặc dù cuốn sách nặng về thảo luận các thuật toán lập trình khá rắc rối, tớ đã cố gắng viết lại cho dễ hiểu với tất cả mọi người. Tớ tạm đặt tên cho bài toán là: Bài toán về Xã hội bền vững.

Ngoài lề: Vừa qua tớ đã nhận được tin từ cả bên Nhạc Việt và Nhạc Số về sự ra mắt của phiên bản mới. Bên Nhạc Việt đã có sự thay đổi rất lớn và tích cực về giao diện, còn bên nhạc số thì theo những gì tớ thấy từ phiên bản “Closed Beta” (bản thử nghiệm nội bộ) cũng rất hứa hẹn. Một khi Nhạc Số chính thức cho ra phiên bản mới và Nhạc Việt hoàn thiện nốt những gì họ đang làm (đặc biệt có lẽ là tốc độ truy cập), tớ sẽ có một bài viết so sánh lần 2 về hai dịch vụ này.

Bài toán về một “xã hội bền vững”

Bài toán sau xuất phát từ thực tế hôn nhân trong hầu hết các xã hội hiện đại mà chúng ta đang sống (trừ các nước Ả Rập, Hồi giáo). Hai nhóm đối tượng trong trường hợp này là nam giới và nữ giới. Để đơn giản, hãy giả sử số người nam bằng số người nữ (thực tế cũng gần vậy) và mỗi người chỉ được lấy một người khác giới (nguyên tắc một vợ - một chồng). Hãy gọi M = {m1, m2, …, mN) là tập hợp nam giới, và F = {f1, f2,…, fN} là tập hợp của nữ giới. Hơi buồn cười một tí, nhưng hãy giả sử rằng mỗi ông đều có một danh sách những cô mà mình thích sắp xếp theo thứ tự giảm dần, và ngược lại, mỗi cô cũng để ý nhiều anh và cũng xắp xếp các anh này theo mức độ cô ta thích anh ta. Tất nhiên, ai cũng muốn được lấy người mình thích nhất trong danh sách, hay ít ra cũng là người mình thích nhất trong danh sách còn lại.

Điều chúng ta muốn là liệu có một “thuật toán” nào để có một xã hội “bền vững”. Thế nào là một xã hội “bền vững”? Hãy thử tìm hiểu xem thế nào là một xã hội “không bền vững”.

“Xã hội bền vững”

Xét một xã hội thu nhỏ có 2 người nam là M1 và M2, và 2 nữ là F1 và F2. Mỗi người trong số họ có danh sách những người mình thích như sau:

(i) M1 thích F1 hơn F2
(ii) M2 thích F1 hơn F2
(iii) F1 thích M1 hơn M2
(iv) F2 thích M1 hơn M2

Xã hội trên sẽ là xã hội không bền vững nếu như chúng ta gán các cặp như sau: (M1, F2) và (M2, F1). Lý do là vì m1 thích F1 và ngược lại F1 cũng thích m1 nên cả hai luôn có xu hướng tìm cách “bỏ trốn” để đến với nhau. Ngược lại, xã hội trên sẽ là bền vững với cách chia cặp như sau: (M1, F1), (M2, F2).

Hãy suy nghĩ thêm một chút và đọc lại đoạn trên để thật sự phân biệt được xã hội bền vững và không bền vững trước khi đi tìm thuật toán cho vấn đề này.

… và thuật toán của các bà mối!

Nhưng trước khi đi vào tìm một thuật toán cho vấn đề, có lẽ chúng ta nên tìm hiểu xem: liệu với bất kỳ xã hội nào chúng ta cũng sẽ tìm đuợc ít nhất một cách sẵp xếp để nó bền vững hay không?

Hãy bắt đầu thật đơn giản: tất cả mọi người trong xã hội đều đang độc thân. Giả sử như một người đàn ông độc thân M chọn cưới người phụ nữ F, là người anh ta thích nhất trong danh sách những người mà anh ta để ý! Liệu nếu để M cưới F thì có thể dẫn đến một xã hội bền vững hay không? Câu trả lời là không nhất thiết bởi có thể, sau một thời gian, một người đàn ông độc thân M2 - cũng thích F hơn tất cả những người con gái mà anh ta gặp - cũng muốn cầu hôn cô ta. Sẽ thật không hay nếu F đã lỡ đồng ý cưới M nhưng lại thích M2 hơn. Những ngược lại, nếu F không đồng ý với M từ đầu thì biết đâu sẽ chẳng có ai khác hỏi cưới cô ta. Một cách giải quyết tự nhiên sẽ là, hãy để M và F bước vào một giai đoạn trung gian trước khi thật sự cưới nhau. Và đó chính là thời gian mà chúng ta gọi là “ĐÍNH HÔN”.

Kế tiếp, chúng ta chuyển đến một giai đoạn mà tại lúc đó, trong xã hội, có một số cặp đã đính hôn nhưng vẫn còn nhiều người chưa kết hôn. Điều gì có thể xảy ra ở giai đoạn này? Hãy xét từ góc độ một người đàn ông còn đang độc thân M2. Đến một lúc nào đó, anh ta quyết định mình cần lấy vợ và … duyệt qua danh sách những người mà anh ta để ý, chọn người anh ta thích nhất trong số đó là F và gửi lời cầu hôn. Có hai khả năng: nếu F vẫn còn đang độc thân, tất nhiên M và F cũng sẽ bước vào giai đoạn đính hôn như ở trên. Ngược lại, nếu F đã đính hôn với người khác (chưa cưới) - M1, sẽ có hai khả năng phụ nữa: nếu F thích M2 hơn là người mà cô ta đang đính hôn M1, F sẽ hủy hôn với M1 và đính hôn với M2 (M1 trở lại tình trạng độc thân). Nếu F thích người cô ta đang đính hôn M1 hơn, cô ta sẽ từ chối và M2 sẽ phải tìm một người khác trong danh sách của anh ta.

Quá trình trên sẽ cứ tiếp tục cho đến khi nào trong xã hội không còn ai sống độc thân (hãy cứ giả sử rằng không ai chọn sống độc thân cả). Để tóm tắt quá trình, xin xem đoạn thuật toán sau:

Tuy không hiển nhĩên, nhưng bạn có thể dễ dàng chứng minh được rằng với thuật toán trên, chúng ta sẽ luôn có được xã hội bền vững như định nghĩa ở cuối phần đầu bài viết. Tớ không ghi các chứng minh cụ thể ở đây vì thật ra đó không phải là mục đích chính của bài viết, nhưng các bạn có thể lần lượt chứng minh các tính chất nhỏ sau để chứng minh khẳng định trên (chủ yếu dùng phản chứng):

(i) Một người phụ nữ sẽ mãi trong tình trạng đính hôn kể từ lần đầu tiên cô ta được cầu hôn (trừ khi cô ta cưới luôn) và trong tất cả những lần đính hôn kế tiếp, cô ta sẽ luôn gặp người đàn ông mà cô ta thích hơn người trước đó.
(ii) Bất kể thế nào, thứ tự những người phụ nữ mà một người đàn ông chọn cầu hôn sẽ ngày càng tệ hơn (“tệ hơn” ở đây tất nhiên nghĩa là trong danh sách của anh ta).
(iii) Thuật toán trên sẽ dừng sau tối đa n^2 lần chạy.
(iv) Tại bất kỳ thời điểm nào, nếu còn một người đàn ông độc thân thì chắc chắn đâu đó cũng sẽ còn một người phụ nữ chưa chồng.

Kết luận thú vị

Đến đây, hi vọng bạn ít ra đã hiểu được vấn đề và cách giải quyết ở mà ở trên tớ tóm tắt. Ngoài chỗ giải thích về khái niệm của việc “đính hôn” ở trên, điều tớ cảm thấy thú vị khi đọc phần này trong sách chính là ở đoạn nó mở rộng thảo luận vấn đề – như sau:

Hãy thử áp dụng thuật toán trên cho một xã hội thu nhỏ gồm 2 nam (M1 và M2) và 2 nữ (F1 và F2), mỗi người trong số họ có danh sách những người họ để ý như sau:

M1 thích F1 hơn F2
M2 thích F2 hơn F1
F1 thích M2 hơn M1
F2 thích M1 hơn M2

Bằng cách áp dụng thuật toán trên, chúng ta sẽ đi đến một kết quả duy nhất: (M1 cưới F1) và (M2 cưới F2). Đây rõ ràng là một xã hội bền vững như chúng ta muốn. Tuy nhiên, còn có một cách xắp xếp khác cũng là một xã hội bền vững: (M2 cưới F1) và (M1 cưới F2) mà với thuật toán trên chúng ta sẽ luôn bỏ sót. Điểm khác nhau giữa hai cách xắp xếp là gì? Trong cách sắp xếp đầu, vì người đàn ông là người được chọn người phụ nữ mình muốn nên trong những trường hợp như trên, tất cả mọi người đàn ông đều cưới được người mà anh ta thích nhất, bất kể ý thích của người phụ nữ (hoàn toàn có thể có trường hợp tất cả những người phụ nữ đều phải lấy người mà họ ít thích nhất). Rõ ràng, thuật toán của chúng ta KHÔNG công bằng – ưu tiên cho nam giới (đó cũng là thực tế xã hội). Nhưng giả sử như chúng ta quyết định để cho người phụ nữ được quyền chọn bạn đời trước, thì trường hợp ngược lại sẽ xảy ra: sẽ có trường hợp tất cả nữ giới đều hạnh phúc trong khi… :). Chúng ta rút ra được kết luận gì?

Đọc cả chương sách chỉ toàn nói về thuật toán nhưng rất lôi cuốn và thú vị bởi những kết luận rất bất ngờ như trên. Đó là điều mà không phải cuốn sách nào cũng có thể đạt được. Nếu có thể, các bạn hãy tìm đọc cuốn Algorithm Design (Thiết kế thuật toán) của hai đồng tác giả Jon Kleinberg và Éva Tardos, nhà xuất bản Pearson.

Trang 2: Nguồn gốc bài toán (nếu bạn muốn biết thêm)

Trang: Next page