11
$\begingroup$

You are in a chatroom with three Stack Exchange users. They are a Spambot, a Trusted User, and a Moderator, but you don't know who is who; the chatroom only displays their names (user314, user2718, and user1618), not their reputations. You need to discern their identities, and are only allowed to ask them yes/no questions, with each question being directed at a single user.

Each user has a different degree of helpfulness...

  1. The Spambot is very unhelpful, and answers yes or no randomly.
  2. The Trusted User quite helpful, but occasionally makes mistakes. At most one of the answers this user gives will be incorrect.
  3. The Moderator is perfectly helpful, and will always answer correctly.

The only thing these three users know is each others identities. If you ask them a question they don't know the answer to, you will be banned from the chatroom for being off-topic. Also, self-referential questions (such as, "Will your answer to this question be no?") are strictly against the chatroom's Paradox Prevention Policy.

Determine the users' identities by asking at most six questions.

I don't know if six is optimal. I will accept the first correct answer, but if someone comes along later with a solution with fewer questions, I'll accept theirs instead.

I did not invent this puzzle, I got it from a different puzzle forum. The puzzle at the top of the linked discussion thread is different then the one here, you have to dig down to find the variant I used.

$\endgroup$
  • 1
    $\begingroup$ Presumably not particularly relevant, but I notice that the users' anonymous numbers are pi, e, and phi to the first few digits each. $\endgroup$ – Glen O May 27 '15 at 5:27
  • 7
    $\begingroup$ This is correct. I am infallible. $\endgroup$ – Aza May 27 '15 at 5:38
  • 1
    $\begingroup$ do you ask them all simultaneously(=6 questions per user) or one-by-one(=6 questions in total)? $\endgroup$ – Novarg May 27 '15 at 6:10
  • $\begingroup$ @Novarg good question, you ask one by one. Asking everyone to answer the same question counts as three questions. $\endgroup$ – Mike Earnest May 27 '15 at 6:16
  • 1
    $\begingroup$ Moderators' names are shown in blue, FWIW. :D $\endgroup$ – Scimonster May 27 '15 at 14:09
3
$\begingroup$

For convenience I've renamed your users A, B and C.

(Q1 & Q2) Ask A, "Is B the spambot?" twice in succession.

Case 1: Two yeses

If you get two yeses, that means either A is the spambot (and the others could be anything), A is the moderator and B is the spambot, or A is the trusted user and B is the spambot (since trusted user will only make a mistake once).

In all three cases, C is not the spambot.

Now (Q3) ask C if A is the moderator.

Case 1a

If you get a yes, C can't be the moderator (moderator won't tell you someone else is the moderator). Since we already know C isn't the spambot, C must be the trusted user, but we don't know whether they've used their mistake or not.

Repeat the question (Q4). If it's yes again, A must be the moderator, C the trusted user (with no mistakes - o ye of little faith) and B the spambot.

If Q4 was no the second time, you have to ask again (Q5). If you get a yes (that's YNY for Q3-Q5), A must be the mod and B the spambot. If you get a no (that's YNN for Q3-Q5) then A must be the spambot and B the moderator.

Case 1b

If C said that no, A was not the moderator, then you have one of the three cases:
- C is moderator, A is trusted user, B is spambot
- C is moderator, A is spambot, B is trusted user
- C is trusted user (mistake in Q3), A is mod, B is spambot

Ask C the same question (Q4) to rule out the third case. If C is the trusted user, they will have used up their mistake so will say yes the second time, which proves A is mod and B is spambot.

Therefore if C says no again, you know you have one of the first two cases and C is the moderator. The moderator will tell you the truth so just ask (Q5) C who's who (e.g. "is A the spambot?") and you're done.

Case 2: Two nos

This is symmetrical to Case 1 with B and C the other way around; I've omitted it for brevity and to reduce the chance of me making a transcribing error.

Case 3: One yes, one no (order doesn't matter)

A can't be the moderator, since they've given conflicting answers. A is either the spambot or the trusted user. If they're the trusted user, they've used up their mistake and will now tell the truth (this is important).

Now ask (Q3) ask B if C is the moderator.

Case 3a: B says yes

B can't be the moderator if they tell you someone else is. We already deduced that A wasn't the moderator, so C must be the moderator. Therefore C will tell you the truth, so ask C (Q4) who's who out of the other two and you're done.

Case 3b: B says no

In this case we have one of the following cases:
- B mod, A spambot, C trusted user
- B mod, C spambot, A trusted user
- B spambot, C mod, A trusted user (because A is not mod)
- B trusted user, C mod, A spambot

In the latter three cases, note that the trusted user has made a mistake already and won't make any further mistakes.

Now ask B (Q4) if A is the spambot. Remember that B is either the spambot himself or truthful.

Case 3bi

B says no. Since we know that B is either the spambot himself or truthful, A cannot be the spambot. We already ruled out A being the moderator in Q1-2, so A must be the trusted user. What's more, A used up their mistake in Q1 or Q2, so A must now be truthful. So we can ask (Q5) A who the other two are (e.g. "is C the spambot?") and we're done.

Case 3bii

B says yes. We know that B is either the spambot himself or truthful, so either A or B is the spambot. We also know A is not mod. Therefore we have one of:
- A spambot, B mod, C trusted
- A spambot, B trusted, C mod
- B spambot, A trusted, C mod

Sadly, we haven't asked C any questions yet in this scenario so we can't guarantee truthfulness (they could still be a trusted user making an error).

So next (Q5) we ask C, "Is A the trusted user?"

Case 3bii-a: If we get a yes, either C is the moderator and A the trusted user, or C is the trusted user (option 1 from list in 3bii) and has now used up their mistake. Either way, C will now tell the truth, so we can use our final question (Q6) to ask "Are you the moderator?" to narrow it down between (C mod/A trusted/B spam) and (C trusted/A spam/B mod).

Case 3bii-b: If we got a no from C to "Is A the trusted user?" we know we have either:
- C mod, A spambot, B trusted user (used mistake in Q3), or
- C trusted user (no mistakes), A spambot, B mod
Either way, B won't make a mistake, so we can use our final question (Q6) to ask B if he is the moderator, which will tell us which of those two options it is.

$\endgroup$
  • $\begingroup$ well done, you put a lot of work into this, and it is very clear :) $\endgroup$ – Mike Earnest May 27 '15 at 21:47
-1
$\begingroup$

Here's how I would go about doing it, although I would need a place to write notes down.

I would ask the same question six times: "Is user314 the Spambot?"
Then I would write down each user's response to the question after each time. Unless I have an extraordinary stroke of bad luck, the Spambot's answers will be randomly spread between Yes and No, the Trusted User will answer with five answers the same and one different, and the Moderator will answer the same every time.

For example:

user314: 4 yes, 2 no
user2178: 5 yes, 1 no
user1618: 6 yes
Therefore I can conclude that user314 is the Spambot (random answers and verified by the other two),
user2178 is the Trusted User (answered all but one with a yes; also verified by the Moderator answering the same way),
and user1618 is the Moderator (answered all as yes).

$\endgroup$
  • $\begingroup$ At most one of the answers this user gives will be incorrect. - what if trusted will answer all 6 correct? And spambot too? Answers shouldn't be based on luck. And see OP comment: Asking everyone to answer the same question counts as three questions. $\endgroup$ – Novarg May 27 '15 at 6:28
  • $\begingroup$ My mistake, jm13fire, the way I initially worded the question was incorrect, I meant a single question should be asked of only a single user, not all three. Still, solutions should work with certainty, not just high probability. $\endgroup$ – Mike Earnest May 27 '15 at 6:35
  • 1
    $\begingroup$ 1/32 times spambot will answer the question with identical answers. 3/16 times he will answer the question with 5 identical and 1 out. These are not tremendous odds. You can improve them, to 1/64 and 3/32, by asking a question you know the answer to, but it's still not requiring a tremendous amount of bad luck. Also if one questions asked to all participants counts as a single question I doubt 6 questions are needed. $\endgroup$ – Taemyr May 27 '15 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.