Convoluted Logic Puzzles 101 and 102

Question

I need some help. I'm registered for two courses at the Louisiana Institute of Epistemology this semester, but the TA's are super hard to communicate with! Can you help figure out where my classes meet and get a passing grade in both? I'm looking for a strategy which has a 100% chance of working, if that isn't too much to ask.

Here are the syllabi for the two classes. Thanks in advance!

---

Convoluted Logic Puzzles 101

Instructor: Raymond Smullyan*
Prerequisites: Must be comfortable with the concept of Knights (who are honest), Knaves (who always lie), and Fools (who ignore the question and answer randomly).
Teaching Assistants: A Knight, a Knave, and a Fool.
TA Emails (in no particular order): [email protected], [email protected], [email protected]
Location: One of the 64 rooms in the logic department. Email the TA's to find out which.
Email Policy: Your emails should only be addressed to a single TA at a time. The TA's will only answer emails which contain a single yes or no question about the course. You should not assume that the TA's know each other. Asking a self-referential questions will result in a failing grade. Same goes for asking a question which the TA does not know the answer to.
Grading: There will be no homework or midterms. The final exam is simply to show up to class. If you successfully do this, your grade is determined by the number of emails you sent, according to the following rubric:

$$ \begin{array}{|r|c|c|}\hline \text{Emails Sent} & ≤9&≥10\\\hline \text{Grade} & \text{Pass} & \text{Fail}\\\hline \end{array} $$

---

Convoluted Logic Puzzles 102

Instructor, Prerequisites, Location, Email Policy: See syllabus for CLP 101.
Teaching Assistants: Two Knights and a Fool.
TA Emails (in no particular order): [email protected], [email protected], [email protected].
Grading: Same as for CLP 101, but with the following rubric: $$ \begin{array}{|r|c|c|}\hline \text{Emails Sent} & 10&\ge 11\\\hline \text{Grade} & \text{Pass} & \text{Fail}\\\hline \end{array} $$

---

TL;DR There are two puzzles. The goal of both is to find which of 64 rooms a class meets in. There are three people whom you can ask yes/no questions to determine this info, each directed at a single person. These people do not know each others' identities.

1. In the first puzzle, these three people comprise a Knight, Knave and Fool in some unknown order. The goal is to deduce the room in 9 questions (in the worst case).

2. In the second puzzle, there are two Knights and a Fool, and you have 10 questions.

*On a serious note, Raymond Smullyan sadly passed away just last month.

Answer 1

We treat the room number as a 6 bit binary number and assume everyone agrees on the encoding. ie let 000000b be the first room 000001b the next and 111111b the last room. But any system to uniquely identify the room in six bits (or yes/no's) works with only minor changes to the wording of the questions.

101: well solved above.

ask a known truth value of each (are you a TA?), the one who answers in the minority will continue to answer with the same truth value. Three questions to find a reliable TA, six questions for six bits of the room, nine in total.

102: Since there is only one fool anything two TA's agree on is true.

1,2,3) Ask Descartes the first 3 bits over three questions. "is bit 0 0?" "is bit 1 0?" .. 4) Ask Euler if the bits you got from Descartes are correct. "are bits 0,1,2 011?" (if Descartes answers are yes, no, no)

Here the two answers cause different paths, So I'll label them A and B

A) Euler says no. Either Descartes or Euler is the fool: ignore them both and disregard their answers. Since there is only one fool Fermat must be reliable. A 5,6,7,8,9,10) ask Fermat each bit in turn. B) Euler agrees with Descartes. B 5,6) ask Descartes about bits 3 and 4. B 7) ask Euler if Descartes' bits are correct.

Again with different answers we do different things so I'll label these C and D

C) Euler says no. As with A the fool is one of two and you ignore them both, but this time you keep the first 3 bits and trust Fermat. C 8,9,10) ask Fermat the last 3 bits. D) Euler confirms Descartes' second group. We have 5 known bits. D 8,9,10) ask each for the last bit, and go with the majority.

This works by having enough reserve questions to change TA's if an error is detected. and finishes one question early if no error is ever detected, which should happen 1/3+1/8*1/3+1/64*1/3 ~= 38%

Answer 2

101

Q1. A, are you TAing CLP101? Q2. B, are you TAing CLP101? Q3. C, are you TAing CLP101? Two of the three answers I get must agree. If they say yes, then the other guy is the knave; if they say no, then the other guy is the knight. In either case, six more questions to the other guy will tell me where to go.

102

[EDITED to add: The following is wrong because I somehow managed to multiply 3 by 3 and get 6 instead of 9. I'm leaving it here until such time as I or someone else come up with a correct solution, in case there are useful ideas in it.]

I begin by asking

D for bit 0 of the room number, E for bit 1 of the room number, and F for bit 0 xor bit 1. If the obvious parity check passes then I have two good bits. Otherwise, I know that exactly one of these things is true: D is the fool and his bit 0 is wrong; E is the fool and his bit 1 is wrong; F is the fool and his bit 0^1 is wrong. I do exactly the same for bits 2,3 and exactly the same for bits 4,5. I have now asked 6 of my 10 questions. If the parity checks all passed then I'm done. Otherwise, here's where we stand: if $n$ is the number of parity checks that failed then I have a set A of $n$ even-numbered bits and a set B of $n$ odd-numbered bits, such that one of three things is true: D is the fool and all the bits in A are wrong (but no others); E is the fool and all the bits in B are wrong (but no others); or F is the fool and all the bits I got from D and E are correct.

Now I ask

E for one of the bits in set A. If he agrees with D then we have ruled out the case where D is the fool and all the bits in set A are wrong (because if D is the fool then E isn't, so he'll answer this one correctly and therefore disagree with D). So now we know D is a knight and the bits in set A are good; we can ask D about one of the bits in set B (which, remember, are either all right or all wrong) at which point we know all the bits in B, and we're done. Eight questions at most.

But if, on the other hand,

if E disagrees with D about that bit in set A then we know that either D or E is the fool. In particular, F isn't. So now we ask F about one bit from A and one from B, and we know everything. Nine questions at most.

Answer 3

101:

This one seems easy.

You first send 3 emails to each of the TAs asking if you got the right email(for example: "if your email [email protected]?"). Once you get all 3 responses back, you will have one yes, one no and one random. So you can easily determine at least one knight or one knave(1 yes and 2 no = the TA who said yes is a knight; 2 yes and 1 no = the TA who said no is a knave)
Then you send remaining mails to the one who you know, asking for a binary representation of the room number. The emails would be like: "If you convert the room number into binary, will the rightmost/second(third/fourth...) from the right digit be 1?". Based on his/her responses you will have 6 binary digits, which you can easily transform into the room number. Just don't forget to flip them if you are talking to the Knave.
"But 6 binary digits can only form numbers from 0 to 63, how will you know if it's room 63 or 64?"
Easy. There are 64 rooms in total, so if you will end up having all zeros(000000), then the digit on the left will be 1, which will make the room 64. If any of the 6 last digits is not 0, then the 7th from right can not be 1, since this will make a number greater than 64.

---

102:

Work in progress...