Câu hỏi 15
Alice có bản đồ của xứ sở thần tiên, một đất nước bao gồm $n \geqslant 2$ thị trấn. Đối với mọi
cặp thị trấn, có một con đường hẹp đi từ thị trấn này sang thị trấn khác. Một ngày nọ, tất cả các con đường được tuyên bố là chỉ có "một chiều". Alice không có thông tin về hướng đi của các con đường, nhưng Vua Cơ đã đề nghị giúp đỡ cô. Cô được phép hỏi anh ta một số câu hỏi. Với mỗi câu hỏi lần lượt, Alice chọn một cặp thị trấn và Vua Cơ cho cô biết hướng 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 ngoài hay không. Chứng minh rằng cô ấy luôn có thể tìm ra bằng cách hỏi tối đa $4 n$ câu hỏi.
Nhận xét. Vấn đề này có thể được đặt ra bằng một tuyên bố rõ ràng về điểm được trao cho các giới hạn yếu hơn $c n$ đối với một số $c\gt 4$, theo kiểu IMO 2014 Bài toán 6.
cặp thị trấn, có một con đường hẹp đi từ thị trấn này sang thị trấn khác. Một ngày nọ, tất cả các con đường được tuyên bố là chỉ có "một chiều". Alice không có thông tin về hướng đi của các con đường, nhưng Vua Cơ đã đề nghị giúp đỡ cô. Cô được phép hỏi anh ta một số câu hỏi. Với mỗi câu hỏi lần lượt, Alice chọn một cặp thị trấn và Vua Cơ cho cô biết hướng 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 ngoài hay không. Chứng minh rằng cô ấy luôn có thể tìm ra bằng cách hỏi tối đa $4 n$ câu hỏi.
Nhận xét. Vấn đề này có thể được đặt ra bằng một tuyên bố rõ ràng về điểm được trao cho các giới hạn yếu hơn $c n$ đối với một số $c\gt 4$, theo kiểu IMO 2014 Bài toán 6.