Week 1 Problems.
- 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?
- 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?
- 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.)
- 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.
- 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?
- 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.)
- 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
which will tell you which room is the right room no matter if the
politician is good or bad.