Good Mathematical Puzzle Book for Couples

Solution 1:

You might have some luck with the books of Martin Gardner. Many of these books are collections from his monthly column on Mathematical Puzzles, Games, and Diversions for Scientific American.

For instance, there is a widely-loved book including his article on Hexaflexagons. But he has many books.

Good luck!

Solution 2:

No doubt, the book "Fifty Challenging Puzzles" in probability by Mosteller will likely be the most entertaining for probability puzzles. A good list is documented here along with the book from Mosteller. While other types of puzzles (word puzzles, geometric jigsaw etc) are interesting, probability puzzles adds an extra dimension to things because you can see it manifest all around you. Search for the "Inspection Paradox" and you will find lots of interesting applications and fun solving it over skype. HTH