Thread: Liar/Truth Question

Suppose there is a mixture of 100 professors at a university. Among the professors we have professors that are honest and dishonest professors; that is, the honest ones always tell the truth whereas the dishonest ones always lie. You're able to ask any of the professors questions about other professors: "Professor A, is Professor B honest?" and then professor A will respond either yes or no. How do I come up with a simple algorithm that would determine which of the 100 professors at the university are honest (in at most 198 questions). It's assumed that there are less dishonest professors than there are honest ones.

I vaguely remember how to do this in Discrete Math with truth tables; this is for a Bioinformatics class

ask each of the professors "what is 2+2"

There's some algorithm that says it can be done in 198 questions or less, I believe. That's where that comes from. I think it's def. more complicated than asking them 1 question, which I don't see how that will determine which are telling the truth and which aren't. And how do we know that they are (or not)?

Originally Posted by fifthrapiers

There's some algorithm that says it can be done in 198 questions or less, I believe. That's where that comes from. I think it's def. more complicated than asking them 1 question, which I don't see how that will determine which are telling the truth and which aren't. And how do we know that they are (or not)?

the problem is that there are too little constraints. 198 problems for 100 professors can mean you can do anything you want practically. With the question "2+2=?" just ask all the professors (only 100 questions) and see which answer 4.

Maybe you are forgetting a constraint?

You're right, and I think this problem would be too easy for a 300 level college course .

"You're able to ask any of the professors questions about other professors: "Professor A, is Professor B honest?" and then professor A will respond [with] either yes or no. How do I come up with a simple algorithm that would determine which of the 100 professors at the university are honest (in at most 198 questions). It's assumed that there are less dishonest professors than there are honest ones."

I'm assuming the last sentence has some relevant, although it may not be apparent (to me any way). So you can't ask the 2+2 question...you can only ask the other professors if they're honest or not, in which case the other one will either respond, "yes," or "no".

*EDIT* Looked over prob and I didn't leave anything out, as you suggested I might have. Thanks for your help, Quick.

Originally Posted by fifthrapiers

"You're able to ask any of the professors questions about other professors

I can't believe I skipped over that

I did some research online, and found this site:

http://www.cs.usu.edu/~mjiang/cs5050...6/20060118.pdf

It's exactly the same, but the wording is a bit different. Except, in this one, instead of professors ALWAYS telling the truth or ALWAYS lying, they have professors ALWAYS tell the truth, but they may SOMETIMES tell the truth and may SOMETIMES lie. But I can't even understand the sometimes with their solution. Since mine is always, I would think this should be much easier.

The explanation given is too hard for me to follow. My professor said she did it using a graph, but said she can see 2 ways to solve this. Apparently the problem is much easier with both of them being always.