36
$\begingroup$

I've just taken a CS exam, which had the following question

6 persons entered a library the day a book got stolen. Each of them entered the library once and only once, and stayed there for some time, then left. If two persons were in the library at the same time, at least one of the two saw the other. After the investigation, the testimonies were

  • Albert stated he saw Bernard and Édouard

  • Bernard said he saw Albert and Isabelle

  • Charlotte said she saw Didier and Isabelle

  • Didier said he saw Albert and Isabelle

  • Édouard said he saw Bernard and Charlotte

  • Isabelle said she saw Charlotte and Édouard

Only the culprit is lying. Who is he/she ?

EDIT: I haven't had the time yet to check everybody's answers and claims.

To those saying the problem is ill-posed, I've actually translated the exact wording from the exam (Question IV.C https://www.concours-centrale-supelec.fr/CentraleSupelec/2015/MP/sujets/2014-033.pdf). As Meelo suggested, this can be solved swiftly with interval graphs.

$\endgroup$
  • 5
    $\begingroup$ Are these implied to be the complete lists of who everyone saw? $\endgroup$ – Aza Apr 28 '15 at 17:34
  • 4
    $\begingroup$ @LeGrandDODOM Wouldn't be possible for them all to enter and leave together such that no one is lying (if this is not the complete list)? $\endgroup$ – Mark N Apr 28 '15 at 17:51
  • 3
    $\begingroup$ @leoll2: The guy that posted the puzzle said it in response to Emrakul's question "Are these implied to be the complete lists of who everyone saw?" @Emrakul No, that's just what each person told the police.. $\endgroup$ – Ian MacDonald Apr 28 '15 at 19:23
  • 6
    $\begingroup$ As of now, I see 5 answers "proving" B&D&E as culprits. So something is wrong somewhere. I feel , the question is incomplete or wrongly worded. $\endgroup$ – Prem Apr 28 '15 at 19:26
  • 3
    $\begingroup$ I think itriedacrab and leoll both came up with a solid answer proving D is the lyar. $\endgroup$ – Spacemonkey Apr 28 '15 at 19:52

12 Answers 12

15
$\begingroup$

I think I have an answer:

Didier is lying

I started drawing a graph, eventually gaining this timeline of events (overlaps acceptable).

$Edouard \leftarrow Albert \leftrightarrow Bernard \rightarrow Isabelle \leftrightarrow Charlotte \rightarrow Didier$

You can connect the other sightings, to have at least one relationship,

save for Didier. Didier observes Albert and Isabelle, but there is no relationship between Didier and Bernard, even though they should overlap in some way in order for Didier to observe both Albert and Isabelle. (Didier observed Albert and Isabelle. Bernard is between Albert and Isabelle. Therefore either Bernard should have seen Didier or Didier should have seen Bernard as they would have been at the library at the same time).

Also

Édouard or Didier would have observed the other from their overlapping timelines.

You can verify the answer with this image.

Graph

$\endgroup$
  • $\begingroup$ I think this needs more explanation. Why should there be a relationship between D and B because D saw both A and I? $\endgroup$ – Rand al'Thor Apr 28 '15 at 19:05
  • $\begingroup$ @randal'thor you're right, I need a drawing tool. B visited between A and I, so at least one of B or D should have seen the other for D to have seen A and I. $\endgroup$ – itriedacrab Apr 28 '15 at 19:09
  • $\begingroup$ This seems right $\endgroup$ – Spacemonkey Apr 28 '15 at 19:47
  • 1
    $\begingroup$ Nitpick: D never states that he did not see B. So you assume that the persons answers lists all the people they saw, which is a reasonable assumption but not actually in the wording of the problem. $\endgroup$ – Taemyr Apr 29 '15 at 8:11
  • 2
    $\begingroup$ This appears correct. Ran a brute force for completeness... there are 48 possible permutations that satisfy the conditions of the problem, all have the same liar (the one stated in this solution). In short: (1) A, B, and E enter in any order, (2) A leaves, (3) I enters, (4) B leaves, (5) C enters, (6) E and I leave in either order, (7) D enters, (8) C and D leave in either order. That covers half the cases, the other half do the same in reverse order. $\endgroup$ – glibdud Apr 29 '15 at 15:34
10
$\begingroup$

Because the problem states that exactly one of them is lying, it must be the case that they were not all in the library at once. If they were all in the library at the same time, each of them would have been able to make their statements truthfully, contradicting the one condition.

Let:
$A$ Albert
$B$ Bernard
$C$ Charlotte
$D$ Didier
$E$ Edouard
$I$ Isabelle

Then:
$A \rightarrow B + E$
$B \rightarrow A + I$
$C \rightarrow D + I$
$D \rightarrow A + I$
$E \rightarrow B + C$
$I \rightarrow C + E$

Now let's expand one step:

$A \rightarrow B + (A + I) + E + (B + C)$
$B \rightarrow A + (B + E) + I + (C + E)$
$C \rightarrow D + (A + I) + I + (C + E)$
$D \rightarrow A + (B + E) + I + (C + E)$
$E \rightarrow B + (B + E) + C + (D + I)$
$I \rightarrow C + (D + I) + E + (B + C)$

Here, we notice that $D$ is the only one that doesn't have someone see him after one step. Let's expand again:

$D \rightarrow A + (B + (A + I) + E + (B + C)) + I + (C + (D + I) + E + (B + C))$

Here is the first chance that $D$ has been mentioned in his graph. Unfortunately for him, the graph also contains all of the other people, which can't be the case (as discussed earlier).


Of course, a scenario could be constructed such that $D$ is invisible (by hiding or being quick or whatever). Because there is only one person that claims to see this invisible person, that person is allowed to be the single liar. Any other person is stated to have been seen by at least two people, so everyone else must have actually been seen by at least one person. Our old friend "Invisible Didier", however, cannot be seen by anyone. Hence, Charlotte is a liar and the culprit.

$\endgroup$
  • $\begingroup$ Not really satisfied with the reason, he could just see whoever then immediatly leave thus no one would see him. $\endgroup$ – Spacemonkey Apr 28 '15 at 19:12
  • 1
    $\begingroup$ elegant way to do it... There is a self consistent solution where you assume D is the only liar and he is lying about everything. $\endgroup$ – kaine Apr 28 '15 at 19:12
  • $\begingroup$ @kaine, I agree but that is also true for some of the others. $\endgroup$ – Spacemonkey Apr 28 '15 at 19:13
  • $\begingroup$ @Spacemonkey, that's true. If $D$ enters and leaves immediately without anyone seeing him, then $C$ could certainly be lying. $\endgroup$ – Ian MacDonald Apr 28 '15 at 19:13
  • $\begingroup$ @Spacemonkey Maybe...find them....the best way i can find to look at it is in terms of pairs that can't touch: (AC, AI, BC, BD, DE) $\endgroup$ – kaine Apr 28 '15 at 19:15
10
$\begingroup$

To start: We need to define who was in together at the same time: We'll start off assuming everyone is honest and then look for contradictions.

The relations are as such:

AB, AD, AE, BE, BI, CD, CE, CI, DI, & EI

In all of these cases, at least one person claimed the other was there at the same time.

For the record, the missing relations are:

AC, AI, BC, BD, & DC

So with this information we can figure out who was supposed to be in at the same time. Since AB, AE, & BE are all present at the same time we can conclude that all three were there at (more or less) the same time for the purpose of creating a timeline. All the "combined" relations are:

ABE, AD, BEI, CDI, & CEI

Visually that becomes:

A ---|---|   |   |
B ---|   |---|   |
C    |   |   |---|---
D    |---|   |---|
E ---|   |---|   |---
I    |   |---|---|---

We can now attempt to organize this into a timeline. Since each person only entered once, each line should be intact. This is the best we can get:

A ---|---|   |   |
B    |---|---|   |
C    |   |   |---|---
D ---|   |   |   |---
E    |---|---|---|
I    |   |---|---|---

Ok, so the problem is obvious: We have a cyclical timeline. This timeline only makes sense if we turn it into a cylinder, because no matter how we attempt to put it together (on a straight 2D path) one of the lines is going to be at both ends of the graph without connecting all the way through. So now we can try to verify each of the above relations. We'll go in the order of the "corrected" graph, and we want to rely on cyclical relationships. In other words - 1 sees 2 who sees 3 who sees 1 because that confirms all three are there. Even if, say, 1 was lying, 2 confirms 3 and 3 confirms 1. Since there can only be one liar; 2 confirms themselves by being witness to 3.

AD: D sees A, but A does not see D. No one else is around to complete the circle. Unconfirmed.

ABE: E sees B, B sees A, A sees E (and also B). Confirmed.

BEI: E sees B, B sees I, I sees E. Confirmed.

CEI: C sees I, I sees E, E sees C. Confirmed

CDI: D sees I, I sees C, C sees D (and also I). Confirmed.

Interesting - only one unconfirmed. Also interesting is that we have a double confirmation (where 3 sees both 1 and 2) on either side of the unconfirmed relation.

So one unconfirmed means that that one (AD) has to be the false sighting - and since AD is D's claim - that makes Didier the dirty lying thief.

Go directly to jail!

  • Do not pass Go.
  • Do not collect $200.
  • Give the book back, jeez.
$\endgroup$
  • 1
    $\begingroup$ at least one person claimed the other was there at the same time. Please justify this statement. I see no reason in OP to assume that when A says he sees B and E, that he saw those two at the same time. Ie. it's possible that B and E was never in the library at the same time even if A tells the truth. $\endgroup$ – Taemyr Apr 29 '15 at 8:16
  • $\begingroup$ @Taemyr I did explain that. E sees B. I never said A seeing both means that they're both there at the same time. A seeing both means A is there at the same time E is there and A is there at the same time B is there. Only because E sees B does it mean that all three are there at the same time. The sentence you quoted refers to the box above it. $\endgroup$ – Alexander Apr 29 '15 at 13:30
  • $\begingroup$ It's possible that A was in the library at the same time as B without A seeing B. Thus A's statement may be a lie. Thus D seeing A may be true as it is not the only possible lie. $\endgroup$ – Rick Sep 3 '15 at 19:32
10
$\begingroup$

This is perhaps the interval graph solution LeGrandDODOM referred to.

Create a graph by

adding an edge between each pair where one supposedly saw the other. Graph representing people who saw each other

We then have

If everyone is telling the truth, the resulting graph is an interval graph. Interval graphs clearly cannot have an induced $C_4$, but the resulting graph has at least two: $ADIB$ and $ADCE$. Hence not everyone is telling the truth and the lies must correspond to edges or non-edges to make both of these $C_4$s not induced. Thus $A$ or $D$ is lying as these are the only two on both $C_4$s. $D$ may be lying about seeing $A$, or perhaps $A$ is lying about not seeing $C$ and $I$. As far as I can tell, either case can happen.

$\endgroup$
  • 1
    $\begingroup$ Except if $A$ were the liar, $ADIB$ would still be a valid $C_4$, because both $D$ and $B$ said they saw $A$. $\endgroup$ – glibdud Apr 29 '15 at 17:26
  • 1
    $\begingroup$ This answer is excellent, except the second to last sentence makes an oversight, thus missing the conclusion. You're right that one of those two is lying because they're the only two on both C4s, but more relevant is that there's only one edge in both C4s. Ergo, that edge is the lie, and we therefore know who the liar is. $\endgroup$ – Mooing Duck Apr 29 '15 at 19:29
  • 1
    $\begingroup$ @glibdud: If you consider it possible that $A$ actually saw $C$ and $I$ and this is considered lying, then I stick with $A$ could be the liar. It's true, ADIB is still a $C_4$, but it is no longer an induced $C_4$ (that is, there are edges among those $4$ vertices not part of the cycle). Therefore, $ADIB$ is not a problem. In fact, Zeb below gives a specific example of how this could happen. Since you have issue with Zeb's answer too, I think perhaps we're interpreting the problem differently. $\endgroup$ – Tyler Seacrest Apr 30 '15 at 6:51
  • 2
    $\begingroup$ @MooingDuck: Thanks. You're right in that the only way to make the graph an interval graph by removing edges claimed by a single person is to remove that AD edge. But if you consider adding edges to make a graph an interval graph, that's where I feel like you can claim A is a possible liar. But again, perhaps we're interpreting the puzzle in different ways. $\endgroup$ – Tyler Seacrest Apr 30 '15 at 6:53
  • 1
    $\begingroup$ @glibdud I believe the interpretation you made is that the liar's statement must contain no truth, whereas this interpretation is that the liar said something false or omitted information. For both interpretations the truth tellers omitted no information. $\endgroup$ – Rick Sep 3 '15 at 20:22
4
$\begingroup$

The Problem is ill Posed

If both person 1 states they see person 2 and person 2 states they see person 1 then they must have been in the library at the same time. This is true because at least one of person one and person 3 must be telling the truth as there is only one liar.

To move further we need to further define what it means to lie:

If lying by omission is not lying

In this case people are allowed to have seen people they do not mention without being considered liars. The only way to be considered a liar is to say you saw someone you in fact did not.

If this is the case then:

Any of them could be a liar.

First lets tabulate the statements, if the column header stated they saw the row header then I'll mark that intersection. If it was a corroborated sighting it is marked with an X, if it was a one directional sighting it is marked with a ?

  a b c d e i
a \ X   ?
b X \     ?
c     \   ? X
d     ? \
e ?       \ ?
i   ? X ?   \

From this we can see each person stated at least one uncorroborated sighting.

This means that any of them could be the liar: Everyone except the person the liar supposedly saw arrives. Then the liar leaves and the last person arrives. Now everyone would have seen everyone with the exception of the liar and the person they supposedly saw. Since the person they supposedly saw did not claim to see the liar, they did not lie. Thus everyone except the liar only told lies of omission and any of them could have done it.

If the whole truth and nothing but the truth is required

In this case we can make some more deductions.

If neither person 1 states they see person 2 nor person 2 states they see person 1 then either they must not have been in the library at the same time or one of them is the liar. This is true because if they were in the library at the same time at least one of them would have seen the other so then one of them must have omitted seeing the other and is thus lying.

The liar could have been there the entire time. The liar could just be lying by omission. As long as everyone else's testimonies are consistent this should be valid. This means that any consistent system of testimonies with 5 people could be valid with the 6th person being the liar that was there the whole time. Thus we can just examine each 5 person subsystem. Thus the analysis that follows excludes the liar from the the analysis, and anywhere is says people or person, this means truth telling people/person as the liar is excluded from the analysis.

First lets try the full system assuming no liar:

Assuming no lies then here is a table where an X indicates that the row header and column header were in the library at the same time, and a blank indicates they were never in the library at the same time (top half used only for clarity):

  a b c d e i
a \ X   X X
b   \     X X
c     \ X X X
d       \   X
e         \ X
i           \

Now if pair 1&2, pair 2&3, and pair 1&3, each have an X then 1,2, and 3 must have all been in the library at the same time. We know this must be true because none of them can reenter the library. WLOG 1 arrived first. 1 must not leave until both 2 and 3 have arrived. WLOG 2 arrives next. 2 must not leave until 3 has arrived. Thus when 3 arrives they will all be there.

There are no sets of 4 people where each pair of people has an X. Thus there was not a time when there were 4 people simultaneously in the library. This means that the periods where there were at least 3 people in the library were never interrupted by a forth person coming or going and can be considered one time unit. (Remember the caveat that the liar is excluded, so the liar my be present simultaneously with three truth tellers)

In the 6 person system there are 4 triplets:

library occupant triplets

ABE, BEI, CDI, and CEI

If these three triplets exist on the timeline then all of the X's involved with them will be satisfied. The remaining X's that need to be satisfied are:

  a b c d e i
a \     X  
b   \
c     \      
d       \
e         \  
i           \

AD. For each of these pairs (just one in this case) there must be a time period during which only the pair is in the library as none of these pairs is part of a triplet.

Thus a list of occupancies that must have existed at some point during the day are as follows: ABE, BEI, CDI, CEI, and AD

This can be visualized in tabular where the rows are people, the columns are time periods and an O indicates occupancy.

  1 2 3 4 5
a O       O
b O O
c     O O
d     O   O
e O O   O
i   O O O

To be a solution the time periods would need to rearrange so that each person occupied the library only during consecutive periods. As expected these periods cannot be arranged in such a manner. Proof for those interested otherwise skip to the next section:

For i's visit to be consecutive periods 2, 3, and 4 must be next to each other. withing that span 2&4 and 3&4 must be consecutive for e and c respectively. That only allows the order 2, 4, 3 or its reverse:

  1 2 4 3 5
a O       O
b O O    
c     O O
d       O O
e O O O
i   O O O

For d to be consecutive 5 must be consecutive with 3, and for e and b to be consecutive 1 must go next to 2, but for a to be consecutive 1 must go next to 5 which is impossible. Thus indeed someone must be lying.

The Possibilities

A lied

Following the same logic as the previous example we can construct tables without A (s A could have been there the whole time if they're lying, This really boils down to removing A from the final period table:

  2 4 3
b O
c   O O
d     O
e O O
i O O O

This is a legitimate possibility. A could be the culprit. Here's a diagram of the library occupancy including who saw who when. Note that A did not see B despite saying they did, whereas everyone else saw only who they said they saw, and no two people were in the library at the same time without one of them seeing the other. Library Occupancy Liar A

B lied

  1 4 3 5
a O     O
c   O O
d     O O
e O O
i   O O

Again not possible

C lied

  1 2 3 5
a O     O
b O O
d     O O
e O O
i   O O

Again not possible

D lied

  1 2 4
a O
b O O
c     O
e O O O
i   O O

This scenario is also possible so D could be the culprit:Library Occupancy Liar D Note: that here D said they saw A but they instead saw E. This Solution allows for everyone to see exactly 2 people, which is slightly more in line with the problem statement, so if the problem statement was modified to state that each person saw exactly two people then D would have to be the culprit as if A was the liar they would see a minimum of three people.

E lied

  1 2 3 5
a O     O
b O O
c     O
d     O O
i   O O

Again not possible

I lied

  1 4 3 5
a O     O
b O
c   O O
d     O O
e O O

Again not possible

Conclusion

This problem has two solutions as stated, but could be easily modified to eliminate A as the culprit by stating that each person saw exactly two other people in the library. In that case D is the culprit. Another modification/interpretation that some people took and would result in the same conclusion: The lair included no truth in their statement while the honest students stated the whole truth and nothing but the truth (but this makes the puzzle much easier, and relies on using two different definitions of lying). Yet another modification would be to state that no one, including the liar, saw anyone that they didn't claim to see.

$\endgroup$
  • $\begingroup$ You yourself said that there can't be 4 people in the library at once. Thus, your scenario for A being the liar can't work because the graph requires 4 people at once twice (ABEI, ACEI). $\endgroup$ – ErikE Feb 6 '16 at 1:29
  • $\begingroup$ @erik that was in the section where I was under the assumption that there was no liar. When there is a liar, the liar can be present during any of the times where there are three other people in the library without invalidating anyone else's testimony. $\endgroup$ – Rick Feb 7 '16 at 5:30
  • $\begingroup$ But the OP says there is one liar... I don't understand why you'd entertain any other scenario. $\endgroup$ – ErikE Feb 7 '16 at 5:47
  • $\begingroup$ Your final answer is that "the problem has two solutions as stated". This is what I'm taking exception to. Do you still maintain this? You say, "This is a legitimate possibility. A could be the culprit." But according to your own logic, A can't. There is nothing in your answer that eventually disclaims A as a valid answer with the rules as given. $\endgroup$ – ErikE Feb 8 '16 at 17:01
  • $\begingroup$ @ErikE According to my own logic it certainly can... If you take the paragraph "There are no sets of 4 ... can be considered one time unit." and substitute "truth telling people/person" in for "people/person" it is now more obvious that my logic still holds. from the statement "First lets try the full system assuming no liar:" onward, all of my systems ignore the liar as if they didn't exist. So "people" doesn't include the liar. and thus there are three "people" in the library while ABEI and ACEI are in the library because for the analysis of whether A could be lying, A is not considered. $\endgroup$ – Rick Feb 9 '16 at 15:54
3
$\begingroup$

The problem is ill-posed.

The liar must be one of A or D, but there is a consistent scenario where A lies and everyone else tells the truth, as well as a consistent scenario where D lies and everyone else tells the truth.

First scenario:

A enters at 7:00 AM, I enters at 8:00 AM, B enters at 9:00 AM, E enters at 10:00 AM, B leaves at 11:00 AM, C enters at 12:00 PM, E leaves at 1:00 PM, D enters at 2:00 PM, C leaves at 3:00 PM, D leaves at 4:00 PM, I leaves at 5:00 PM, A leaves at 6:00 PM. A is the only liar: the truth is that A saw everybody.

Second scenario:

D enters at 7:00 AM, E enters at 8:00 AM, C enters at 9:00 AM, I enters at 10:00 AM, C leaves at 11:00 AM, B enters at 12:00 PM, I leaves at 1:00 PM, A enters at 2:00 PM, B leaves at 3:00 PM, A leaves at 4:00 PM, E leaves at 5:00 PM, D leaves at 6:00 PM. D is the only liar: the truth is that D saw everybody.

Whittling down the suspects:

Say that suspects X and Y are "connected" if one of X or Y claims to have seen the other. Define a 4-cycle to be a four-tuple of suspects (X,Y,Z,W) such that X is connected to Y, Y is connected to Z, Z is connected to W, W is connected to X, X is not connected to Z, and Y is not connected to W. If (X,Y,Z,W) is a 4-cycle, then it is pretty easy to see that at least one of X,Y,Z,W must be lying. Using the 4-cycle (A,B,I,D) we see that one of A,B,I,D is lying, and using the 4-cycle (A,D,C,E) we see that one of A,D,C,E is lying. Thus the liar is either A or D.

There is a hidden symmetry in the problem:

The connection graph described earlier is symmetric under the permutation (AD)(BC)(EI).

$\endgroup$
  • $\begingroup$ The fact that two people are in the library at the same time doesn't necessarily imply that they both saw each other. Thus the flaw in your first scenario is your assertion that the proposed liar saw everybody. It's possible that he only saw the two people he claimed to have seen, and thus is telling the truth. $\endgroup$ – glibdud Apr 29 '15 at 15:55
  • $\begingroup$ Actually, your second scenario has the same flaw, though it's closer to the right order of events. $\endgroup$ – glibdud Apr 29 '15 at 17:12
  • $\begingroup$ @glibdud In Senario 1 while it's true that A did not necessarily see everyone they must have seen those that did not see them as :If two persons were in the library at the same time, at least one of the two saw the other and thus A must have seen C,E, and I but did not state seeing C or I and thus lied by omission. $\endgroup$ – Rick Sep 3 '15 at 14:38
3
$\begingroup$

Note: this answer assumes that a truth-teller says ALL the truth, without omitting information.

The symbol $X-$>$Y$ means that $X$ saw $Y$. We know that:
$A-$>$E$
$E-$>$C$
$C-$>$D$
$D-$>$A$
Which means that $A,B,C,D$ were all in the store at a certain moment. Though, there isn't any edge (graph edge, I mean) between $A-C$ and $E-D$, which should be mandatory if they're all telling the truth. Therefore, the liar is $A,C,D$ or $E$.
B and I are honest.

Suppose $C$ liar. We have a triangle between $A-B-E$, which means that they were together at some point. We also have the triangle $I-E-B$, but we don't have a tie $A-I$, meaning that there's a moment when $B$ was inside the shop and either $I$ or $A$ had already left it, while the other (of $A$ or $I$) hadn't entered yet. If so, how is it possible that $D$ saw $A$ and $I$ without seeing $B$? Impossible! Therefore, C is truth-teller.

Suppose $E$ liar. We know that $A$ and $I$ are never together. $D$ saw both $A$ and $I$ , $B$ saw both $A$ and $I$ too, so how is it possible that $B$ and $D$ weren't together? Impossible! Therefore, E tells the truth.

Suppose $A$ liar. $B$ and $C$ didn't meet. $E$ has seen both $B$ and $C$, meaning that $E$ was present when one had left and the other had yet to enter. D was intermediate between $B$ and $C$, despite not meeting $B$, because he has seen $A$ (who was seen by $B$). So, how is it possible that $E$ and $D$ never met? Impossible, so $A$ tells the truth.

The liar is $D$. This is a scheme of compatible timings. The time is represented on the horizontal axis. People that share points with the same abscissa were together in the library, of course. enter image description here

$\endgroup$
  • $\begingroup$ How can you make the statement that "E tells the truth" and then declare that the liar is E? Is one of those meant to be D? $\endgroup$ – Bailey M Apr 28 '15 at 19:22
  • $\begingroup$ @BaileyM Exactly, I've edited! I hope that it was the only wrong miswritten letter $\endgroup$ – leoll2 Apr 28 '15 at 19:24
  • $\begingroup$ I get the feeling you're falling into the same trap I originally fell into. $\endgroup$ – Spacemonkey Apr 28 '15 at 19:32
  • $\begingroup$ @Spacemonkey Explain? Does my picture conflict with any of the statements? $\endgroup$ – leoll2 Apr 28 '15 at 19:33
  • $\begingroup$ I can try, this thing is making my head dizzy, lol $\endgroup$ – Spacemonkey Apr 28 '15 at 19:34
2
$\begingroup$

I believe the "correct" way to do this is to start by determining which groupings are certain. (I'm certain it's correct, but I don't know if it's how they expected it to be done)

We can quickly identify two pairs of people who definitely saw each other.

  • Albert and Bernard both saw each other.

  • Charlotte and Isabelle both saw each other.

This means these two pairs must have happened.

Now, we also have that Albert saw Edouard, who saw Bernard. This indicates that Edouard was present with at least one of the two, as Albert and Edouard can't both be lying.

Similarly, Isabelle saw Edouard, who saw Charlotte, so Edouard was present with at least one of the two, as Isabelle and Edouard can't both be lying.

We also have that Isabelle saw Edouard, who saw Bernard, who saw Isabelle. These three must be together, as only one can be lying, which still ties all three into the same group.

Finally, we have Isabelle saw Charlotte, who saw Didier, who saw Isabelle. Again, only one can be lying, so these three were present together.

So we have (ABE), (BCI), (CEI), and (CDI) as certain to be present in their respective groups.

This leaves just one claim unaccounted for. Didier claimed to be present with Albert. This is the only claim not corroborated by anybody else, directly or indirectly, and therefore must be the lie.

To solve this more easily, I drew up the claims as a directed graph, and then looked for loops within the graph. If three people formed a loop, they corroborate each other's claims. The only claim not part of a loop is Didier claiming to have seen Albert.

To be clear, methods based on working out timelines are problematic, as they require assumptions about sequences, whereas the above is purely about requiring that there be only one liar.

$\endgroup$
  • 1
    $\begingroup$ As the question was from a CS exam, I feel like this solution is an appropriate one. I had a similar puzzle on my algorithms & data structures exams. $\endgroup$ – Fodder Apr 29 '15 at 4:38
  • 1
    $\begingroup$ "Finally, we have Isobelle saw Charlotte, who saw Didier, who saw Isobelle. Again, only one can be lying, so these three were present together." You have to consider the timelines. Isabelle enters, Didier enters, Isabelle leaves, Charlotte enters. Only one is lying, but Isobelle and Charlotte was never present at the same time. (This sequence might be contradictory to other statements made; I only try to point out that your inference is invalid) $\endgroup$ – Taemyr Apr 29 '15 at 8:22
  • $\begingroup$ @Taemyr - the sequence I did it in was relevant. Charlotte and Isabelle saw each other. Albert and Bernard saw each other. The rest depends on those two. $\endgroup$ – Glen O Apr 29 '15 at 8:37
  • $\begingroup$ Fair enough, although not sufficient. Charlotte enters, Isobelle enters, Charlotte leaves, Didier enters. Only one lie, Charlotte and Didier was not present at the same time. $\endgroup$ – Taemyr Apr 29 '15 at 8:41
  • $\begingroup$ @Taemyr - I realise it sounds a little vague, but what I meant by "present together" was "there was a continuous period, during which at least one of the three was present at any point in that period and all three were present at some point in that period". It indicates that any timeline must have those three in a "group". $\endgroup$ – Glen O Apr 29 '15 at 8:54
1
$\begingroup$

This problem is actually underdetermined. Credit goes to Mark N for the idea of everyone entering the room at the same time


Counter-example: Everyone enters the room at the same time.

Solution 1: Albert is the liar

Albert can claim that they didn't see Bernard even if Bernard was in fact there. As long as Bernard claims that they saw Albert, this follows the rule that one of them saw the other.

Solution 2: Bernard is the liar (similar argument)

Bernard can similarly claim that they didn't see Albert even if Albert was in fact there. As long as Albert claims that they saw Bernard, this follows the rule that one of them saw the other.


Since we have arrived at two valid solutions, this is an underdetermined system.

$\endgroup$
  • 2
    $\begingroup$ All this proves is that it is certain that everybody was NOT in the room at the same time. There is no valid solution in this case, because there must be multiple liars. For example, neither D nor E claims to have seen the other. If they were truly in the room at the same time, then one of them DID see the other, according to the question, so one of them must be lying about not seeing the other. Since the same goes for A & I and B & C, there is no case where only one person is lying, so this scenario does not fit the question. $\endgroup$ – Hylianpuffball Apr 29 '15 at 12:11
  • $\begingroup$ If everyone arrived at the same time then either D or E would have seen each other but neither stated as much, in this case one of them would be lying by omission. Similarly, with B and C. Thus if omitting people seen is considered lying, then not everyone could be in the library at the same time. $\endgroup$ – Rick Sep 3 '15 at 18:24
0
$\begingroup$

These are the only absolute statements I've arrived to:

The following are never inside the library at the same time::

A and C
A and I
B and C
B and D
D and E

$\endgroup$
0
$\begingroup$

I feel like the answer may be that...

Bernard is the culprit.

Why?

There exists a little inconsistency between people seen.
Let's draw these reports out:
B -> AI
D -> AI
C -> DI
A -> BE
E -> BC
I -> CE

This leaves us with the following.

Albert, Bernard, Charlotte, and Edouard were all seen twice.
Isabelle was seen three times.
Didier was seen once.

Given this information,

Say Bernard saw Didier instead of Isabelle. We get the following:
B -> AD
D -> AI
C -> DI
A -> BE
E -> BC
I -> CE

This evens everything out, with Didier and Isabelle now being sighted twice each.

Therefore...

It can be concluded that Bernard lied about seeing Isabelle.

$\endgroup$
  • 1
    $\begingroup$ Equity in sightings would be nice, but there's no reason that prevents someone from being seen by multiple people. $\endgroup$ – Alexander Apr 28 '15 at 22:48
0
$\begingroup$

-> is saw; <- is seen
A -> B E
B -> A I
C -> D I
D -> A I
E -> B C
I -> C E

A <- B D
B <- A E
C <- E I
D <- C
E <- A I
I <- B C D

The thief lied, so that means the thief claims he saw someone when he didn't. That means the thief saw 1 or 0 people. Conversely, only 1 person at most could have seen the thief. Therefore, since D is the only one seen by 1 person or less, D must be the thief.

$\endgroup$
  • $\begingroup$ Why couldn't the thief see 2,3,4 or 5 people? If they are lying they could leave out people they did see too. $\endgroup$ – Rick Sep 3 '15 at 18:15
  • $\begingroup$ Why couldn't more than one person see the thief? $\endgroup$ – Rick Sep 3 '15 at 18:17
  • $\begingroup$ Because everyone claims to have seen more than one person and one of them has to be lying (specifically, the problem says that everyone but the liar must be telling the truth)? $\endgroup$ – Kingrames Sep 3 '15 at 18:36
  • $\begingroup$ Why couldn't the liar have seen people they didn't claim to have seen? $\endgroup$ – Rick Sep 4 '15 at 14:27

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.