Sami Logic Puzzle

[morrisonlucas]

The solution below works, but the statement B4 is entirely self-fufilling (i.e. it is only false because it is false). I'm hoping there is another solution without that problem. To solve, I assumed that C3 was true and then extrapolated from there.

I also tried assuming that B4 was true and E1 was true . Both of those led to contradictions.

Solution is invisible, before each statement.

Alan says: Lies = 3
T 1. David's final statement is true.
L 2. Frank told more lies than David.
L 3. Bob always tells the truth.
T 4. My second statement is false.
L 5. Eric told more truths than lies.

Bob says: Lies = 1
T 1. Eric lied at least once.
T 2. Alan told more lies than David.
T 3. Frank's second statement is true.
L 4. I always tell the truth.
T 5. Chuck told more lies than truths.

Chuck says: Lies = 4
L 1. Bob told more lies than I did.
L 2. Alan told more truths than lies.
T 3. Eric always lies.
L 4. David's third statement is true.
L 5. Frank lied exactly once.

David says: Lies = 2
T 1. Alan lied at least twice.
T 2. Eric told more lies than Alan.
L 3. Bob told more lies than truths.
L 4. Chuck always lies.
T 5. Frank's third statement is true.

Eric says: Lies = 5
L 1. Chuck always lies.
L 2. My fourth statement is true.
L 3. Frank told more lies than Bob.
L 4. I tell more truths than lies.
L 5. Frank lied exactly twice.

Frank says: Lies = 0
T 1. Alan told more lies than Bob.
T 2. Eric's first statement is false.
T 3. Alan told more lies than truths.
T 4. Bob only lied once.
T 5. Eric always lies.

Can anyone get a different solution?

[edited: first post was to test invisible, then to fix typo]

[This message has been edited by morrisonlucas (edited 06-28-2002 01:11 PM).]

[CrystyB]

A new puzle already?? We need to get mith to a doctor, quick!!

[Nauplius]

I came up with the same solution. I went on the assumption that:
At least one person was telling the entire truth on all statements. Starting with Alan I followed each statement until it led to a contradiction, then moved on to the next person with all true. Little did I know that the person telling the complete truth was the last one

[danElectro]

A1 T, A2 F, A3 F, A4 T, A5 F
B1 T, B2 T, B3 T, B4 F, B5 T
C1 F, C2 F, C3 T, C4 F, C5 F
D1 T, D2 T, D3 F, D4 F, D5 T
E1 F, E2 F, E3 F, E4 F, E5 F
F1 T, F2 T, F3 T, F4 T, F5 T

B4 must be F, it's a self-contradiction

[CrystyB]

New users - highlight (select) all or part of the text to reveal the hidden part of the post...

And B4 is not a self-contradiction. The fact that it doesn't participate in the solution is a completely different thing.

[Fjord]

I wrote a program to iterate through the all possible combinations and came up with the same answer and no other answers. You should be able to get the source code from http://lynnserv.2y.net/Sol.java if you are interested

[Bicho the Inhaler]

Okay, I got the same thing. Fjord, that is a lot of combinations (more than a billion!). We thank you for taking the time to do a careful check.

I really liked this problem because the work I'm doing right now is closely related. Some of you may have heard of the (in)famous "SAT" (here, SAT stands for "satisfiability", not "Scholastic Aptitude Test"!) problem, which is famous for being the first identified NP-complete problem and infamous because nobody has figured out whether it is possible to find an "efficient" algorithm (i.e., running time grows as a polynomial function (or better) of the size of the input) to solve it. The SAT problem is, given a Boolean expression, to decide whether it is ever true (satisfiable), and usually we want a "certificate", i.e., a satisfying assignment of the variables, as a proof if the expression turns out to be satisfiable. Sami's logic puzzle is a clear example of a SAT problem. While I was working on it, I noticed that the basic method I was using is very similar to the algorithms in the most common (and most successful ) SAT solver programs.

I'm actually working on algorithms for solving a generalization of SAT, Quantified Boolean Formulas, but I had to study SAT algorithms first.

[HappyFunBall]

Bicho, you need to check your math. If any 15 of the 30 statements could be true, then we still don't have a billion combinations (155,117,520 or (30 15) where (M N) is the binomial coefficient). However, we're restricted by the fact that every person has a different number of truths. So the real number of combinations is:

6! * (5 0) * (5 1) * (5 2) * (5 3) * (5 4) * (5 5) = 1,800,000.

No sweat for a computer. The 6! means that anyone can be "placed" anywhere, ie, each combination of people telling different numbers of truths. Then, for the person telling 0 truths, there are (5 0) ways -- only 1 -- to pick those thruths out of his 5 statements. And so on, for each of the people.

I didn't check the actual program used...but only 1.8 million are really required, not over a billion.

[Bicho the Inhaler]

Ok, I agree. Depending on the implementation, a program may check fewer combinations. An implementation that treats the truth value of the statements as a binary number and repeatedly increments by one (or something similar), for example, would check all 2^30. But a slightly more sophisticated one, as you note, that takes advantage of certain aspects of the problem, doesn't need to check nearly as many. While we're taking advantage of the problem, though, we don't have to stop at 1.8 million; we can also take note of the various statements that say the same thing (D4 and E1 say the same thing, for example) and not let them have opposite values, reducing our search space further.

I probably shouldn't have assumed that "iterating through all possible combinations" meant the naive implementation, and I admit that I still haven't studied the code, my not knowing Java being a small impediment.

[HappyFunBall]

Well, that got me thinking...and wondering if there were any other consistent solutions if you took away the restriction that each person told a different number of truths. So I wrote a program that did plow through all 2^30 possibilities, and I found out that there was, in fact, exactly one more solution. I'm including it below invisible in case anyone wants to take a stab at it without a computer.

Hint: No one always tells the truth.

Answer:

They go A, B, C, etc...and then statements 1, 2, 3, etc:
TTLLL TTLLT LLLLL TLLTT TLTLL TLTLL

[mintwater]

I find this puzzel a bit disappointed, at first glance I thought it would be like another "Einstein puzzel", like 5 men in different houses and pet, cigerat ect. Then further thinking make it more difficult because of the uncertainty of the statements (true or false). I thought immediately that I have to figure out who always tell the truth and who always lies, then work from there. But there is no way to figure that out just by combining the different statements. At last I did what everybody does and just try to assume if Bob/Chuck/David/Eric/Frank always tell the truth and from there on to work things out. For me it seems just like trial and error, involves almost no intellectual challenge. And then like everyone else I thought the statement "I always tell the truth" from Bob is exactually true within context....so maybe next time someone will change this contraditive statement to something else.

[Quailman]

[Bicho the Inhaler]

I'm with Quailman on this one.

I was actually rather impressed with this puzzle. Sami had to devise a problem that is not only solvable but that also admits only one solution.

Originally posted by mintwater:

---

At last I did what everybody does and just try to assume if Bob/Chuck/David/Eric/Frank always tell the truth and from there on to work things out.

---

This is definitely not the only way to solve it and possibly not the best. I'll refer you to morrisonlucas's post: he/she did not use that method, and neither did I. I did something similar to what morrisonlucas did, but started with a different statement.

Originally posted by ibid.:

---

For me it seems just like trial and error, involves almost no intellectual challenge.

---

I must disagree. In large trial and error situations like this there is definitely a challenge: where to start trying. If you start somewhere random, chances are you'll be there for a while. It takes some intuition to know a good place to start. In this case there might be even faster routes to the solution than the ones posted here (I don't actually know because I only tried the one).

[Macros]

~is tempted to continue his sad game~ oh what the hey,
did that post go in ok bicho? ahahahahahah! im so funny!

[BigBunch]

I loved working with this puzzle until I saw the answer. B4 being B's only lie is silly. For B4 to truly be a lie, B has to tell at least one more lie. I was working with F4 (B lie = 1)being a lie to start me off because of that.

Saying B4 is B's only lie seems is ignoring the lying paradox and seems like a cheaper way to get out of the puzzle.

[BlackiePas]

I get a different solution when Bob's 4th statement is false.
Try this: Chuck always lies. Bob(#3,4) an David (#2,3) lied twice. Alan (#3,4,5), Eric (#2,4,5) and Frank (#2,4,5) lied three times. These conditions seem to satisfy all the statements.

[Bicho the Inhaler]

BlackiePas, you're forgetting that everybody has to tell a different number of truths. You have Bob and David telling the same number as well as Alan, Eric, and Frank telling the same number. HappyFunBall already demonstrated that there is an extra solution when that condition is lifted, which it seems like you have correctly identified. You can read HappyFunBall's solution by highlighting reply 9 to make the "invisible" text appear.

[This message has been edited by Bicho the Inhaler (edited 08-02-2002 09:13 PM).]

[KitMarley]

A fascinating puzzle that I was unable to crack. However, one criticism.
In the context of this game, B4 must be read as "All my 5 statements here are true," just as "X tells more lies than truths" is read as "of his 5 statements here, X tells more lies than truths." Therefore, if B4 is false, another of his statements here must be false. The solution in which B4 is his only false statement is invalid.
B4 is not self contradictory: the statement "I always lie" would be.
Having said that, even without this flaw, I would still have been unable to solve it.