Knights and knaves

This kind of puzzle makes use of knights and knaves. A knight is a person who always tells the truth. A knave is a person who always lies. This sort of puzzle was invented, or at least popularized by Raymond Smullyan. They are fun times.

Classic #1:

You are trying to reach the legendary Knight's Village, where everyone is a knight. But you've reached a fork in the road, and you know that if you take a wrong turn, you will instead end up at the Knave's Village, where everyone is a knave. The fork is unmarked, but you see a villager, and resolve to ask him for directions. What single question should you ask him to get to the Knight's Village?

Classic #2:

You are in a labyrinth, and have reached a fork. One of the paths lead out, and the other will certainly lead to your doom (it's that kind of labyrinth). Two guards stand nearby, identical twin sisters. You have heard of these guards, and know that one is a knight, while the other is a knave. What single question can you ask the guards to get out of the labyrinth?

Comic comes from xkcd. Phrasings of the classics are mine. Some of my readers have already seen the classics, so I also wrote a bonus problem just for you.

Bonus problem:

Twenty-five knights and knaves sit around a round table. They all know each other well, but I don't know any of them. But I know that there's at least one knight at the table. I ask them all to point to the next knight on their left. Each one of them points to another person at the table. To my disappointment, even after carefully considering their answers, there is not a single person at the table who is certainly a knight, or certainly a knave. However, I now know how many knights are at the table in total!

How many knights are at the table?

As usual, solutions are posted. Hesitating to look is highly encouraged.

Solution to "Find the fake coin"

See the original puzzle

Reader DeralterChemiker was able to solve the first problem:

Take any three coins and weigh them against any other three coins. If they weigh the same, the heavy coin is one of the other two; weigh those two coins against each other, and the heavier coin will be identified.

If one set of three coins is heavier than the other, take two coins from the heavier set and weigh them against each other. If one of those is heavier than the other, the heavy coin has been identified. If those two coins weigh the same, the heavy coin is the third coin from that set of three.

And Secret Squïrrel solved the second problem:

Ok, the bonus problem requires a bit more work and a more elaborate decision tree but I'll try to be as succinct as I can. I'll label the coins with letters (A to L) so they don't get confused with my numbering of the steps.

Step 1. Weigh any four coins against any other four, say ABCD - EFGH. The three possible results are: (a) balance, (b) ABCD is heavier, (c) EFGH is heavier.

(a) If they balance, then the fake coin must be one of the others (IJKL). Go to Step 2.1.

OR

(b) If ABCD is heavier, then either one of ABCD is fake and it's heavy OR one of EFGH is fake and it's light. Go to Step 2.2.

OR

(c) If EFGH is heavier, then either one of ABCD is fake and it's light OR one of EFGH is fake and it's heavy. Go to Step 2.3.

Step 2.1. (ABCD balanced EFGH).
Now weigh three known genuine coins (say ABC) against IJK. The three possible results are (a) balance, (b) ABC is heavier, (c) IJK is heavier.

(a) If they balance then L must be the fake. For your 3rd weighing, weigh it against any other coin to see whether it's heavy or light. DONE.

OR

(b) If ABC is heavier then one of IJK is the fake and it's light. For your 3rd weighing, weigh two of them against each other (say I - J). If one of them is lighter then that is the fake, otherwise it is the other one (K) and it's lighter. DONE.

OR

(c) Very similar to (a), if IJK is heavier then one of IJK is the fake and it's heavy. For your 3rd weighing, weigh two of them against each other (say I - J). If one of them is heavier then that is the fake, otherwise it is the other one (K) and it's heavier. DONE.

Step 2.2. (ABCD heavier than EFGH).
Weigh two coins from each group against one from each group plus two known genuine coins; eg IJKL are known to be not fake so weigh ABEF against CGIJ. The three possible results are (a) balance, (b) ABEF is heavier, (c) CGIJ is heavier.

(a) If they balance then the fake is one of the others, either D (and it's heavy) or H (light). For your 3rd weighing, weigh DH against IJ. If DH is heavier then D is the fake, if lighter then H is the fake. DONE.

OR

(b) If ABEF is heavier then either A or B are fake and heavy or G is fake and light. For your 3rd weighing, weigh A against B to see if one of them is the fake. If they balance then G is fake. DONE.

OR

(c) If CGIJ is heavier then either E or F are fake and light or C is fake and heavy. For your 3rd weighing, weigh E against F to see if one of them is the fake. If they balance then C is fake. DONE.

Step 2.3. (EFGH heavier than ABCD).
Perform the same weighing as for step 2.2 - weigh ABEF against CGIJ (IJ known to be genuine). The same three possible results are (a) balance, (b) ABEF is heavier, (c) CGIJ is heavier (however, the implications of these results are different from 2.2).

(a) If they balance then the fake is one of the others, either D (and it's light) or H (heavy). For your 3rd weighing, weigh DH against IJ. If DH is heavier then H is the fake, if lighter then D is the fake. DONE.

OR

(b) If ABEF is heavier then either E or F are fake and heavy or C is fake and light. For your 3rd weighing, weigh E against F to see if one of them is the fake. If they balance then C is fake. DONE.

OR

(c) If CGIJ is heavier then either A or B are fake and light or G is fake and heavy. For your 3rd weighing, weigh A against B to see if one of them is the fake. If they balance then G is fake. DONE.

If I may offer a more general tip relating to this sort of weighing problem...

It is useful to think of the problem in terms of information and possibilities. Think about how many possibilities you need to distinguish. In the first problem, there are 8 possibilities, because the fake coin can be any one of 8. In the second problem, there are 24 possibilities, since there are 12 coins which could be fake, and the fake coin could either be lighter or heavier. Every time you use the scale, there are three possible results: tilt left, tilt right, or balance. By observing the result, you have received a piece of information, basically a 0, 1, or 2.

With two weighings, you can distinguish between up to 9 possibilities. With three, you can distinguish between up to 27 possibilities.

What would have happened if, in the second problem, you tried weighing three against three instead of four against four? If the scale tilted left or right, then 6 possibilities would remain. If the scale balanced, then 12 possibilities would remain. Since you can only use the scale two more times, it is impossible to distinguish between all 12 of these possibilities. So you know you were on the wrong track.

Trial and error should get you the rest of the way.