Câu hỏi 3
Trò chơi đoán kẻ nói dối là trò chơi được chơi giữa hai người chơi $A$ và $B$. Luật chơi phụ thuộc vào hai số nguyên dương cố định $k$ và $n$ mà cả hai người chơi đều biết.
Khi bắt đầu trò chơi $A$ chọn số nguyên $x$ và $N$ với $1 \le x \le N$. Người chơi $A$ giữ bí mật $x$ và nói sự thật về $N$ với người chơi $B$. Người chơi $B$ hiện cố gắng lấy thông tin về $x$ bằng cách đặt câu hỏi cho người chơi $A$ như sau: mỗi câu hỏi bao gồm $B$ chỉ định một tập hợp $S$ số nguyên dương tùy ý (có thể là một số được chỉ định trong một số câu hỏi trước đó) và hỏi $A$ liệu $x$ có thuộc về $S$ hay không. Người chơi $B$ có thể hỏi bao nhiêu câu hỏi tùy thích. Sau mỗi câu hỏi, người chơi $A$ phải trả lời ngay có hoặc không, nhưng được phép nói dối bao nhiêu lần tùy thích; hạn chế duy nhất là, trong số $k+1$ câu trả lời liên tiếp, ít nhất một câu trả lời phải trung thực.
Sau khi $B$ hỏi bao nhiêu câu hỏi tùy thích, anh ta phải chỉ định một tập hợp $X$ tối đa $n$ số nguyên dương. Nếu $x$ thuộc về $X$ thì $B$ thắng; nếu không, anh ta sẽ thua. Chứng minh rằng:
(a) Nếu $n \ge 2^k$ thì $B$ có thể đảm bảo thắng.
(b) Với tất cả $k$ đủ lớn, tồn tại một số nguyên $n \ge (1.99)^k$ sao cho $B$ không thể đảm bảo thắng.
Khi bắt đầu trò chơi $A$ chọn số nguyên $x$ và $N$ với $1 \le x \le N$. Người chơi $A$ giữ bí mật $x$ và nói sự thật về $N$ với người chơi $B$. Người chơi $B$ hiện cố gắng lấy thông tin về $x$ bằng cách đặt câu hỏi cho người chơi $A$ như sau: mỗi câu hỏi bao gồm $B$ chỉ định một tập hợp $S$ số nguyên dương tùy ý (có thể là một số được chỉ định trong một số câu hỏi trước đó) và hỏi $A$ liệu $x$ có thuộc về $S$ hay không. Người chơi $B$ có thể hỏi bao nhiêu câu hỏi tùy thích. Sau mỗi câu hỏi, người chơi $A$ phải trả lời ngay có hoặc không, nhưng được phép nói dối bao nhiêu lần tùy thích; hạn chế duy nhất là, trong số $k+1$ câu trả lời liên tiếp, ít nhất một câu trả lời phải trung thực.
Sau khi $B$ hỏi bao nhiêu câu hỏi tùy thích, anh ta phải chỉ định một tập hợp $X$ tối đa $n$ số nguyên dương. Nếu $x$ thuộc về $X$ thì $B$ thắng; nếu không, anh ta sẽ thua. Chứng minh rằng:
(a) Nếu $n \ge 2^k$ thì $B$ có thể đảm bảo thắng.
(b) Với tất cả $k$ đủ lớn, tồn tại một số nguyên $n \ge (1.99)^k$ sao cho $B$ không thể đảm bảo thắng.