# 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?

• Also found the prisoners with black/white hats problem pretty accessible. Keeping it to only two colors of course. Added that to the list. – Patch Aug 28 '15 at 8:08
• If you want your student to learn how to write proofs, don't give them puzzles. – Asaf Karagila Aug 28 '15 at 8:16
• I will of course help my students learn the proper technique for proof writing. I don't see how having them get into the right mind set with some fun puzzles can hurt? Mind you, this is the first day of class, the students are all fresh out of high school, and almost none of them have ever had a theoretical math course before. I think helping them flex their brains and practice logical thinking is not only useful but necessary. – Patch Aug 28 '15 at 8:19

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

• This does seem like a good one. Thank you! – Patch Aug 28 '15 at 3:37
• +1 for the question but I have to say after reading the solution it would definitely take me more than ten minutes to figure out – Elliot G Aug 28 '15 at 3:51
• Yes, I think the full "100 blue-eyed islanders" problem would be a bit much. I was thinking of maybe changing it to 2 or 3 islanders (1 is trivial, but is a step in the correct direction for the general solution). – Patch Aug 28 '15 at 3:54
• @Patch yes, I also think it's better to do so. IMO, three would be the suitable choice (maybe with a hint: "what happens if there were only $2$?"). – user230734 Aug 28 '15 at 3:58
• I ended up using the hats/prisoner problem, and the blue/brown eyes problems. We discussed the coins problems together as a class, and then I had them break up into two groups to work on the other two puzzles. – Patch Aug 28 '15 at 22:41

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?

• This one is less "mathy" than the sequences problem below, but I'm still a little hesitant. I do like it though, and I've actually never heard this one before. Thanks for sharing! – Patch Aug 28 '15 at 8:07
• It comes down to a number having an odd number of divisors (and thus being a square), so might be an intro to a divisibility lecture or something – Elliot G Aug 28 '15 at 16:57
• Link above no longer works but same site has it at: mathforum.org/library/drmath/view/56747.html – Partly Cloudy May 27 at 18:45
• @PartlyCloudy thanks; updated. – Elliot G May 27 at 20:16

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.

• I think combinatorics is definitely a good way to go, but I'm unsure of this particular example. Only because I was hoping to steer clear of any "real math" for this first proto-lesson. – Patch Aug 28 '15 at 3:45

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!)