Câu hỏi 2
Cho hai số nguyên dương $k\le n$. Nước IMO có $n$ ngôi làng, một số cặp được nối bằng đường. Khoảng cách giữa hai làng là số con đường ít nhất phải đi qua trên một lộ trình từ làng này đến làng kia; nếu không có lộ trình thì khoảng cách là vô hạn.
Một người mới đến, tên Alice trong bản tiếng Anh và Xiaoxun trong bản tiếng Trung, đang cách ly nên không nhìn thấy mạng lưới đường, nhưng biết $n,k$. Cô muốn xác định khoảng cách lớn nhất giữa các làng có hữu hạn hay không. Trong mỗi cuộc gọi đến văn phòng IMO, cô nêu hai làng và hỏi khoảng cách giữa chúng lớn hơn, bằng hay nhỏ hơn $k$. Văn phòng trả lời đúng sự thật, coi khoảng cách vô hạn là lớn hơn $k$. Chứng minh cô có thể xác định điều đó bằng không quá $2n^2/k$ cuộc gọi.
Một người mới đến, tên Alice trong bản tiếng Anh và Xiaoxun trong bản tiếng Trung, đang cách ly nên không nhìn thấy mạng lưới đường, nhưng biết $n,k$. Cô muốn xác định khoảng cách lớn nhất giữa các làng có hữu hạn hay không. Trong mỗi cuộc gọi đến văn phòng IMO, cô nêu hai làng và hỏi khoảng cách giữa chúng lớn hơn, bằng hay nhỏ hơn $k$. Văn phòng trả lời đúng sự thật, coi khoảng cách vô hạn là lớn hơn $k$. Chứng minh cô có thể xác định điều đó bằng không quá $2n^2/k$ cuộc gọi.