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