Câu hỏi 13
Cho các số nguyên dương cố định $k$, $n$. Trong trò đoán với người nói dối, Amy chọn các số nguyên $x$, $N$ thỏa mãn $1 \leq x \leq N$. Cô cho Ben biết $N$, nhưng không cho biết $x$. Ben có thể hỏi nhiều lần liệu $x \in S$ hay không, với các tập số nguyên $S$ tùy ý. Amy trả lời có hoặc không, và có thể nói dối, nhưng nhiều nhất $k$ lần liên tiếp. Sau khi hỏi bao nhiêu câu tùy ý, Ben phải nêu một tập gồm nhiều nhất $n$ số nguyên dương. Nếu $x$ thuộc tập đó, Ben thắng; nếu không, thua. Chứng minh:
a) Nếu $n \geq 2^{k}$, Ben luôn có thể thắng.
b) Với $k$ đủ lớn, tồn tại $n \geq 1.99^{k}$ mà Ben không thể bảo đảm thắng.
a) Nếu $n \geq 2^{k}$, Ben luôn có thể thắng.
b) Với $k$ đủ lớn, tồn tại $n \geq 1.99^{k}$ mà Ben không thể bảo đảm thắng.