Week 1 Problems.


  1. Suppose you have a good balance scale and 9 coins. You know that one of the coins is a counterfeit weighing less than all the other coins. How can you find the counterfeit coin in only two weighings?
  2. Suppose you have the same 9 coins, 1 counterfeit as in problem 1. Unfortunately(??), you now have three scales. The problem is that two of the scales are good and one is broken and you don't know which is which. The broken scale might work correctly, it might show the light side as heavy, the heavy side as light, or when the sides are the same it might show one or the other sides as light. How many weighings will it take for you to find the counterfeit coin?
  3. Amazingly, we suddenly are visited by Martians and Venusians. Even more surprisingly, they look exactly the same to us. Even the men look exactly the same as the women. However, they have very strange psychologies. The Martian men and the Venusian women always lie and the Martian women and the Venusian men always tell the truth. Can you come up with a single, simple, yes/no question that will tell you what the gender of the Venutian or Martian you ask is? (Of course, you don't know whether the person you ask is Martian or Venusian, man or woman.)
  4. Same setup as in 3. This time you want to know whether the person you ask is Martian or Venusian. Come up with a simple yes/no question that will determine that.
  5. Is it possible to come up with a single yes/no question that will determine both gender and whether the person is Martian or Venutian? How about two yes/no questions?
  6. There are two kinds of politicians. Good politicians always tell the truth. Bad politicians always lie. You come up to two politicians and you ask one of the politicians what kind of politician they are. The one on the left says "We are both bad politicians." Deduce the kind of politician that each is. (Of course, no-one actually believes in politicians who always tell the truth, but suspend your disbelief for the sake of the problems.)
  7. You are walking in the capital building trying to find a particular room. You come to where the room should be but there are two unlabeled rooms right next to each other. There is a politician there who obviously would know which room it is, but you don't know if he is good or bad. Can you come up with a question you can ask that politician which will tell you which room is the right room no matter if the politician is good or bad.