Câu hỏi 80
Alice có một bản đồ của Xứ Sở Thần Tiên, một đất nước gồm $n \geqslant 2$ thị trấn. Với mỗi cặp thị trấn, có một con đường hẹp đi từ thị trấn này tới thị trấn kia. Một ngày nọ, tất cả các con đường đều được công bố là đường "một chiều". Alice không có thông tin gì về chiều của các con đường, nhưng Vua Cơ đã đề nghị giúp cô. Cô được phép hỏi ông một số câu hỏi. Với mỗi câu hỏi, Alice chọn một cặp thị trấn và Vua Cơ cho cô biết chiều của con đường nối hai thị trấn đó.
Alice muốn biết liệu có ít nhất một thị trấn ở Xứ Sở Thần Tiên có nhiều nhất một con đường đi ra hay không. Chứng minh rằng cô luôn có thể biết được điều đó bằng cách hỏi nhiều nhất $4 n$ câu hỏi.
Alice muốn biết liệu có ít nhất một thị trấn ở Xứ Sở Thần Tiên có nhiều nhất một con đường đi ra hay không. Chứng minh rằng cô luôn có thể biết được điều đó bằng cách hỏi nhiều nhất $4 n$ câu hỏi.