Fun logic puzzles to teach logic/proof-writing to students Forgive me if this is too soft of a question, but I am looking for some fun, quick, and interesting logic puzzles to give to my students. I'm teaching an honors calculus course, and this will be their first introduction to proof writing.
It was my hope that having them work in groups, on a number of small logic puzzles, will get them thinking in the right way for such a class. I'll be asking them to write up formal proofs to these puzzles, which they can then present to the other groups.
So far I really enjoy the following two puzzles:


*

*You have 12 coins, one is heavier. How can you find the heavier coin in only 3 weighings?

*You encounter a fork in the road, guarded by two twins. One road leads to safety, one leads to certain death. One twin always tells the truth, and the other always lies. What single question can you ask the twins to find the safe road?

*10 prisoners (the number is irrelevant) are on death row, and the warden offers them a pardon if they can guess the color of their hat correctly: (1) all the prisoners are lined up and can only see the people/hats in front of them in line. (2) hats are either black or white. (3) the number of either color hat is not given. How can all but possibly one prisoner be guaranteed to go free?


The level of "cleverness" for these two puzzles is what I'm aiming for; something that will take the students about 10 minutes to figure out and write down a solution for.
Do you have any other suggestions? Any other favorite brain teasers?
 A: The Blue Eyes Puzzle is a very good candidate in my opinion.
A: This might be a cliché by now but I've always liked the locker problem.
Edit: in case of broken link, here is the problem statement, which I copied from MathForum.org.

There are $100$ closed lockers in a hall, and $100$ students. Student $1$ 
  walks down the hall and opens all $100$ lockers. Student $2$ closes all 
  even-numbered lockers. Student $3$ looks at every third locker (a 
  multiple of $3$), and if it is open closes it, or vice-versa (this 
  student changes the condition of the locker). Student $4$ repeats the 
  action of student $3$, but only changes the condition of lockers that 
  are a multiple of $4$. This goes on with every student doing the same 
  routine for his or her number.
After 100 students go through, how many lockers are open? 
  And are the open lockers even or odd?

A: I think that many combinatorics problems will be a good candidate, because counting is very intuitive to everyone (and there are very few theorems to be used). A personal favorite is the following:
Let $a_n$ be a nondecreasing sequence of integers, and $b_k$ be the number of terms of {$a$} that are greater than $k$. Prove that the sum of the elements of the two sequences are the same. 
A: I found this one from one of this year's UK maths olympiads a really nice problem for teaching proof.  The "answer" is not too hard and should be fun for high school students, but most "proofs" they write will have big holes they didn't realise and patches they can find and understand, and even once they have a proof they can be shown techniques to streamline it.

A chessboard is formed from an 8 × 8 grid of alternating black and white squares, as shown. The side of each small square is 1 cm. What is the largest possible radius of a circle that can be drawn on the board in such a way that the circumference is entirely on white squares or corners?

(If anyone has other problems with similar characteristics -- subtleties needing iterative proof repair -- please post.  It's a hard but valuable thing to teach!)
