8
$\begingroup$

You are located outside of two rooms which have a door between them. Each room has one or more computers whose total power is unknown, so they cannot be reliably used as proof-of-work to compare times, however they are not strong enough to break cryptographic secrets. You cannot see who is in the rooms.

There are only two options:

  1. there are two different people in the rooms: in each room there is a different, honest person who stays in their room, or

  2. there is one dishonest person who pretends to be two different people, by moving between the rooms.

You and the person in each room can verbally communicate with each other only through a computer network. You can also send stuff back and forth between you and the rooms, e.g. cards, balls — in order to find out if these are two different people or one person who pretends to be two. However there is a random delay of up to one minute in all methods of communication due to limits of the communication infrastructure.

The people in the rooms can communicate with each other through you, assuming they are two different people.

However, you cannot do anything that would reveal the actual identity of a person, e.g. check their DNA, take their fingerprints, take their photo, collect a sample of their handwriting, ask to see their ID card, listen to their voice, etc.

What strategy would you devise in order to make the dishonest person reveal their pretension, if indeed there is only one person in the rooms?

P.S. It's always possible to send to each room a different secret number, and if a person can tell me both numbers, then they have proven that they have access to both rooms. However to achieve this, I will probably have to reward the dishonest person e.g. by paying them, or by threatening to punish honest people who cannot prove having access to both rooms. Which is exactly the opposite of what a good solution would achieve. A good solution would make a dishonest person expose their pretension without punishing (or punishing too severely) honest people.

$\endgroup$
  • 1
    $\begingroup$ Is there a reason why you call these person(s) honest or dishonest? I ask to make sure this is not another one liar and one truth-teller riddle. $\endgroup$ – Abbas Sep 3 at 11:20
  • $\begingroup$ @Abbas In each of the two cases, the occupants of the rooms would claim that they are two different people. In the 2nd case it would be a lie. $\endgroup$ – rapt Sep 3 at 11:29
  • $\begingroup$ same principle applies I think. $\endgroup$ – Abbas Sep 3 at 11:39
  • $\begingroup$ what about rot13(Jbhyq lbh fnl lrf vs V nfxrq lbh, ner gurer gjb crbcyr va gur ebbz?) $\endgroup$ – Abbas Sep 3 at 11:52
  • 1
    $\begingroup$ @Adam This tag covers several other concepts. The dishonest person in my question is a spy, if I understand the term correctly. They may lie if they think it would help hide their secret. $\endgroup$ – rapt Sep 3 at 12:09

12 Answers 12

9
$\begingroup$

How about

All you have to do is preoccupy both sides using a method which cannot be abused by the dishonest person. For example any of these will do:
1. Hand both sides a woodwind instrument and tell them both to use it at the same time.
2. Send them both a locked container which contains a code word which they can only unlock by keeping all of their limbs on the container for an extended amount of time.
3. Send a device to each side that contains a code word and will only open when a button on it is held for an extended amount of time. The devices are set so that they will (for example) explode if they come within a certain proximity of each other.
4. You can give both sides a bottle which can only be drained if drunk. They must drink from it and give it back. You can check for tampering or if the bottle wasn't drained after you are handed it back. One of the bottles contain water; the other contains strong sleeping medication. Simply speak to both rooms afterwards, it will be very straightforward to figure out!
5. Give a typical and unique construction task to both rooms and time them. If they take longer than the average person then you should start to suspect it is the same person.
6. Have both sides read a long (never been released) book in a short amount of time and then ask about specific details of the books. Maybe the books chosen are such that someone who reads both of them fast will confuse the details which is another technicality on top of just reading the content.
7. Give both rooms a large cipher to decrypt.

$\endgroup$
  • $\begingroup$ Your several variations of proof of work are interesting but possible to circumvent. Idea #4 (poison) is good, but it can be a sleep medication instead. How would you adjust it to my updated question, i.e. computer network communication, where people are not supposed to be knocked out? $\endgroup$ – rapt Sep 3 at 11:14
  • 2
    $\begingroup$ @rapt if I understand the scenario correctly, a delay in communication - with the communication through computer makes this question unsolvable without resorting to psychology. P.s. the methods I listed are all way more complicated to pull off in practice however I summarised them to be sufficient examples. $\endgroup$ – Adam Sep 3 at 11:33
  • $\begingroup$ @Adam the delay is only up to one minute, so most of your solutions are still fine. $\endgroup$ – Stop Harming Monica Sep 4 at 14:53
4
$\begingroup$

You could:

send one side a leaky propane tank and, after a little bit of messaging, send the other side a lit match. If it is the same person walking between both rooms, the gas will spread to the other side.

Or more humanely:

Send one side a strong smelling compound. Ask the other side to send back a sample of clothing. Use a trained dog to detect if the compound is on the clothing.

$\endgroup$
  • 2
    $\begingroup$ How would the first method show if there are two people or one? The person does not need to carry the thing around? $\endgroup$ – infinitezero Sep 4 at 11:44
  • 2
    $\begingroup$ The second solution works well. Send them a box rigged to spray the smelly compound when opened. Ask them to open it to see what's inside. Then ask the other room to send you the shirt they're wearing $\endgroup$ – Stephen R Sep 4 at 14:41
  • $\begingroup$ Clarification: Send one of them the smelly stuff. Ask the other one for their shirt. $\endgroup$ – Stephen R Sep 4 at 14:57
3
$\begingroup$

I may:

Preparing a rope with enough length, and put each end to each room. Then I'll also send each room a clock, and same note written "Pull the rope at XX:XX". If the rope could be pulled at same time, 2 individuals in separate room is proved. If only 1 end is pulled or nothing happened, maybe just 1 dishonest guy in the connected rooms.

Notes: This solution stands only when someone is impossible to stay in the middle door and could reach both rope ends with both hands, due to the distance between the entries to put/send stuffs is not mentioned.

Improved:

Maybe more simple.

Just send in same clocks and same notes written: "Show me your left(or right) hand(or foot) at XX:XX". If I could see same hands(or foots) at same time via the put/send stuff entries, then it's true that 2 individuals in separate rooms, else only 1 dishonest guy in connected rooms.

$\endgroup$
  • $\begingroup$ What if there is no way to communicate between me and the person other than sending notes/stuff back and forth, and there is some random delay due to the communication infrastructure (in other words, imagine we communicate through a computer network)? $\endgroup$ – rapt Sep 3 at 9:35
  • $\begingroup$ Hmm, that should be a totally different question compared to the original one. If that, something authentication concept in IT may help, like public/private key or digital signature, to identify whom is the real guy to contact or just someone pretended. $\endgroup$ – Conifers Sep 3 at 9:47
  • $\begingroup$ A dishonest person may get two different sets of keys. Your task is through a clever communication find out if they are one person or two. $\endgroup$ – rapt Sep 3 at 10:21
  • $\begingroup$ Then you might to have modify your question or ask a new one, due to all of the answers should works, through common sense, simple logical deduction or physic property. Anyway, time to think more deeper :D $\endgroup$ – Conifers Sep 3 at 10:30
  • $\begingroup$ I have updated the question. It's hard to keep it simple and accurate at the same time. I hope this time around I did not miss anything. $\endgroup$ – rapt Sep 3 at 10:54
3
$\begingroup$

This may be cruel yet very effective.

ask them to donate 1.5L of blood each. If it's a single person, they will have to donate 3L of blood, which will be fatal. Either person will confess to you, or you'll realise, once they stop responding.

$\endgroup$
  • $\begingroup$ This would identify the person. $\endgroup$ – Veedrac Sep 4 at 1:06
  • $\begingroup$ How would this identify the person? $\endgroup$ – infinitezero Sep 4 at 7:48
  • $\begingroup$ Eg. the DNA in the blood. $\endgroup$ – Veedrac Sep 4 at 18:01
  • $\begingroup$ "check their DNA", if I collect it, I don't check it. $\endgroup$ – infinitezero Sep 4 at 18:05
2
$\begingroup$

I claim that, under a stricter interpretation of the problem, the solution is

not possible.

Although the question is tagged I'm going to treat it as an problem, which means ignoring everything except the messages passed between rooms. I'll assume that the participants, either the two honest parties or the single malicious party, have bounded but unknown computational power, i.e. they are limited to solving polynomial-time problems and that we cannot use proof-of-work.

Under this model the question becomes, is it possible to distinguish between a single Turing machine from a pair of Turing machines? The answer is

no. Whatever programs run on the pair of Turing machines could be simulated by a single two-tape Turing machine, which can itself be simulated by an ordinary Turing machine with at most a quadratic slowdown.

This result is slightly stronger than needed, since we did not have to specify any restrictions on the messages being passed or the computations being run. The argument is also extendable to cover stronger computational models, like nondeterministic or probabilistic Turing machines, oracle machines, etc.

What all this means is that a real answer to the question as originally formulated will need to use

, like relying on the human nature of the participant(s)

$\endgroup$
1
$\begingroup$

I think the best way to come up with an answer to this question is to look at this backwards - instead of thinking of ways to reveal if there is one person or two, think of how you would try to keep your secret if you were the one in the rooms.

To start with, I would make sure that all my interactions were carefully recorded so that I wouldn't unintentionally use information I'd received from the wrong room. If the computer doesn't support reviewing messages received, I'd have a notepad in each room on which I'd write down all the information I was given while in that room. I'd also have a box in which to put any objects I'd been given, so that I wouldn't unintentionally give back an object to the wrong room. Being a well-trained spy, you can be certain that I would never slip up and reveal myself through information or objects received from the room that I wasn't currently in.

The random delay in communication certainly helps with this - I could consistently wait longer than necessary to reply to messages and to pick up or return objects. This would give me time to review whatever notes I needed in order to maintain the deception.

Now then, how would I uncover a spy like this? If I sent them anything to eat or drink, the spy would wisely say "I'm sorry, I'm not allowed to eat or drink anything that's been sent to me" and return the item to me. I could try to trip them up on the communications delay by sending them an item that can detect when it has been handled - after it has been returned to me I would be able to see when they first touched it, and when they last touched it, and check if it matches the communication delays that they have been claiming. However, if the spy maintains proper discipline and waits a while to even touch objects, this method still won't work.

I can only think of one way to guarantee that you can determine if there is one person or two (two if you're allowed to kill someone):

Determine what information the spy is trying to get, and send it to them encrypted with a nonce, and send that nonce to the other room. When a nonce is generated in a crytographically secure manner and only used once, it is a perfect form of encryption that cannot be broken by any amount of computational power. The only trick here is that you need to obtain some information that is important enough to the spy that they will be willing to reveal themself.

$\endgroup$
  • $\begingroup$ 1. "only used once" - you mean only once for encryption (not necessarily for decryption)? 2. the simplest info is such that would stop something that would make life too difficult for a person who claims to be honest (i.e. who claims to stay in only one room), e.g. some code to prevent shutting the power off in the room of each honest person; however that goes against the principle of not punishing honest people. In that case instead of fancy encryption, just send each room a number, if a person knows both #s, I won't shut their power off. Any way to get the truth without punishing good guys? $\endgroup$ – rapt Sep 3 at 21:46
  • $\begingroup$ If there are two people, nothing stops them communicating with each other. $\endgroup$ – Stop Harming Monica Sep 4 at 15:00
1
$\begingroup$

Here is another possible solution
First, a simple one, then one that could deal with a more suspicious person.

What we need:

For example 1: A two-component poison, that is not deadly when taking only one component.
There are several real-world examples of these, including deadly drug combinations, or components of an euthanasia cocktail.
For example 2: The same poison, and a healthy dose of bluff and some patience.

This is our plan (simple version):

Our test subjects will have to eat at some point.
-Put one part of the two-component poison in each of their meals, without informing them.
-If there is only one person, their will not survive the poison combination.

If we are dealing with a more suspicious individual:

The person (if only one), may not eat at all, or eat only the food in one room. Because they are afraid of being poisoned (which I guess is a reasonable fear).
We are now entering a longer process:
-When giving them their daily meal, put one component of the poison in the food in one room, and the other component in the other.
-Wait until they would have starved if they didn't eat anything. Not sure how long that would be, but if we had infinite time, I guess a year would be plenty.
-After waiting, tell the persons that you have been putting a poison in the food for one of the persons that would slowly deteriorate them, killing them eventually.
-If there are 2 persons, they would be terrified (sorry), but safe.
-If there is only one person, they will have no choice but to start eating the food from both rooms, thinking they will be safe. That will in fact kill them quickly.

Some side notes:

If we use a deadly cocktail of narcotics, taking only one of the two component will have a clear effect (tripping, feeling nauseous, paranoia). That could be convincing them that they are actually being poisoned, hence convincing them to take the food in the other room.

Could the person just take the food in one room, and hope that it is the antidote?
That would be very illogical to do:
They are led to believe that one is poison and the other antidote. So, If they take only 1, they have either a 100% or 0% of survival. Taking the food in the other room will give them a 100% chance of survival. So regardless of which food they take first, it is always a good option to take the other food. (Or so they think...)

If we would have told the persons after a year that the poison would kill them quickly, they wouldn't believe us, because then they would already be dead.

Limitation:

If the person in the room has the same knowledge as us - and therefore not believe us - this is no solution. In that case, they would know that we are trying to give them a 2-component cocktail. They will just keep eating the food from one room.

$\endgroup$
1
$\begingroup$

Since I can't yet comment ("reputation" issues) I'm posting this as an answer, and would just like to point out that all "Ask the two rooms to perform a one-shot action on the same time" solutions (and by "one-shot" I mean it's not continuous work, you click a button, for example, and are done, as opposed, say, to typing in the entire text of "Hamlet" in one sitting) are wrong.

Since there is a random delay of up to a minute, and assuming (as it is not explicitly stated) that a single lying person can move between the rooms at near-instantaneous speed, it is easily possible that they perform the one-shot operation in both rooms themselves, relying on the randomness of the delay to not give their secret up: the fact that the key was reported as being pressed in room A first does not actually mean it was the first pressed!

In contrast, typing a large body of text at on sitting defeats said randomness (I'm assuming, for this claim, that once an input stream from one of the rooms started it is continuous, that is, if the person on the room started typing and I started getting its response once the random delay finished, I'll keep getting that user's typing in real-time, as long as the user keeps typing. Actually, a pause would then be the ultimate indicator).

$\endgroup$
  • $\begingroup$ The random DELAY was added TO THE problem later to manage TIME based solutions, so THAT'S why it's in THERE. As for continuous TASKS, like typing A long SET OF characters, couldn't an HONEST person just need a BREAK every once in a while, KIND OF like how it's hard to CAPITALIZE ARBITRARY PARTS of a comment WHILE typing at the SAME SPEED all the TIME? $\endgroup$ – hdsdv Sep 4 at 4:58
  • $\begingroup$ Didn't know that about the delay, I don't usually look at the edit log. As to the "need a break"... well, of course, I'm making some assumptions about the person(s) abilities. Even so, if we assume the input stream is consistent once the delay has worn off and until a meaningful pause in the typing is detected, I stand by my solution. Even this comment, if you type it by hand without pause should do the trick of proving. Basically, any operation taking longer than 1 minute to complete would do. And BTW, I didn't capitalize ARBITRARY parts of my answer. Look better, you'll see the logic... :D $\endgroup$ – O.F. Sep 4 at 5:37
  • 1
    $\begingroup$ I claim it's arbitrary because if you read your answer, with all of the capitalized words uncapitalized, it doesn't change the meaning or anyone's ability to understand it in any meaningful way. People like to italicize (or capitalize, when they don't know the markup) things to make them seem important. But that doesn't make them important. $\endgroup$ – hdsdv Sep 4 at 5:48
  • 1
    $\begingroup$ I can't upvote (thank you stupid reputation limitations), so consider your comment upvoted. :) I got your point about arbitrariness, I just, as I'm sure you know, disagree. Thanks for this cheerful discussion (really, not being sarcastic), but it feels like we're having a private chat that, on top of all, is off-topic. Upvoting you again, and have a great day! $\endgroup$ – O.F. Sep 4 at 6:01
1
$\begingroup$

I think the following would work:

Tell both ends to give you a random sequence of Zeros and Ones of large length, let's say 1000. Repeat this for several days. After a while you can compare (using algorithms from cryptography) the sequences given by the Person behind door A to the ones given by the Person behind door B. If the sequences from Person A are only self-similar as well as the sequences given by Person B, then it is highly likely that they are different Persons. If the cross-similarity is as high as the inter-similarity, then it is likely that there is only one Person behind both door A and door B.

$\endgroup$
  • $\begingroup$ Do you have any evidence for this? $\endgroup$ – Stop Harming Monica Sep 4 at 14:58
  • $\begingroup$ @OrangeDog paper , especially page 183: The ‘‘quality’’ of generated sequences is reported to be related to mental disorders [6,7,14] and the age of subjects [5]. Sorry for the formatting, the numerous edits and the deleted comment, I can't press enter without sending the comment. See also paper "We built a model that predicts[...], but also the deployment of patterns in another sequence generated by the same subject." $\endgroup$ – Supersamu Sep 4 at 15:14
  • $\begingroup$ They have a computer, so I don't think this works. The trickster might as well just use an RNG. $\endgroup$ – infinitezero Sep 4 at 18:06
0
$\begingroup$

Ask them to type on the keyboard some complex poem one letter at a time (the left room should type odd letters, the right room even letters).

You just need to measure the time it takes. If there is one person in each room, it'll be reasonnably fast. You would get something like:

Words: Two households both equal in dignity
Time : 0----------------------------------->
Left : To hueod bt eul i dgiy
Right: w  oshls oh qa n int

If the person need to go from one room to the other, the latency to move from one room to the other will be visible:

Words: Two households both equal in dignity
Time : 0----------------------------------->
Left : To   hueod       bt   eul   i  dgiy
Right:    w       oshls   oh    qa  n     int

We are testing causality here.

$\endgroup$
  • $\begingroup$ There is an up to 1 min random latency there. This won't work. $\endgroup$ – infinitezero Sep 4 at 18:07
  • 1
    $\begingroup$ This is for communicating with outside (or between room), not in the computer. So in the former case, the computer will measure a 1 unit of time between word (and can take 1mn to send the result, we don't care). In the latter case, the same computer will measure a 5 unit of times between words (and this will still take 1mn to send the result). $\endgroup$ – xryl669 Sep 4 at 20:36
0
$\begingroup$

I have another quite simple one:

Prepare two identical looking boxes with red buttons on it

The first one will hurt (tazer, tear gas, whatever) the person when pressing the button, the second one will simply open and contains a sheet of paper with a message.

Send the first person the box. Tell this person: "Don't press the red button: It will hurt you badly (or even kill you) when trying. Tell the person that you will send the same box to person 2.

If the person does not believe you... oh well... he will be hurt, but you warned him.

A little later send the other box to person 2: Tell this person to open the box by pressing the red button and tell you whats inside. Don't mention the tazer or whatever from box 1.

If it is the same person, he will not open the second box and can't tell you what's inside, no matter whether he tried (and got tazed) or believed you...

If there are two distinct persons, the second will press the button and give you the message, not knowing anything about the danger of the first box...

Voila...

$\endgroup$
0
$\begingroup$

First option:

Send each of them a bath tube full of sticky, not easily cleanable color, one blue, one red and a big sheet of paper. Let them paint their body with the color and let them press the same part of their bodies on the paper (like their left hand or whatever you consider not revealing the identity). Then let them send back the paper. If the colors are clean, they are different people. If it is mixed, it was the same person.

Second option (warning: not for people who can't stand horror movies or violence):

Send them a saw and let each of them cut off 6 toes and then send them back to you. Works as long as they don't have extra toes. Does not specially punish honest people (At least not more then dishonest people).

Third option:

Send them a 4m long stick with a button on each side, which only permanently enables its light when both are pressed at the same time and let them send it back.

Fourth option:

Send them a camera and let them photograph part of their back from a certain distance (in a not identifiable way). A single person has a hard time taking a photo of his own back from a certain distance.

Fifth option:

Send them a device which only tells them a secret code to tell you, when it registers 15 different finger prints or otherwise identifies 2 different persons.

Sixth option:

Send in a trusted person who verifies if there are 1 or 2 persons and then sends back a secret code. There will be only 2 different codes for 1 or 2, so it won't be identifying.

Seventh option:

Burn down the building and watch whether the fire brigade rescues 1 or 2 persons.

Let's hope, nobody uses my answer to use it in real life in a game show ;)

$\endgroup$

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