2
$\begingroup$

(Your investigations continue here.)


I am testing this puzzle to see how it works, and gauge the difficulty. I have plans which will be unveiled in future puzzles of a similar nature, pending interest etc here.

Here are the rules:

There is a group of people on an isolated island, and, in a curious twist, the butlers have all been murdered. You have been sent to collect statements from each person.
- Each person in the group is either guilty or innocent.
- Each person is either friends or not friends with each other person. The friendship is mutual.
- Each guilty person is friends with every other guilty person.
- Each innocent person has witnessed a number of events, which allows them to deduce the innocence or guilt of a number of people in the group. This may or may not have been reciprocated.
- The guilty people know who the guilty and innocent parties are.
- Each person is either boastful or modest (to be explained below).

The statements that each person makes are as follows:
- Innocent modest people will simply make a list of truthful statements.
- Innocent boastful people will do the same, but will also make a statement about a random other person about whom they know nothing. If the person is their friend, they will say s/he is innocent. Otherwise they'll just say something (innocent or guilty at random).
- Guilty modest people will say that friends are innocent (regardless of whether they are); they will say that non-friends are guilty (which is inaccurate, because their non-friends are innocent by the above definitions).
- Guilty boastful people will do the same. But they will also make one truthful statement (either that one of their guilty friends is guilty or that one of their innocent non-friends is innocent).

This kind of thing happens a lot to you...

On this particular day, you go out to the island and get to sit down with the main characters: Bill, Celia, Laine, Timika, Delicia, and Terrance

These are their statements:

Statements of Bill:
- I am innocent
- Delicia is guilty
- Laine is guilty
- Celia is guilty
- Timika is innocent

Statements of Celia:
- I am innocent
- Timika is guilty
- Bill is guilty
- Laine is innocent
- Terrance is innocent

Statements of Laine:
- I am innocent
- Bill is guilty
- Terrance is innocent

Statements of Timika:
- I am innocent
- Terrance is guilty
- Delicia is guilty
- Bill is innocent

Statements of Delicia:
- I am innocent
- Laine is innocent
- Bill is guilty
- Terrance is innocent

Statements of Terrance:
- I am innocent
- Timika is guilty
- Delicia is innocent
- Laine is innocent
- Bill is guilty

This seems like a complete disaster. You are struggling to find something sensible out of what they say. So you phone your mentor and good friend, Hercule, and he says, "Ze simplest solution is probably true. Find ze solutio' wiz ze fewest conspirators. Zat will be your answer."

As always, post your solutions below, and please also comment about the puzzle - what you like and what you don't. How difficult your found this. As I said, I'm hoping to do a couple more, assuming this works as intended...

$\endgroup$
  • $\begingroup$ Do the guilty people know who else is guilty and who is not? $\endgroup$ – 2012rcampion Dec 5 '15 at 2:50
  • $\begingroup$ Yes. Guilty people know who the other guilty people are $\endgroup$ – Dr Xorile Dec 5 '15 at 3:04
3
$\begingroup$

Some useful facts about innocent people:

  1. An innocent person makes at most one false statement. (Every one of their statements is true, except for at most one boastful statement, which can be true or false.)

  2. If an innocent person claims a set of people is guilty, no more than one of those people is innocent.

  3. If an innocent person states that $n$ people are guilty, at least $n-1$ people are guilty.

  4. If $n$ people are guilty, an innocent person will claim that at most $n+1$ people are guilty.

And some facts about guilty people:

  1. If a guilty person claims a set of people is guilty, at most one of those people is guilty. (Every statement they make about someone being guilty is false, as mentioned by Dr. Xorile, except for at most one boastful statement, which is always true.)

Since we want to find the case with the minimum number of guilty people, we can step through a number of cases: first assuming that no people are guilty, then assuming that one person is guilty, etc. The first possible case that we find is the correct answer.

Zero

We can immediately eliminate the case where nobody is guilty; since in that case everyone would be innocent, and they would all claim that there was at most one guilty party (by property 4).

One

In this case, every innocent person claims that at most two people are guilty. That means that Bill must be guilty (by property 4), since he claims three people are guilty.

However, that means everyone else is innocent, and at most one of Timika's statements:

  • Terrance is guilty
  • Delicia is guilty
  • Bill is innocent

is false (property 1); however, all three statements are false: a contradiction.

Two

Assume that Bill is innocent. Then at most one of his statements:

  • Delicia is guilty
  • Laine is guilty
  • Celia is guilty

is false (property 1). Since there are only two guilty parties, one of the first three statements must be false. Since Bill can make at most one false statement, two of Delicia, Laine, and Celia must be guilty. Everyone else (Timika and Terrance) must be innocent.

Since Terrance is innocent, at most one of his statements:

  • Timika is guilty
  • Delicia is innocent
  • Laine is innocent
  • Bill is guilty

can be false; however, we know that both the first and last are false: a contradiction.

Therefore our assumption was false, and (if there are exactly two guilty people) Bill is guilty.


Assume that Timika is innocent. At most one of her statements:

  • Terrance is guilty
  • Delicia is guilty
  • Bill is innocent

can be false (property 1). We know that the last is false. However, since only one additional person can be guilty, at least one of the first two must also be false: a contradiction.

Therefore, if exactly two people are guilty, Bill and Timika are guilty.

Now we only need to check that no contradictions arise if Bill and Timika are guilty. To do this I make a big assumption:

Everybody is Modest

This simplifies the rules, giving us some new properties:

  1. Everything an innocent person says is true.

  2. If a guilty person claims that another person is guilty, that person is innocent.

We don't need to worry about guilty persons' claims that another person is innocent, since this only implies that the two are friends. If the second party is guilty, this must be satisfied; otherwise the person is innocent, and their friendships don't matter. I'll mark these statements with don't care.

Let's check everyone's statements:

Bill Guilty:

  • I am innocent don't care
  • Delicia is guilty innocent, OK
  • Laine is guilty innocent, OK
  • Celia is guilty innocent, OK
  • Timika is innocent don't care

Celia Innocent:

  • I am innocent innocent, OK
  • Timika is guilty guilty, OK
  • Bill is guilty guilty, OK
  • Laine is innocent innocent, OK
  • Terrance is innocent innocent, OK

Laine Innocent:

  • I am innocent innocent, OK
  • Bill is guilty guilty, OK
  • Terrance is innocent innocent, OK

Timika Guilty:

  • I am innocent don't care
  • Terrance is guilty innocent, OK
  • Delicia is guilty innocent, OK
  • Bill is innocent don't care

Delicia Innocent:

  • I am innocent innocent, OK
  • Laine is innocent innocent, OK
  • Bill is guilty guilty, OK
  • Terrance is innocent innocent, OK

Terrance Innocent:

  • I am innocent innocent, OK
  • Timika is guilty guilty, OK
  • Delicia is innocent innocent, OK
  • Laine is innocent innocent, OK
  • Bill is guilty guilty, OK

Since there are no contradictions, it is possible that Bill and Timika are guilty, and (thanks to our previous arguments) we know that this solution is unique for two or fewer guilty parties.

$\endgroup$
  • $\begingroup$ So what was the plain text of your md5? $\endgroup$ – Dr Xorile Dec 5 '15 at 5:40
  • $\begingroup$ @DrXorile "Bill and Timika" $\endgroup$ – 2012rcampion Dec 5 '15 at 5:55
  • $\begingroup$ Classic. I briefly considered writing a script to go through all the combinations to see if it could be done. I think one would normally add some random text in to thwart such a technique. But its probably easier to solve the puzzle! Lol $\endgroup$ – Dr Xorile Dec 5 '15 at 5:58
  • $\begingroup$ Do you have any feedback on the puzzle? I'm assuming from the lack of upvotes that this isn't one to repeat too many more times! But if I were to repeat it, what would make it more interesting. My original idea was to have a quasi-realistic scenario where it could be solved based on unreliable statements. $\endgroup$ – Dr Xorile Dec 5 '15 at 6:02
  • $\begingroup$ @DrXorile, good point, I forgot to salt my hash =P I actually used some computer analysis to solve this one (by reduction to boolean satisfiability); that's how I figured out that it didn't matter what statements were boastful. There are 6*5/2=15 possible friendships (2^15 states), 3, 4, or 5 possibilities per person for which statements are boastful (6000 states), and 6 guilty/not guilty (2^6). The total search space is about 33.5 bits. I don't know how hard it would be without computer assistance, but it was an interesting problem! $\endgroup$ – 2012rcampion Dec 5 '15 at 6: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.