Alright, I'll add a puzzle to the bunch...
You have N computers on a space station. An accident happens, and some of the computers are damaged, but you know the number of good (undamaged) computers is greater than the number of bad (damaged) ones.
Your goal is to find *one* computer that's still good.
Your only method of testing is the following: Use one computer (say, X) to test another (Y). If X is a good computer, it tells you correctly the status of Y. If X is bad, it may or may not give the correct status of Y; assume it will give whatever answer is least useful to your testing strategy.
In worst-case, how many tests must you use to find one computer that's still good? (in terms of N)
You're permitted any combination of tests, though keep in mind the bad machines may not be consistent in the results they give you.