Algorithms, Knights, and Knaves II

So, we have moved on from just Big-O to Big-Omega and Big-Theta. There isn't much difference between the three (in terms of proof structure). Proofs regarding one of these are just as easy as proofs regarding others. We have also moved on to talking about steps and timing in an algorithm, which isn't all too bad. However, the definition given for the worst case run-time, in symbolic form, as well as finding the lower and upper bounds for that run-time, is a little bit confusing, but I have to get that confusion sorted out, at least before the test. It usually works out in the end, so I'm not too worried.

The third exercise, like the other two, is decently easy. The third assignment seems deceptively easy. In the past, on assignments, there were usually a few problems that I could not figure out, so I had to go to office hours, CSC help center, or stay behind after lecture. This time, all the problems seem completely do-able. I've done a few of them, and they were pretty easy. I'll just have to see if the rest of the assignment is just as easy.

So, back to knights and knaves:

3. Person A says: "If B is a knave, then I am a knight". Person B says: "We are different." What are A and B?

Understand the problem: We see here A stating an implication, not a bi-implication. That might be important. Also, it would probably help to know how to negate implications.

Plan a solution: In this case, as in all cases, it would be helpful to consider the different possible cases and the logical implications of such cases. In other words, if A is a knight, then certain things must hold true. If we get a contradiction between what must logically be true and what is the case in the question, then we know that that case is false, and we move on to another case.

Carrying out the plan:

For the first case, suppose A is a knight. Then, he would be telling the truth and the implication would be true, but the implication does not tell us what B is. Suppose B is a knave. In this case, A and B are different, so B would be telling the truth, but knaves lie. So, B can't be a knave. Suppose B is a knight. Well, in this case, B would be lying, so B can't be a knight. Hence, A being a knight leads to contradictions, so A must be a knave.

Case 2: A is a knave. Then, A would be lying, so the negation of the implication is "B is a knave and A is a knave." Well, if B is a knave, then B would be lying and everything makes sense. If B is a knight, then that would be going against the negation of the implication, which we know to be true. Hence, both A and B are knaves.

Review: It was helpful to consider each case and figure out the one that makes sense (logically). It's also helpful to have a good understanding of logic, which allows us to solve these puzzles.

4. You ask A: "Are you both knights?" A answers either Yes or No, but you don't know enough to solve the problem. You then ask B: "Are you both Knaves?" B answers Yes or No, and now, you know the answer. What are A and B?

Understanding the problem: the last three problems could have been done mentally, but this one would be difficult to keep track of without a pencil and a piece of paper. A few things to keep in mind for this one: Just knowing A's answer is not enough and knowing B's answer after A's answer is enough. Hence, it's can't be the case where knowing A's answer is enough to solve the problem, nor can it be the case where knowing B's answer in addition to knowing A's answer is not enough to solve the problem. If I run into any of these two cases, then I can disregard them. Additionally, the negation of "A and B are both knights" is not "A and B are both knaves."

Planning: I'll write out the various cases, consider the various knights/knaves combinations that can arise out of those cases, and figure out which ones are logically consistent with the problem as a whole (there should only be one, otherwise you can't really solve this problem), and pick that one. That should be the solution.

Carrying out the plan:

The question posed to A: Are you both knights?

The question posed to B: Are you both knaves?

Case 1: A says yes and B says yes. If A is a knight, then A is telling the truth, so B must necessarily be a knight. But, B would be lying by answering yes, so we have a contradiction, meaning A can't be a knight. If A is a knave, then he would be lying. In this situation, if B is a knight, by answering yes, he would be lying, since they are obviously not both knaves. If B is a knave, then both A and B are knaves, so B would be telling the truth by answering yes. Yet again, we get a contradiction. Hence, considering the possible arrangements of knight and knave, we can conclude that the case "yes, yes" is not logically possible.

Case 2: A says yes and B says no. If A is a knight, then B is also necessarily a knight (as previously explained). And, B would be telling the truth by answering no. So, this works out, but we are not done. If A is a knave, then A and B are obviously not both knights, so A would be lying. If B is a knight, then B would be telling the truth by answering no. So, it also works in this case too. Consider also if B is a knave. Then, both A and B are knaves, so by answering no, B would be lying. Once again, it works out. Hence, we see that the case "yes, no" leads to three different knight and knave arrangements. Hence, A and B's answers are not enough to figure out what they are. So obviously, the solution is not here.

Case 3: A says no and B says no. If A is a knight, then he would be telling the truth, so B would necessarily be a knave. But, by answering no, B would also be telling the truth, since they are not both knaves. Hence, B can't be a knave in this situation and A can't be a knight. If A is a knave, then A would lying. So in reality, both A and B are knights, but we get a contradiction. So, A can't be a knight. Hence, the "no, no" case is also not logically consistent.

Case 4: A says no and B says yes. By process of elimination, this is probably the right case. But, we'll double check to be sure. If A is a knight, then B is necessarily a knave. And, by answering yes, B would be lying, since they are obviously not both knaves. So, it's consistent in this situation. If A is a knave, then in reality, both A and B are knights. And, as previously shown, we get a contradiction. So, in this case, there is only one logically consistent combination: A is a knight and B is a knave. And, since there is only one logically consistent combination, that means A and B's answers are enough, so this is the right combination.

Review: As predicted, it would be difficult to solve this puzzle without writing out the possible combinations on a piece of paper. There might have been a faster way to solve this, but whatever. Essentially, this is just a matter of using truth tables. This shows that for problems that involve more extensive thinking, it's easier to write it out.