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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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?