Fun logic puzzles to teach logic/proof-writing to students

The Blue Eyes Puzzle is a very good candidate in my opinion.

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?

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.