Results 1 to 8 of 8

Math Help - Liar/Truth Question

  1. #1
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    ask each of the professors "what is 2+2"
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    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)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by fifthrapiers View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    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.
    Last edited by fifthrapiers; September 27th 2006 at 03:39 PM. Reason: Addition to reply.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by fifthrapiers View Post
    "You're able to ask any of the professors questions about other professors
    I can't believe I skipped over that
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Truth Table
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: July 21st 2010, 09:59 AM
  2. Truth Tables
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: November 8th 2009, 05:15 PM
  3. Identify liar/truthful
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 7th 2009, 01:26 AM
  4. Liar Paradox
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 22nd 2009, 09:10 PM
  5. Truth Table Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 3rd 2008, 11:30 AM

Search Tags


/mathhelpforum @mathhelpforum