Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -


  • Please log in to reply
8 replies to this topic

#1 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 22 November 2010 - 06:58 PM

Suppose that you encounter 6 people, each of whom is either a truth teller (always tells the truth), a liar (always tell lies), or a random answerer (always answer randomly with 'Yes' or 'No'). You know that in this group of 6, there are 3 random answerers, 1 truth teller, and 2 liars, but you don't know which person is which. The puzzle is to identify the 3 random answerers with the following information:

1) You can only ask yes/no questions to 1 person at a time
2) You can ask the same question of different people, or address different questions to the same person.
3) Everytime you ask a question, your question count increases by 1
4) Each person in the group of 6 knows what type of people the remaining 5 are.

So, determine a strategy that is guaranteed to identify the 3 random answerers. Bonus: what is the maximum number of questions required to guarantee correct identification?

Edited by bushindo, 22 November 2010 - 07:00 PM.

  • 0

#2 tamjap

tamjap

    Junior Member

  • Members
  • PipPip
  • 38 posts

Posted 22 November 2010 - 08:40 PM

Hypothetically, if a question is asked of the truth teller with an answer he cannot possibly determine accurately (e.g. "If asking a yes or no question of a random answerer, will his/her answer be correct"), does the truth teller's head explode?
  • 0

#3 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 22 November 2010 - 10:16 PM

Hypothetically, if a question is asked of the truth teller with an answer he cannot possibly determine accurately (e.g. "If asking a yes or no question of a random answerer, will his/her answer be correct"), does the truth teller's head explode?


Yes, if that happens, the truth teller's head will explode. Actually, more seriously, I just realized that I made a mistake in constructing this puzzle. Turns out in the worst case I can narrow the 6C3 = 20 possible configurations down to 2, but no further. Therefore a solution is not possible, at least not for me. If a mod can delete this topic, I'd appreciate it very much. Sorry to those who spent time thinking about the problem as it was posted.
  • 0

#4 araver

araver

    Senior Member

  • Members
  • PipPipPipPip
  • 1555 posts
  • Gender:Male

Posted 23 November 2010 - 08:22 AM

Yes, if that happens, the truth teller's head will explode. Actually, more seriously, I just realized that I made a mistake in constructing this puzzle. Turns out in the worst case I can narrow the 6C3 = 20 possible configurations down to 2, but no further. Therefore a solution is not possible, at least not for me. If a mod can delete this topic, I'd appreciate it very much. Sorry to those who spent time thinking about the problem as it was posted.



Allowing for non-answers (head exploding)
Spoiler for


Seriously now
Spoiler for


Still not sure we need to delete this as we do not have a formal proof that it's impossible.

I propose we leave it as an open question for now or as "Bushindo's 3-Randoms-Hiding-Successfully Conjecture" :D

Edited by araver, 23 November 2010 - 08:25 AM.

  • 0

Summer of 2013:
Show the Mafia world you're back in action ... signup for The Coup of Rhotus Mafia.You know you want it, we know you still have it in you so .... Come join the madness!  :thumbsup: 
 
Puzzles open: Strange Creatures I Past puzzles: Mystery Operation Series: I, II, III, IV; Contamination Scenario;
Past games: Crack the Code Series: III, VII, IXPast mafia games: UN Mafia, UN Mafia II, Star Trek Mafia, TMM IV

Almost random quotes:
>> Not only is the universe stranger than we imagine, it is stranger than we can imagine.


#5 araver

araver

    Senior Member

  • Members
  • PipPipPipPip
  • 1555 posts
  • Gender:Male

Posted 23 November 2010 - 09:28 AM

Actually, after thinking a little more ... I almost had a proof but it had a hidden fallacy in it. Just putting it here maybe it inspires an actual proof.

Spoiler for


OFF-TOPIC I admit I still enjoy this puzzle as I'm a twisted-version of a researcher :D
I enjoy mostly proving that something is either not possible or undecidable B))

Edited by araver, 23 November 2010 - 09:29 AM.

  • 0

Summer of 2013:
Show the Mafia world you're back in action ... signup for The Coup of Rhotus Mafia.You know you want it, we know you still have it in you so .... Come join the madness!  :thumbsup: 
 
Puzzles open: Strange Creatures I Past puzzles: Mystery Operation Series: I, II, III, IV; Contamination Scenario;
Past games: Crack the Code Series: III, VII, IXPast mafia games: UN Mafia, UN Mafia II, Star Trek Mafia, TMM IV

Almost random quotes:
>> Not only is the universe stranger than we imagine, it is stranger than we can imagine.


#6 araver

araver

    Senior Member

  • Members
  • PipPipPipPip
  • 1555 posts
  • Gender:Male

Posted 23 November 2010 - 11:20 AM

And since I started ranting, let me continue with
Spoiler for

Edited by araver, 23 November 2010 - 11:23 AM.

  • 0

Summer of 2013:
Show the Mafia world you're back in action ... signup for The Coup of Rhotus Mafia.You know you want it, we know you still have it in you so .... Come join the madness!  :thumbsup: 
 
Puzzles open: Strange Creatures I Past puzzles: Mystery Operation Series: I, II, III, IV; Contamination Scenario;
Past games: Crack the Code Series: III, VII, IXPast mafia games: UN Mafia, UN Mafia II, Star Trek Mafia, TMM IV

Almost random quotes:
>> Not only is the universe stranger than we imagine, it is stranger than we can imagine.


#7 Lemeshianos

Lemeshianos

    Junior Member

  • Members
  • PipPip
  • 22 posts

Posted 23 November 2010 - 05:04 PM

I am just going to go for the Bonus question.
Since you are asking for the maximum and not the minimum, then my answer would be "Infinite number of questions"! (or just a number higher than the number anyone comes up with)
  • 0

#8 wolfgang

wolfgang

    Senior Member

  • Members
  • PipPipPipPip
  • 754 posts
  • Gender:Male

Posted 23 November 2010 - 07:36 PM

Hi...did anyone think about deviding the 6 people into two groups of 3?
In this case we will have only three possiblities:-
1- RRR......TLL
2- RRL......TLR
3- RLL......TRR
This method may help to find a possible solution,and minimize number of questions..
  • 0

#9 bushindo

bushindo

    Senior Member

  • VIP
  • PipPipPipPip
  • 721 posts
  • Gender:Male
  • Location:Los Angeles, CA

Posted 23 November 2010 - 08:12 PM

And since I started ranting, let me continue with

Spoiler for


Good work, araver. You made some valuable contribution from an otherwise flawed puzzle. I'm glad you enjoyed it. I sure enjoy reading your proof.

Hi...did anyone think about deviding the 6 people into two groups of 3?
In this case we will have only three possiblities:-
1- RRR......TLL
2- RRL......TLR
3- RLL......TRR
This method may help to find a possible solution,and minimize number of questions..


This is a good start, but it is virtually impossible to distinguish between mirror pairs. Suppose we narrow the problem to either possibility 2 or 3 in your example, it is virtually impossible to determine which is the correct one from there.

Edited by bushindo, 23 November 2010 - 08:13 PM.

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users