Suppose that there are 16 people standing in a straight line in a room. Each person is either a truth teller (always tell the truth) or a naysayer (always answer NO). You are in a different room, and your task is to determine the positions of all the truth teller in this line. You can not see the 16 people, as they are in the other room.

You are allowed to take 'turn' to determine their persona. During each turn, you can address 1 single YES/NO question to ALL 16 people. The question will be relayed to the 16 people, and the total number of YES will be relayed back to you. Assume that number of YES relayed back to you at the end of each turn is reliable. As usual, you are not allowed to ask questions that are impossible for the truth tellers to answer accurately with YES/NO (asking paradoxes, etc.) .

Show that it is possible to correctly identify all the truth tellers and the naysayers within 6 questions.

## Question

## bushindo 14

Suppose that there are 16 people standing in a straight line in a room. Each person is either a truth teller (always tell the truth) or a naysayer (always answer NO). You are in a different room, and your task is to determine the positions of all the truth teller in this line. You can not see the 16 people, as they are in the other room.

You are allowed to take 'turn' to determine their persona. During each turn, you can address 1 single YES/NO question to ALL 16 people. The question will be relayed to the 16 people, and the total number of YES will be relayed back to you. Assume that number of YES relayed back to you at the end of each turn is reliable. As usual, you are not allowed to ask questions that are impossible for the truth tellers to answer accurately with YES/NO (asking paradoxes, etc.) .

Show that it is possible to correctly identify all the truth tellers and the naysayers within 6 questions.

Edited by bushindo## Link to post

## Share on other sites

## 20 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.