Câu hỏi 49
Hôm qua có $n\ge4$ người ngồi quanh một bàn tròn. Mỗi người chỉ nhớ hai hàng xóm của mình là ai, không nhớ ai ngồi bên trái và ai bên phải. Hôm nay bạn muốn xếp lại chính những người đó quanh bàn sao cho mỗi người có đúng hai hàng xóm như hôm qua (hàng xóm bên trái hôm qua có thể trở thành hàng xóm bên phải hôm nay). Bạn được hỏi một số người; mỗi người được hỏi sẽ chỉ ra hai hàng xóm hôm qua của mình.
a. Xác định số người ít nhất $f(n)$ cần hỏi để chắc chắn thành công nếu các câu hỏi sau không được phụ thuộc kết quả câu hỏi trước. Nghĩa là phải chọn trước toàn bộ danh sách người sẽ hỏi, trước khi thực sự hỏi bất kỳ ai.
b. Xác định số người ít nhất $g(n)$ cần hỏi để chắc chắn thành công nếu câu hỏi sau có thể phụ thuộc kết quả câu hỏi trước. Nghĩa là có thể chờ câu trả lời đầu tiên rồi mới chọn người hỏi tiếp theo, và cứ như vậy.
a. Xác định số người ít nhất $f(n)$ cần hỏi để chắc chắn thành công nếu các câu hỏi sau không được phụ thuộc kết quả câu hỏi trước. Nghĩa là phải chọn trước toàn bộ danh sách người sẽ hỏi, trước khi thực sự hỏi bất kỳ ai.
b. Xác định số người ít nhất $g(n)$ cần hỏi để chắc chắn thành công nếu câu hỏi sau có thể phụ thuộc kết quả câu hỏi trước. Nghĩa là có thể chờ câu trả lời đầu tiên rồi mới chọn người hỏi tiếp theo, và cứ như vậy.