Câu hỏi 150
Mỗi số nguyên dương hoặc là "ngoan" hoặc là "hư", và Nhà tiên tri của các con số biết số nào thuộc loại nào. Tuy nhiên, Nhà tiên tri sẽ không trực tiếp cho bạn biết một số là ngoan hay hư. Những câu hỏi duy nhất mà Nhà tiên tri trả lời là các câu hỏi dạng "Tổng của tất cả các ước ngoan của $n$ là bao nhiêu?", trong đó $n$ là số do người hỏi chọn. Chẳng hạn, giả sử (chỉ trong ví dụ này) $2$ và $3$ là ngoan, còn $1$ và $6$ là hư. Khi đó, nếu bạn hỏi Nhà tiên tri "Tổng của tất cả các ước ngoan của $6$ là bao nhiêu?", Nhà tiên tri sẽ trả lời là $5$.
Chứng minh rằng với mọi số nguyên dương $n$ cho trước nhỏ hơn $1$ triệu, bạn có thể xác định $n$ là ngoan hay hư bằng cách hỏi Nhà tiên tri không quá bốn câu hỏi.
Chứng minh rằng với mọi số nguyên dương $n$ cho trước nhỏ hơn $1$ triệu, bạn có thể xác định $n$ là ngoan hay hư bằng cách hỏi Nhà tiên tri không quá bốn câu hỏi.