Đến nội dung


Chú ý

Nút $f_x$ để gõ $\LaTeX$ hoạt động không được ổn định trong thời gian này. Tạm thời các bạn có thể vào trang này để gõ rồi copy vào bài viết. Mong các bạn thông cảm.


Hình ảnh

[IMO 2012 - P.3] Chứng minh: Nếu $n \ge {2^k}$ thì $B$ có thể chiến thắng


  • Please log in to reply
Chủ đề này có 5 trả lời

#1 Crystal

Crystal

    ANGRY BIRDS

  • Hiệp sỹ
  • 5529 Bài viết
  • Giới tính:Nam
  • Đến từ:Huế

Đã gửi 11-07-2012 - 00:55

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.

#2 perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Hiệp sỹ
  • 3612 Bài viết
  • Giới tính:Nam
  • Đến từ:ĐN
  • Sở thích:Đàn guitar, ngắm người mình yêu, học toán

Đã gửi 11-07-2012 - 12:15

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 :D
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D

$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$




I'm still there everywhere.

#3 Karl Heinrich Marx

Karl Heinrich Marx

    Thượng sĩ

  • Thành viên
  • 291 Bài viết
  • Giới tính:Nam

Đã gửi 11-07-2012 - 13:12

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 :D

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.

#4 perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Hiệp sỹ
  • 3612 Bài viết
  • Giới tính:Nam
  • Đến từ:ĐN
  • Sở thích:Đàn guitar, ngắm người mình yêu, học toán

Đã gửi 11-07-2012 - 13:34

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$ :)
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D

$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$




I'm still there everywhere.

#5 Karl Heinrich Marx

Karl Heinrich Marx

    Thượng sĩ

  • Thành viên
  • 291 Bài viết
  • Giới tính:Nam

Đã gửi 11-07-2012 - 14:24

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 :))

#6 khanh3570883

khanh3570883

    Trung úy

  • Thành viên
  • 900 Bài viết
  • Giới tính:Nam
  • Đến từ:Địa ngục

Đã gửi 12-07-2012 - 10:35

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

THẬT THÀ THẲNG THẮN THƯỜNG THUA THIỆT

LƯƠN LẸO LUỒN LỎI LẠI LEO LÊN

 

Một ngày nào đó ta sẽ trở lại và lợi hại hơn xưa





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh