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

[dungxibo123]

Có n người bị tình nghi một vụ ăn cắp tài khoản ngân hàng. Những người này chỉ là kỹ sư tin học hoặc nhà quản lý.

Tuy nhiên, hồ sơ của họ đều đã bị hủy và không ai biết ai là ai, do vậy cảnh sát cần thẩm vấn từng người.

Điều tra ban đầu cho thấy chắc chắn hung thủ là người quản lý.

Biết rằng các kỹ sư tin học luôn luôn nói thật còn các nhà quản lý thì không chắc như vậy. Và hơn nữa, n người này đều biết nghề nghiệp thật sự của nhau.

Cảnh sát cần đặt câu hỏi để xác định ai làm nghề gì và câu hỏi chỉ có thể ở dạng trả lời có hoặc không, đúng hoặc sai …

1. Nếu như số kỹ sư tin học nhiều hơn số nhà quản lý (trong n người), phải hỏi ít nhất bao nhiêu câu để tìm ra ít nhất một kỹ sư tin học?

2. Nếu số kỹ sư ít hơn số nhà quản lý, liệu có thể tìm ra hung thủ?

TS Trần Nam Dũng
ĐH Khoa học Tự nhiên, ĐH Quốc gia TP HCM

 

[No Moniker]

Có n người bị tình nghi một vụ ăn cắp tài khoản ngân hàng. Những người này chỉ là kỹ sư tin học hoặc nhà quản lý.

Tuy nhiên, hồ sơ của họ đều đã bị hủy và không ai biết ai là ai, do vậy cảnh sát cần thẩm vấn từng người.

Điều tra ban đầu cho thấy chắc chắn hung thủ là người quản lý.

Biết rằng các kỹ sư tin học luôn luôn nói thật còn các nhà quản lý thì không chắc như vậy. Và hơn nữa, n người này đều biết nghề nghiệp thật sự của nhau.

Cảnh sát cần đặt câu hỏi để xác định ai làm nghề gì và câu hỏi chỉ có thể ở dạng trả lời có hoặc không, đúng hoặc sai …

1. Nếu như số kỹ sư tin học nhiều hơn số nhà quản lý (trong n người), phải hỏi ít nhất bao nhiêu câu để tìm ra ít nhất một kỹ sư tin học?

2. Nếu số kỹ sư ít hơn số nhà quản lý, liệu có thể tìm ra hung thủ?

TS Trần Nam Dũng
ĐH Khoa học Tự nhiên, ĐH Quốc gia TP HCM

 

1. Mình nghĩ câu này là $n-k+1$ với $k$ là số kĩ sư. ( không biết đúng không nữa,  mình dùng quy nạp )

với $n-k$ câu hỏi : "Mày có phải kĩ sư không?'' và 1 câu hỏi còn lại là : ''Mày có làm chung việc với thằng X không?'' ( X là 1 thằng trả lời ''có'' trong số $n-k$ thằng đã hỏi, lấy X làm mốc)

Bài viết đã được chỉnh sửa nội dung bởi No Moniker: 25-07-2016 - 14:40

[dungxibo123]

caau

 

1. Mình nghĩ câu này là $n-k+1$ với $k$ là số kĩ sư. ( không biết đúng không nữa,  mình dùng quy nạp )

với $n-k$ câu hỏi : "Mày có phải kĩ sư không?'' và 1 câu hỏi còn lại là : ''Mày có làm chung việc với thằng X không?'' ( X là 1 thằng trả lời ''có'' trong số $n-k$ thằng đã hỏi, lấy X làm mố

mình cũng nghĩ vật khi mới đọc bài toán này từ Face của thầy đã thử cmt vào nhưng thầy vẫn chưa trả lời :v chịu

[JUV]

a/Giả sử có $k$ kĩ sư, $q$ nhà quản lí với $q<k$. Với mỗi người $A$ bất kì thì ta hỏi mọi người xem $A$ có phải kĩ sư không. Vì số kĩ sư nhiều hơn nhà quản lí nên số câu trả lời thật sẽ luôn nhiều hơn số lần nói dối. Vì vậy nếu $A$ là NQL thì sẽ có nhiều câu trả lời không, nếu là KS thì có nhiều câu trả lời có. Vì số kĩ sư nhiều hơn NQL nên chỉ cần khảo sát nhiều nhất $\left [ \frac{n+1}{2} \right ]$ người là sẽ có $1$ KS. Vì vậy số câu hỏi sẽ là $n\left [ \frac{n+1}{2} \right ]$

b/ Giả sử $q>k$, các nhà quản lí sẽ thông đồng với nhau như sau:

- Mỗi người trong số họ sẽ nói tất cả các KS là NQL

- Mỗi người sẽ tự nhận mình là kĩ sư

- Họ sẽ phân chia câu trả lời cho mỗi người sao cho với mỗi NQL bất kì, sẽ có $k$ người bảo họ là KS còn $q$ người bảo họ là NQL. Sẽ có $k$ trong $q$ người đó có câu trả lời về mỗi người đôi một giống nhau, $q-k$ người còn lại trả lời bất kì 

Đương nhiên vì số NQL nhiều hơn KS nên hoàn toàn có thể phân chia được. Vì luôn có trường hợp $q-k$ người kia là NQL nên câu trả lời của họ không có giá trị. Nhưng ta cũng không thể xác định được trong $2k$ người còn lại, nhóm $k$ người nào là KS, nhóm nào là NQL theo tính chất đối xứng

Còn nếu $k=0$, các nhà quản lí chỉ cần tự nhận mình là KS còn mọi người khác là NQL thì điều tra sẽ bế tắc

Bài viết đã được chỉnh sửa nội dung bởi JUV: 30-07-2016 - 11:49