Simple but serious problems for the edification of non-mathematicians When people graduate with honors from prestigious universities thinking everything in math is already known and the field consists of memorizing algorithms, then the educational system has failed in one of its major endeavors.
If members of the next freshman class will take just one one-semester math course before becoming the aforementioned graduates, here's what I think I might do (and this posting is indeed a question, as you will see).  I would not have a fixed syllabus of topics that the course must cover by the end of the semester.  I would assign very simple but serious problems that I would not tell the students how to do.  A few simple examples:


*

*$3 \times 5 = 5 + 5 + 5$ and $5 \times 3 = 3 + 3 + 3 + 3 + 3$.  Why must this operation thus defined be commutative?

*A water lily has a single leaf floating on the surface of a pond.  The leaf doubles in size every day.  After 16 days it covers the whole pond.  How long will it take two such leaves to cover the whole pond.  (Here lots of students say "8 days".  I might warn them against that.  This is the very hardest problem assigned in an algebra course that I taught, according to most of the students.)

*Here is a square circumscribing a circle. [Illustration here.]  Here is how you use this to see that $\pi<4$.  [Explanation here.]  Now figure out how to prove that $\pi > 3$ by a similarly simple argument.

*Multiples of 12 are 12, 24, 36, 48, 60, 72, 84, ......  Multiples of 18 are 18, 36, 54, 72, 90, .....  The smallest one that they have in common is 36.  Multiples of 63 are 63, 126, 189, 252, 315, 378,.....  Multiples of 77 are 77, 154, 231, 308, 385,....  Could this sequence go on forever without any number appearing in both lists?  (Usual answer: Yes.  It will.  Because 63 and 77 have nothing in common.)  Is it the case that no matter which pair of numbers you start with, eventually some number will appear in both lists?


I said  simple but serious, the latter meaning they will actually learn something worth learning about mathematics or about how to think about mathematics.  Not all need be as elementary as these.  With some of the less elementary problems I might sketch a solution or write out a solution in detail and then ask questions about the solution.
I would not fix in advance the date at which problems were to be turned in, but would set deadlines after discussion reveals that serious difficulties are overcome.  I might also do some "teasing" concerning various math topics not covered.
HERE'S THE QUESTION: Which published books of problems can participants in this forum recommend for this purpose?  Why those ones?
 A: One good option is "The Magic of Numbers" by Gross and Harris (not to be confused with a book of the same title by ET Bell), which was written for the eponymous class Gross used to teach at Harvard.  The problems include some stuff on, say, Catalan numbers, and some reasonably serious modular arithmetic (e.g. RSA encryption) with a minimum of baggage, which should recommend the book to non-mathematicians.
The Art of Problem Solving series (here) is also quite good.  I learned a lot from some of those books when I was in high school--they have lots of exercises, ranging from very easy to problems I, at least, found quite difficult.  And there is a lot of discussion of technique, which I think non-mathematicians often find  lacking in other textbooks.
And Martin Gardner's entire oeuvre is great, and I think that recommendation probably doesn't require any explanation.
A: Your pedagogical approach sounds suspiciously like the one in many Math Circles. The National Association of Math Circles has problem lists on their website. Here's another problem set which looks interesting.  
If your intention is to leave these students with the sense that there is fabulous ongoing research in mathematics, I'd recommend the Five Golden Rules: Great 20-Century Mathematics and Why They Matter.  It's quite accessible because it focuses on the general ideas.
A: Published books of problems generally mean to nudge serious, dedicated and perhaps talented mathematics students towards a research-oriented frame of mind.  If you really mean a bound problem collection for general education, I expect you will have to write such a book yourself.  But I would probably recommend against publishing such a book - on the grounds: don't teach until you see the whites of their eyes.  A mathematics problem that will work with one cohort might variously and unpredictably either defeat or insult the intelligence of another.  And, as the the response to your other question might indicate, teachers of mathematics will have very diverse views of what constitute a value partial knowledge of mathematics.  
That said, if I had an audience of highly intelligent but not especially mathematically oriented students, I might focus their "last look" at mathematics on Lawvere and Schanuel's Conceptual Mathematics (which has many good problems).  The authors show themselves as both wise and smart.  While the book could save the soul of a stray mathematician, it does not harbor any hidden agenda that means ignoring the needs of the broader audience.  And while it might accidentally remediate some high school induces confusions, even the best trained students will find most of what the authors say both very new and very fundamental.  
Serge Lang's Math Talks for Undergraduate also attracts me, but where Lawvere and Schanuel help a student think about the larger world in a more mathematical way, Lang wants non-mathematicians to understand more about what mathematicians do.
Research mathematician/teachers generally hold as a sacred shibboleth the dictum that "mathematics in not a spectator sport."  In the case of a class of general education students seeing mathematics in the classroom for the last time, and and the risk of blasphemy, I question this, I question whether having these students primarily trying to solve problems for themselves necessarily constitutes the best use of their time.  I believe that the mathematics community has neglected developing of literature of what one might call proof-oriented spectator mathematics.  But still I might recommend a book: I taught a course recently out of Ross Honsberger's Episodes in 19th and 20th Century Euclidean Geometry where I focused on close readings of complicated but elementary proofs of concrete and yet often spectacularly counter-intuitive facts, all material most mathematics majors will never see on the grounds that it isn't sufficiently modern.  But as a toy model of what mathematicians do it worked very well for my students. 
A: "Heard on the Street" by Timothy Falcon Crack is a collection of brainteasers that were supposedly put to interview candidates for Wall Street jobs. The book has many more questions like the ones you asked - most of them can be solved without any heavy mathematical machinery, but they all require a little ingenuity.
Sadly, the book has become famous enough that recent graduates hoping to get banking jobs often memorise all the problems, rendering the whole process useless.
A: How about The Theory of Remainders by Andrea Rothbart. 
I remember back in the day I was struggling with the concept of modular arithmetic and randomly came across the book above. It's really well written in an unorthodox way as a dialogue between two people talking about modular arithmetic. The book introduces basic concepts of abstract algebra and has plenty of "simple, but serious" exercises. If I recall correctly, it did a really good job of motivating the concept of fields. Above anything, it was written with a high school audience in mind, so incoming freshmen should not be deterred by the level of difficulty. I also found the style of the book engaging. I dare say I was bitten by the number theory bug shortly after reading it. 
