Chủ đề này có 5 trả lời

[Crystal]

Problem: The liar's guessing game is a game played between two players $A$ and $B$. The rules of the game depend on two positive integers $k$ and $n$ which are known to both players.

At the start of the game $A$ chooses integers $x$ and $N$ with $1 \le x \le N.$ Player $A$ keeps $x$ secret, and truthfully tells $N$ to player $B$. Player $B$ now tries to obtain information about $x$ by asking player $A$ questions as follows: each question consists of $B$ specifying an arbitrary set $S$ of positive integers (possibly one specified in some previuos question), and asking $A$ whether $x$ belongs to $S$. Player $B$ may ask as many questions as he wishes. After each question, player $A$ must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any $k+1$ consecutive answers, at least one answer must be truthful.

After B has asked as many questions as he wants, he must specify a set $X$ of at most $n$ positive integers. If $x$ belongs to $X$, then $B$ wins; otherwise, he loses. Prove that:

1. If $n \ge 2^k,$ then $B$ can guarantee a win.
2. For all sufficiently large $k$, there exists an integer $n \ge 1.99^k$ such that $B$ cannot guarantee a win.



Bài toán: Trò chơi đoán kẻ nói dối là một trò chơi giữa hai người chơi $A$ và $B$. Quy tắc của trò chơi phụ thuộc vào hai số nguyên dương $k$ và $n$ mà cả hai người chơi đều đã biết trước.

Bắt đầu trò chơi, $A$ sẽ chọn các số nguyên $x$ và $N$ với $1 \le x \le N$. $A$ giữ bí mật số $x$ và nói số $N$ cho $B$. $B$ sẽ cố thu nhận thông tin về số $x$ bằng cách hỏi $A$ các câu hỏi như sau : mỗi câu hỏi bao gồm việc $B$ xác định một tập $S$ tùy ý các số nguyên dương (có thể là một tập đã được nhắc đến trong câu hỏi trước đó) và hỏi $A$ xem $x$ có thuộc $S$ hay không. Sau mỗi câu hỏi, $A$ phải trả lời có hoặc không, nhưng có thể nói dối bao nhiêu lần tùy thích, chỉ có điều là phải trả lời đúng ít nhất một trong số $k+1$ câu hỏi liên tiếp.

Sau khi $B$ đã hỏi xong, $B$ phải chỉ ra một tập $X$ có tối đa $n$ số nguyên dương. Nếu $x \in X$, $B$ thắng; nếu ngược lại, $B$ thua. Chứng minh rằng :

1. Nếu $n \ge 2^k$, $B$ có thể đảm bảo một chiến 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ể đảm bảo có một chiến thắng.

[perfectstrong]

a) Em suy nghĩ thế này có đúng không? Ý tưởng của em là thuật toán nhị phân.
Để dễ hình dung, ta đặt $f(x;y)$ là đoạn chứa các số tự nhiên từ $x$ đến $y$.
Đầu tiên, $B$ sẽ hỏi $A$ rằng $x$ có thuộc trong $f\left( {1;\left\lfloor {\frac{N}{2}} \right\rfloor } \right)$ không?
Nếu $A$ nói có thì $B$ sẽ hỏi tiếp đối với $f\left( {1;\left\lfloor {\frac{1}{2}\left\lfloor {\frac{N}{2}} \right\rfloor } \right\rfloor } \right)$.
Nếu $A$ nói không thì $B$ sẽ hỏi đối với đoạn $f\left( {\left\lfloor {\frac{1}{2}\left\lfloor {\frac{N}{2}} \right\rfloor } \right\rfloor + 1;\left\lfloor {\frac{n}{2}} \right\rfloor } \right)$
Cứ như vậy, tổng quát cách hỏi sẽ là: Nếu ở lần thứ $t$ hỏi về đoạn $f(x;y)$ thì lần thứ $t+1$ sẽ hỏi về đoạn $f\left( {x;\left\lfloor {\frac{{x + y}}{2}} \right\rfloor } \right)$. Nếu $A$ trả lời có thì ta tiếp tục các câu hỏi như trên, nếu $A$ trả lời không thì ta hỏi về đoạn $f\left( {\left\lfloor {\frac{{x + y}}{2}} \right\rfloor + 1;y} \right)$ rồi lặp lại thao tác trên.
Điều kiện dừng lại của các lượt câu hỏi này là $x=y$. Khi đó, ta nhận được 1 phần tử là $x_i$.
Cái khó là, em nghĩ làm sao để biết chắc rằng nó nằm ở đoạn nào? Có thể hỏi 1 câu liên tiếp $k+1$ lần chăng

[Karl Heinrich Marx]

a) Em suy nghĩ thế này có đúng không? Ý tưởng của em là thuật toán nhị phân.
Để dễ hình dung, ta đặt $f(x;y)$ là đoạn chứa các số tự nhiên từ $x$ đến $y$.
Đầu tiên, $B$ sẽ hỏi $A$ rằng $x$ có thuộc trong $f\left( {1;\left\lfloor {\frac{N}{2}} \right\rfloor } \right)$ không?
Nếu $A$ nói có thì $B$ sẽ hỏi tiếp đối với $f\left( {1;\left\lfloor {\frac{1}{2}\left\lfloor {\frac{N}{2}} \right\rfloor } \right\rfloor } \right)$.
Nếu $A$ nói không thì $B$ sẽ hỏi đối với đoạn $f\left( {\left\lfloor {\frac{1}{2}\left\lfloor {\frac{N}{2}} \right\rfloor } \right\rfloor + 1;\left\lfloor {\frac{n}{2}} \right\rfloor } \right)$
Cứ như vậy, tổng quát cách hỏi sẽ là: Nếu ở lần thứ $t$ hỏi về đoạn $f(x;y)$ thì lần thứ $t+1$ sẽ hỏi về đoạn $f\left( {x;\left\lfloor {\frac{{x + y}}{2}} \right\rfloor } \right)$. Nếu $A$ trả lời có thì ta tiếp tục các câu hỏi như trên, nếu $A$ trả lời không thì ta hỏi về đoạn $f\left( {\left\lfloor {\frac{{x + y}}{2}} \right\rfloor + 1;y} \right)$ rồi lặp lại thao tác trên.
Điều kiện dừng lại của các lượt câu hỏi này là $x=y$. Khi đó, ta nhận được 1 phần tử là $x_i$.
Cái khó là, em nghĩ làm sao để biết chắc rằng nó nằm ở đoạn nào? Có thể hỏi 1 câu liên tiếp $k+1$ lần chăng

Có thể hỏi 1 câu bao nhiêu lần cũng đc nhưng lập luận của em sai rồi, câu trả lời đâu hẳn đã chính xác, e hỏi 1 câu k+1 lần cũng không thể bik đc đáp án đúng của câu đó. Bên MS có 1 lời giải của anh Hiếu ý tưởng sử dụng đơn biến nhưng thực tế lời giải đó k mường tượng được tại sao con số $2^k$ là bé nhất, cần một lời giải thể hiện được 1 thuật toán chỉ ra con số $2^k$ mới giải quyết được câu b.

[perfectstrong]

Thì em thấy nếu theo cái cách có thể hơi giống em, thì sẽ thấy $2^k$ là số nhỏ nhất. Vì cứ sau mỗi lần hỏi, đoạn con đó sẽ nhỏ đi 2 lần.
$n \ge 2^k$ thì số câu hỏi sẽ ít là $k+1$ lần.
Giờ ta chưa tính tới việc nó có đúng hết không, nhưng với $k+1$ lần liên tiếp, sẽ có ít nhất 1 lần đúng.
Cách này cũng phần nào mường tượng ra con số $2^k$

[Karl Heinrich Marx]

Em thử hình dung nhá, nếu e hỏi họ 1 câu k+1 lần mà họ trả lời có không xem kẽ nhau thì đâu xác định được câu trả lời chính xác là có hay không. Người ta cho e hỏi vô số lần đều được nhưng e đâu có bik là họ trả lời đúng đâu mà thu hẹp đoạn đi 2 lần. Lời giải của e chỉ đúng khi mà bạn A luôn trả lời sự thật mà nếu thế thì chẳng cần đến $2^k$ mà như thuật tin học em có thể chỉ ra luôn được số đó sau vô số lần hỏi. Ý anh một lời giải tìm ra $2^k$ nhỏ nhất thì lời giải đó phải cho thấy trò chơi "kịch tính" nhất khi nào :-j giả sử $B$ đưa ra 1 tập bé hơn $2^k-1$ phần tử thì trường hợp duy nhất nào làm cho B phải thua. Có thể có những lời giải khác đáp ứng đc bài toán nhưng mình muốn xem 1 lời giải thật sự thể hiện bản chất trò chơi diễn ra như thế nào là tối ưu cho cả 2 bên chứ còn bản thân thì chả đủ trí tưởng tượng mà mường tượng ra 2 cậu đấy chơi với nhau thế nào cho mà kịch tính nhất )

[khanh3570883]

Hương giải phần 2, bác nào dịch hộ, em ngại dịch lắm!

Here's an outline of part 2:

Rephrase the problem as "A must make a series of answers so that for every sequence of k+1 consecutive questions, there is no number for which all the answers are false. If this is the case, then at least one of the questions must be true for x and B will learn no information from the possible lies.

Now have A act completely randomly. Show that the probability that fixed k+1 consecutive questions are all lies is at most n divided by 2^k, no matter the questions or answers before those questions.

This now will let you use a version of the Lovasz Local Lemma. It´s different from the usual version in that it's directional and you need to be a bit more careful, but the proof still works.
'
Lovasz Local Lemma will give you arbitrarily long finite sequences of responses. Now, assume B has a deterministic strategy. Finally, do a compactness argument with Tychonoff on {0,1}^n to turn it into an infinite sequence.

This is a sketch for b); as far as I've seen somebody had posted a solution for a), though I did not read it carefully.

What we want to do is to write some $N$ so that no proper subset of $\{1,2,\ldots,N\}$ would be winning under a certain strategy of the liar.

We say that a number $1\leq x\leq N$ requires an answer in $\leq p$ turns at some moment if the previous $k-p+1$ answers are false under assumptions that $x$ is the secret number. And we say that $x$ requires an answer in exactly $p$ turns if it requires an answer in $\leq p$ turns, but not in $\leq p-1$.

At every moment $t$ we count a weighted sum $P(t)$ in the following way: every number that requires an answer in $k+1-i$ turns brings to $P(t)$ a summand $\frac{1.995^i}{N}$.

Suppose we (the liar) are given a new set $S$ to give the immediate answer. Which one will we give? Indeed, if $S$ carries more than a half of $P(t)$ then we say 'yes', otherwise 'no'. Following the strategy, one can easily check that $P(t+1) \leq \frac{1.995}{2}\cdot P(t) + 1$. Then, by induction, $P(t)<400$.

Assume that at some moment our opponent could guarantee that $x$ is not a secret number. Let $t$ be the first such moment. Then $x$ brings $\frac{1.995^{k+1}}{N}$ to $P(t)$. It is impossible if $N<\frac{1.995^{k+1}}{400}$, which is exactly what we wanted for large $k$.

Nguồn: mathlinks