Đọc các bài báo về IP traceback, tôi vừa học được bài toán tuyệt đẹp sau đây:
Alice có một chuỗi C gồm n bits nhị phân cần gửi cho Bob. Tuy nhiên, mỗi lần Alice chỉ có thể gửi 1 bit và gửi xong thì Alice quên béng mất là mình đã gửi bit gì (hay bit nào). Thiết kế một protocol để Alice có thể gửi C cho Bob.
Chú thích: Alice có thể gửi bao nhiêu bits cho Bob tùy ý, miễn là trong giới hạn các ràng buộc trên. Giải bài toán trong hai trường hợp: (i) Bob biết trước n bằng bao nhiêu, và (ii) Bob không biết cả n luôn.
Impossible? Tựa đề của post đã có gợi ý.