MathNet 2006 — Phần 02 Câu hỏi 38

Đặt $k \ge 1$ là một số nguyên. Trong một nhóm người $2k+1$, một số người rất chân thành (họ luôn nói sự thật) và số còn lại là người khó đoán (đôi khi họ nói thật và đôi khi họ nói dối). Được biết, những điều khó lường nhiều nhất là $k$. Một người nào đó ngoài nhóm phải xác định ai là người chân thành và ai là người khó đoán thông qua một chuỗi các bước. Ở mỗi bước, anh ấy chọn hai người $A$ và $B$ từ nhóm và hỏi $A$ $B$ có thành thật không?
Chứng minh rằng sau $3k$ các bước, người ngoài sẽ có thể phân loại $2k+1$ những người trong nhóm một cách chắc chắn.