Thử sức với câu đố tưởng chừng không có lời giải

Theo Alex Bellos, tác giả phụ trách chuyên mục Toán của tờ The Guardian, câu đố này dựa trên khái niệm Zero Knowledge Proof (ZKP) - giao thức cho phép người dùng chứng minh họ biết một kiến thức nào đó nhưng không tiết lộ cho người khác biết kiến thức đó là như thế nào.

Ông cho biết thêm giải Abel (được coi như Nobel Toán học) năm 2021 được trao cho người tiên phong trong lĩnh vực Zero Knowledge Proof - nhà khoa học László Lovász (Viện Toán học Alfréd Rényi và ĐH Eötvös Loránd tại Budapest, Hungary), cùng Avi Wigderson (Viện Nghiên cứu cao cấp tại Princeton, Mỹ).

Câu đố như sau:

Isla làm việc trong một văn phòng có 100 nhân viên. Ngày nọ, cô phát hiện chiếc kẹp giấy ưa thích của mình bị người khác lấy cắp. Cô xác định đối tượng đáng ngờ. Annabel, đồng nghiệp của cô, cho biết cô ấy cũng nghi ngờ một người.

Isla muốn biết xem liệu cô và Annabel có cùng nghi ngờ một người hay không nhưng cả hai lại không muốn người kia biết mình đang nghi ngờ ai, phòng khi họ nghi ngờ đối tượng khác nhau.

Isla nghĩ mãi về cách làm thế nào để cô và Annabel có thể kiểm tra xem họ có nghi ngờ cùng một người không mà không tiết lộ thông tin đối tượng mình thấy đáng ngờ cho đối phương biết.

Câu hỏi đưa ra là liệu Isla và Annabel có thể tìm ra cách đối chiếu suy nghĩ của hai người mà không để người kia biết họ đang nghi ngờ ai hay không?

Phương pháp này cần đảm bảo sau khi đối chiếu, Isla biết được cô và Annabel có nghi ngờ cùng một người hay không. Thứ hai, họ cần đảm bảo người kia không biết họ đang không nghi ngờ ai.

Quy trình xác minh này thuộc giao thức Zero-knowledge. Alex Bellos đánh giá thoạt nhìn, đây là câu đố không có lời giải.

Ví dụ, Isla không thể nói "Người tôi nghi ngờ từng đi làm muộn hôm thứ hai" vì nó tiết lộ một số thông tin về đối tượng kia.

Ông cũng đưa ra giải pháp hai người nhờ đến bên thứ 3 là Dan, một người bạn tốt mà họ rất tin tưởng. Sau đó, Isla và Annabel cùng đánh số các nhân viên trong văn phòng từ 1 đến 100.

Tiếp đến, họ viết số thay thế tên người họ nghi ngờ vào một tờ giấy rồi đưa cho Dan. Nếu Dan xác nhận hai số giống nhau, họ nghi ngờ cùng một người và ngược lại.

Tuy nhiên, giải pháp này không hoàn hảo vì không ai có thể đảm bảo Dan không tiết lộ số mình viết cho người kia. Mọi việc đều phụ thuộc vào mức độ đáng tin của bên thứ 3. Do đó, nó không đảm bảo được việc không tiết lộ thông tin như câu đố yêu cầu.

Gần 200 người đã tham gia thảo luận về câu đố của Alex Bellos và đề xuất các biện pháp kiểm chứng xem Isla và Annabel có nghi ngờ cùng một người. Sau đó, tác giả Alex Bellos cùng đưa ra 3 phương pháp tương đối phù hợp.

Bạn có thể đưa ra biện pháp nào đảm bảo yêu cầu của đề bài hay không, tức Isla và Annabel biết được họ có nghi ngờ cùng người không và không tiết lộ thông tin về đối tượng họ nghi ngờ cho người kia?

Bạn đọc có bài toán khó cần giải đáp hoặc muốn chia sẻ những phép tính hay, có thể gửi về tòa soạn theo địa chỉ email giaoduc@zing.vn.

Bách Linh