Floating Point Numbers and Knights and Knaves III

This week, we seemed to have moved to a slightly unrelated topic regarding floating-point numbers and how numbers are represented in computers. It's sort of interesting and it certainly explains a few questions I've had regarding how arithmetic is done in computers. However, it seems unrelated to everything else that we've covered. All the logic that we learned at the beginning of the semester, that was necessary in order to do proofs in a rigorous manner and to understand mathematical symbols. So, the topic on proofs followed naturally from the topic on logic. Likewise, the topic on Big-Oh also followed naturally from the topic on proofs, since proving that a function is in Big-Oh of another function is just, well, a more specific type of proof. For now at least, the topic on floating point numbers seems unrelated to everything else we've learned this year.

This is not to say that the current topic isn't interesting, because it is. I've certainly never learned something like this in math before. Originally, after the first week, I thought this course would be all about mathematical logic. Obviously, it isn't, but that would have still been great. In any case, I realize now that this course is mostly an introduction to the mathematical and theoretical aspects of computer science. This includes numerical analysis, which seems to be what we are working on right now.

As I've predicted, the assignment was pretty easy. On the first assignment, I wasn't too sure about the necessary and sufficient conditions, and so I had to go to the CSC help center to get that figured out. On the second assignment, I wasn't too sure about the delta-epsilon proofs, so I had to go to office hours and the CSC help center to get those figured this. This time, however, there isn't a single thing I'm confused about. Everything is fair and straightforward and is similar to what we covered in lecture. Hopefully, I'll do well on this assignment.

So anyways, back to knights and knaves:

5. A and B are guarding two doors, one leading to treasure and one leading to a ferocious lion which will surely eat you. You must choose one door. You may as one guard on yes/no question before choosing a door. What question do you ask? Is it easier if you know one is a knight and one is knave (but you don't know which is which)?

Understand the problem: First, the answer to the last question is yes. I don't know how I can possibly solve this question if I didn't know some fact about the two guards. If I know one is a knight and the other is a knave, I can take advantage of that fact and phrase my question is such a way so that a knight and a knave will return the same answer, and such a question would involve me asking a question to one guard about the other guard. Otherwise, if I know nothing about the guards, then I would somehow have to phrase my question so that a knight and knave would return the same answer, independent of the other. And, I'm not really sure how to do that.

Planning a solution: Basically, my plan is to just come up with a list of possible questions and see what the answers would be if the guard is a knight and if the guard is a knave. If the answers are the same, then that would be question I would ask.

Carry out your plan: This took a while to figure out. Eventually, I realized that this would work as a solution: point to a random door and ask the guard, "Would the other guard say this door leads to the treasure?" If the guard is a knight, then the other guard is a knave. And, since knights tell the truth, if that random door does lead to the treasure, then he would say no, since he would know that the other guard, being a knave, would lie. If the door leads to the lion, then he would say yes, since that would be what the knave would say. Likewise, if the guard whom you are asking the question to is a knave, then the other guard is a knight. So, if the door does lead to the treasure, the knave would realize that the knight would say yes, and since knaves lie, then the knave would say no. If the door leads to the lion, then that means that the other guard, being a knight, would say no, leading to the knave saying yes. Basically, in the end, if the guard says yes, go through the other door. If the guard says no, go through that door.

Review: I was fairly difficult to come up with the right question to ask. I tried other possible questions, such as "Is the other guard a knave?" Eventually, I settled on the one above, since it was the first question that I found to work. There might be other ones that work. Notice how my question assumes that the guards know what the other guard is. Maybe that is not the case, in which I case I would have to come up with another answer to this problem. So, after all, my solution might not be that great after all. Oh well...