Câu hỏi 175
Một đất nước có 64 thành phố. Có các con đường nối một số cặp thành phố, nhưng Bob không biết đó là những cặp nào (các con đường không cắt nhau nhưng có thể vượt qua nhau; hơn nữa, các con đường có thể đi theo cả hai chiều). Alice thì biết rõ toàn bộ mạng lưới. Bob có thể chọn một cặp thành phố bất kì và hỏi Alice xem chúng có được nối trực tiếp bởi một con đường hay không. Mục tiêu của Bob là xác định xem có thể đi từ bất kì thành phố nào đến bất kì thành phố nào khác hay không (có thể qua nhiều con đường liên tiếp). Chứng minh rằng không tồn tại thuật toán nào (tức là không có chiến lược nào phụ thuộc vào các câu trả lời lần lượt của Alice) cho phép Bob biết chắc chắn điều đó với ít hơn 2016 câu hỏi.