1
$\begingroup$

I have problem to solve,

Three people have their own statement:

Alice : If Bob tells lie, then Charlie tells lie too

Bob : If Charlie tells lie, then Alice tells lie too

Charlie : If Alice tells lie, then Bob tells lie too,

Who is the lier?

I tried to figure it out by assuming three condition: Alice is telling truth, Bob is telling truth, and Charlie is telling truth, and i used truth table too and assume for false-truth combination, but i still cant solve this problem or find who is the lier. So, who is the lier?

$\endgroup$
0
$\begingroup$

Hint: You can write the three sentences as $$A\leftrightarrow (\neg B\rightarrow \neg C)$$ $$B\leftrightarrow (\neg C\rightarrow \neg A)$$ $$C\leftrightarrow (\neg A\rightarrow \neg B)$$

and all of them need to be true, thus you need to find interpretation such that

$$(A\leftrightarrow (\neg B\rightarrow \neg C))\wedge(B\leftrightarrow (\neg C\rightarrow \neg A))\wedge(C\leftrightarrow (\neg A\rightarrow \neg B))$$ is true.

Hint 2: If you apply cyclic permutation to one of the three sentences, you will get the other ones. That means that interpretation under which all are true must also be invariant under cyclic permutations. There are only two such interpretations.


Edit:

Since J.G. decided to give a full solution, I might do it as well. Let me just say that Hint 2 (in the form that I've written) works only if we know that the solution to the problem is unique, otherwise the argument doesn't go through.

Let $\{a,b,c\}\subseteq \{0,1\}$ be an interpretation. Note that at least two of $\{a,b,c\}$ need to be equal. Since the sentences in the first Hint are cyclic permutations of each other, WLOG, $b = c$. That means that $\neg B\rightarrow \neg C$ is necessarily true and so is $A$, i.e. $a = 1$. Thus, either $(a,b,c) = (1,0,0)$ or $(a,b,c)=(1,1,1)$. You can easily check that the third sentence is false under interpretation $(1,0,0)$. Thus, no one is lying.

$\endgroup$
0
$\begingroup$

No-one is lying.

Let $A$ denote Alice's statement etc. so $A$ is equivalent to $\neg B\implies\neg C$ or, more neatly, $C\to B$. Representing claims as their truth values ($1$ for true, $0$ for false), we can instead write $A$ as $B\ge C$.

Everyone telling the truth works, viz. $A=B=C=1$.

But everyone lying doesn't, because $A=B=C=0\implies B\ge C\implies A=1$.

Nor can exactly two people be telling the truth, since by cyclic permutation we can assume Alice would be one of them, and then the remaining truth-teller would have to be Bob, so $C\ge A$, making Charlie a truth-teller too.

But in fact, a single truth-teller isn't possible either; again cyclic permutation can make it Alice, so Charlie is lying and $B>A$, which contradicts Alice being a truth-teller.

$\endgroup$
0
$\begingroup$

As in my previous answer, we need to find interpretation such that

$$A\leftrightarrow (\neg B\rightarrow \neg C)\tag{$a$}$$ $$B\leftrightarrow (\neg C\rightarrow \neg A)\tag{$b$}$$ $$C\leftrightarrow (\neg A\rightarrow \neg B)\tag{$c$}$$

are all true.

Note that $P\rightarrow Q$ is equivalent to $\neg Q\rightarrow\neg P$, so the above sentences are equivalent to

$$A\leftrightarrow (C\rightarrow B)\tag{$a'$}$$ $$B\leftrightarrow (A\rightarrow C)\tag{$b'$}$$ $$C\leftrightarrow (B\rightarrow A)\tag{$c'$}$$

Now, $P\rightarrow (Q\rightarrow P)$ is tautology, i.e. equivalent to $1$.

Finally,

$$(a')\wedge (b') \implies A\leftrightarrow (C\rightarrow (A\rightarrow C)) \implies A \leftrightarrow 1$$ $$(b')\wedge (c') \implies B\leftrightarrow (A\rightarrow (B\rightarrow A)) \implies B \leftrightarrow 1$$ $$(c')\wedge (a') \implies C\leftrightarrow (B\rightarrow (C\rightarrow B)) \implies C \leftrightarrow 1$$

and thus, everybody tells the truth.

$\endgroup$
0
$\begingroup$

As an alternative and much quicker solution to the ones already given, consider that all statements are cyclic and so no particular person can be the only one lying/telling the truth. Either everyone lies or everyone tells the truth. Clearly it can't be the case that everyone lies, so everyone tells the truth.

$\endgroup$
  • $\begingroup$ This is the quickest way, but only works if we know that solution is unique. For example, $\{(1,0,0),(0,1,0),(0,0,1)\}$ could all be solutions and the cyclic symmetry is satisfied. $\endgroup$ – Ennar Sep 4 '18 at 13:13
  • $\begingroup$ Sure, but that clearly isn't true in this case. Though I agree with you that in more complicated problems that could be a concern. $\endgroup$ – YiFan Sep 4 '18 at 23:43

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.