Bài 3

Trong trò chơi đoán có nói dối, A chọn số nguyên

x

với

1\le x\le N

và cho B biết

N

. B hỏi các câu dạng “

x

có thuộc tập

D

không?”, trong đó

D

là tập số nguyên dương tùy ý. A có thể trả lời thật hoặc dối ở mỗi câu, nhưng trong mọi

k+1

câu liên tiếp phải có ít nhất một câu trả lời thật. Sau hữu hạn câu hỏi, B nêu một tập

X

gồm nhiều nhất

n

số nguyên dương và thắng nếu

x\in X

. Chứng minh (a) nếu

n\ge2^k

thì B có thể bảo đảm thắng; (b) với mọi

k

đủ lớn, có một

n\ge1.99^k

khiến mọi chiến lược đều thất bại.

Bước 1 trên 3: Diễn giải câu trả lời thành các tập ứng viên

Bước trước Bước tiếp

Hiểu nôm na

Câu trả lời thật nói rằng x thuộc tập đã chọn, còn câu nói dối nói rằng x thuộc phần bù; vì vậy mọi khối k+1 câu trả lời đều phải phủ lên x thật.

P_j\in\{D_j,D_j^c\},\qquad x\in P_j\cup\cdots\cup P_{j+k}

Phân tích chi tiết

Với câu hỏi thứ j, gọi $D_j$ là tập B đưa ra và gọi $P_j$ là $D_j$ nếu A trả lời có, hoặc $D_j^c$ nếu A trả lời không. Trong mọi $k+1$ câu liên tiếp có một câu thật, nên số x chưa biết thuộc $P_j\cup\cdots\cup P_{j+k}$ với mọi j.