Optimal Algorithm [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

I have got following problem. On a given mountain a girl is stuck and there are two paths. One path will take her to the rescuer (left turn) and the second one (right turn) will take her to a jungle from where there is no chance to come back. Now she meets a group of people say n who always speak the truth and some people say m may / may not speak the truth. We are given that n is greater than m. So the girl can ask to a random person - which way are the rescuers, the problem is that she doesn't know which one is she asking to (n or m). I want to know if there is a Big Theta (n + m) algorithm to find how many people are telling the truth? or strictly speaking the value of n?

I am able to solve a simpler version of this by myself. Say there only two people, 1 always speaks the truth and other one always lies. She can ask a question for which both of them will give the same answer. For example: to the truth speaker she can ask - "Hey according to the other guy, which way takes to rescuer?". The truth speaker will say - right turn (because the other guy lies). Now she can ask the same question to the liar - he will respond by saying - right turn as well (because the true answer is left turn but since he always lies, he will say right). Now she can walk away to the left knowing it is right answer.

The problem is that in the first case - second set of people may / may not lie. But I think the key is that n > m i.e. number of people who always speak the truth are greater than number of people who may/may not speak the truth. So looks like this will cancel out something.

Any help will be appreciated. Thanks.

Answer 1

Just ask any one of them the following question:

If you were the opposite to what you are going to be when you answer this question, which would be the right way to go?

If he's the indecisive type in lying mode, he'll have to tell you to go the wrong way because, as a truth teller he'd have to tell you the right way but, since he's lying, he won't.

If he's the truth-teller (or an indecisive type in truth mode), he'll have to tell you to go the wrong way because, as a liar, that's what he'd say.

Then just go the other way. No algorithm required, just an O(1) calculation.

Made CW since it's not really a programming related question.

Answer 2

Ask everyone where the direction of rescuer is. Since n > m, the direction that is cited more number of times is the actual direction.