Re-running Raymond

It was Raymond Smullyan's birthday last week, so this is as good a time as any to re-run my favorite, mind-blowing conundrum of his, which I re-post almost every year at one of my two blogs (so if you remember it all-too-well you have permission to skip all that follows). Smullyan set forth the problem in "Annals of the New York Academy of Sciences," 1979, Vol. 321, but I've adapted my version from Martin Gardner's presentation in his Colossal Book of Mathematics. Onward....

You walk into a room that has two enormous bins in it. An evil genie is in charge of one bin which contains an infinite supply of ping pong balls, each of which bears a positive integer label on it, which is its 'rank' (from "1" up to any imaginable number, short of infinity). And, moreover, for EVERY integer there are an INFINITE number of such balls available; i.e. an infinite no. of "#1" balls, an infinite no. of "#726" balls, an infinite no. of "#3,376,422" balls, etc. etc. etc. Now, YOU are in charge of a second bin that contains some FINITE number of these very same-type balls. When you walk into the room it has some set number and variety of balls in it; could be 3 balls total or 500 trillion -- believe it or not, it makes NO difference for the final solution of this puzzle.

Now, a game will be played as follows:
YOU have as a goal to completely empty out your box, given the following rules:

The game proceeds in rounds, in which, first you and then the evil genie, take turns. First, you get to remove ONE ball from the finite box and discard it... BUT once you remove a ball, it is the evil genie's turn, and he gets to replace the ball you discarded with ANY number of balls he wishes OF A LESSER RANK from his infinite bin... i.e., you might discard a "#7" ball, and he could put back in to your bin 37 trillion "#4" balls (or he could put in three "#5" balls if he so chose; he just can't put in anything #7 or above). The sole exception is when you remove a #1 ball, because there are no 'ranks' below one, so there are NO replacements for a #1 ball, and in essence, the genie loses a turn. But in all other instances he can place as many balls as he wishes back into your bin.

Now the question: Is there any strategy you can use to insure you will eventually be able to empty out your box?... or is it rather the case, that the evil genie can, if he so wishes, PREVENT you from EVER emptying out your bin?
...It seems obvious that the latter is the case, as, over time, he replaces almost all of your discarded balls with mind-numbing quantities of fresh balls.

Now that would make for a boring puzzle, wouldn't it... So of course, the answer is, contrarily, as Martin Gardner writes, "Incredible as it seems at first, there is NO WAY to avoid completing the task." [bold added] i.e., mathematically-speaking, over enough time, you will ALWAYS empty out your bin! Completion of the task is "unbounded" (there is no way to predict the number of steps needed to complete it, and indeed it could be a VERRRRY large number), but the box MUST empty out within a finite number of steps!
Raymond Smullyan proved this wild result with advanced math, but happily it only requires logical induction to grasp the general reasoning involved:

Realize that once there are ONLY "#1" balls left in the box you simply discard them one by one (no replacement allowed) until the box is empty -- that's a given, and then the game is over, no matter how long it takes. In the simplest scenario we could start with only "#2" and "#1" balls in the box. Every time you remove a "#2" ball, the genie can ONLY replace it with "#1" balls, thus at some point (it could take a long time, but it must come) ONLY #1 balls will remain, and then essentially the task is over.
S'pose we start with just #1, #2, and #3 balls in the box... Every time a #3 ball is tossed, it can only be replaced with  #1 or #2 balls. Eventually, inevitably, we will be back to the #1 and #2 only scenario (all #3 balls having been removed), and we already know that situation must then terminate.
The same logic applies no matter how high up you go as a starting point (you will always at some point run out of the very 'highest-ranked' balls and then be working on the next lower rank until they run out, and then the next, and then the next...); eventually you will of necessity work your way back to the state of just #1 and #2 balls, which then convert to just #1 balls and game over (even if you remove ALL the #1 and #2 balls first, you will eventually work back down and be using them as replacements). Even if you start with quadrillions of balls in your bin, and they range from say #9 to #774,642,977,528,045,219,368... doesn't matter, eventually you'll end up back to just #1 balls....

The result is both simple and amazing, and reminiscent of some of Cantor's mind-wrenching deductions.

Three For Your Consideration

Recently treated myself to a few older books from Amazon, three of which I just want to pass along:

1)  Have mentioned Steven Strogatz's 2009 "The Calculus of Friendship" multiple times in the past (at Math-Frolic). I read a library copy quite some time ago, and always wanted my own hard copy... delighted to now have it. Recommended to teachers, students of all stripes. And if any of you think it's just a simple, sentimental story, NO, it actually includes real math along the way, as only Dr. Strogatz can tell it (but, yes, buy it for the beautiful story, the math is a bonus!). Really, no math-lover should miss it.

2)  Richard Elwes consistently amazes me with his knack for math explication. The book I ordered is his 2013 "Chaotic Fishponds and Mirror Universes" (subtitled, "The math that governs our world"), and so far, it is way surpassing my expectations (the title doesn't do it justice!). A splendid diversity of engaging topics made timely. Richard is British, and for reasons I don't fathom, his books often don't get very wide US distribution -- absolutely ashame! One of the best popularizers out there! Come on American distributors.
As we get close to the end of the year, Jordan Ellenberg's "How Not To Be Wrong," thus far remains my top popular math pick for 2014... BUT IF Elwes' book were from this year instead of 2013, it would be in the race for that designation! Another great choice for any young math-lovers on your Christmas list.

3)  Finally, one of my old stand-byes: Renaissance-man and logician-supreme, Raymond Smullyan -- I have enough of his puzzle books, but ever since reading his Taoist-inclined, "The Tao Is Silent" (1977) I've wanted to read more of his output on spirituality. The book I got, "A Spiritual Journey" (2009), is essentially three small books in one: the first part focuses in a general way, on the philosophy of religion, the second part is on Ralph Waldo Emerson and Transcendentalism, and the last part is on Richard Bucke's notion of "Cosmic Consciousness" -- it won't suit everyone's taste, spirituality being such a personal matter, but if you liked Martin Gardner's "The Whys of a Philosophical Scrivener," you will likely enjoy this offering from Raymond, which so closely mirrors my own views and Gardner's (though the writing is a bit stodgier, less smooth and concise than Gardner). No math here either, but Smullyan on ANYthing is worth savoring.

There are of course plenty more recent top-notch 2014 popular math books on the shelves to choose from... but always fun to catch up on things one has missed from the past. Smullyan is now in his mid-90's with the quick, lucid mind of someone half-his-age, Strogatz is 55, and Elwes is the kid on-the-block at 36 -- each very different in style and interests, but each leaving us an outstanding body of work for our enjoyment and elucidation. Thanks guys, you've given me Christmas in October!

Master of Logical Legerdemain

Logician, Musician, Magician, Mathematician, Candlestick-maker?....

An Overview of "Four Lives: A Celebration of Raymond Smullyan"  edited by Jason Rosenhouse

If you're a Raymond Smullyan fan, go get Jason Rosenhouse's new volume, "Four Lives: A Celebration of Raymond Smullyan," NOW! And if you're not familiar with Smullyan, but do enjoy logic, puzzles, and math, the same advice goes. I was thrilled to see a tribute to Smullyan come out while he is still among us (his 95th birthday is next month), and to learn more about Dr. Smullyan than I already knew -- EVERYthing I read here raised his pedestal even higher than I already beheld it previously!

Though Rosenhouse is editor (not author) of this volume, his love for Smullyan shines through, as well. Smullyan is an accomplished logician, musician, magician, and mathematician/philosopher (I believe those are the "Four lives" referred to in the title?), who, in his 90s still flirts with all these subjects… oh, and, with the ladies as well, I might add. I consistently find Rosenhouse, by the way, to be one of the best popular math expositors around today (though I don't always agree with some of his more philosophical writings), and this tribute volume is another job well-done.

Part 1 ("Experiencing Raymond") of this offering, brings together an array of folks who knew Smullyan from different perspectives at various times, to pay tribute to him. Each of these essays, some short, some long, are lovely, insightful remembrances. I'm only familiar with 2-3 of the over 20 people who offer thoughts here. They are all good, but my two favorite pieces (and they are also the two longest remembrances) come from Bruce Horowitz, a one-time Smullyan grad student, who writes a wonderful, endearing account of the ongoing student-teacher relationship, and Christopher Maslanka (a puzzle-writer himself) who learned of Smullyan, like many of us did, through the writing of Martin Gardner, and who offers a more wide-ranging tribute to the master logician. I would almost recommend that you start this book by reading Maslanka's account first to give you a good feel and overview (the writers in Part 1 are simply laid out in alphabetical order, so there is no reason not to skip around in any order while reading through them.)
The Introduction to the book, by the way, is Rosenhouse's own story of how he came to know Raymond, and how he ended up as editor for this volume.
Part 2 of the book ("Mathematics and Logic") is probably the driest, toughest section (depending on your background/interest in formal logic), with four contributors (including Douglas Hofstadter) dealing with mathematical logic. There is a rambly, fun "Afterword" to this section written by Smullyan himself, in his typical playful (and punful) style.

Part 3 is a wide-ranging sampler of Smullyan's writing, beginning with a heavy dose of Raymond's bread-and-butter knight/knave (truthteller/liar) puzzles. Also included is one of my very favorite puzzles, the "two envelope" paradox, even though it didn't originate with Smullyan. Toward the end comes a section from Raymond's "The Tao Is Silent" volume, another favorite of mine (on Taoism). And I was happy to learn from this volume that he actually wrote a couple of other spiritual-oriented volumes of which I was unaware. On a separate note, the listed bibliography also includes three "personal/autobiographical" works which I'll have to now look for.

Like Martin Gardner's autobiography, this book will appeal primarily to those who are already enamored of its subject, but hopefully, along the way, it will also pull a few additional folks into the corral of Smullyan fandom.

I'm not sure I envy Dr. Rosenhouse's task here of capturing Raymond Smullyan in 300 pages (akin, I would say, to catching lightning in a bottle!), but he has done an admirable job of it. My sole regret is that there is not more on Smullyan's childhood/youth in it. When someone is as multi-talented, interesting, engaging, and well-loved as Raymond Smullyan, a reader wants to know more about the background that made this individual the person they became. But there's little insight here into Raymond's childhood/family life, formative teen years, or college years. I suppose we'll have to wait for an official biography to come along for that.

It's always difficult for me to think of Martin Gardner without thinking of Dr. Smullyan in tandem, so similar are these two brilliant and humble giants in many regards. Raymond's name, appearance, subject matter, and writing style are all just a tad odder or less smooth than Martin Gardner's, and so he has always seemed slightly off to the edge of Gardner's front-and-center stage appearance and facile way with words [somewhat odd too, given that Gardner was probably the shyer, more reticent/introverted of the two]. For now, Smullyan has a bit of an academic cult-like following, but when he is no longer with us, I suspect his legacy will, like Gardner's and also that of Richard Feynman, broaden out to an even wider audience. And deservedly so! I'm thankful for Dr. Rosenhouse's contribution toward that end.

I'll close out with some of the words from Christopher Maslanka's Part 1 essay:

"…Smullyan's achievement seems to me quite unique. Not only has he made original contributions and advances to mathematical logic, and has expounded elements of the subject in a way that reveals them more clearly, strikingly, and economically; but also he has drawn people at all stages of education to an appreciation of some level of his subject. He manages to involve both the student and the serious academic, the young and the old, the passer-by and the dilettante in mathematical logic. He does this in a rounded way, with a charm and ease which makes it seem like legerdemain."

Indeed, he does… and, I say that, as a knight!

Puzzles, Puzzles!

I usually do puzzles over at the Math-Frolic site, but will switch it around this time....

First, I'll just link to a couple of recent puzzle offerings I liked from Richard Wiseman and Presh Talwalkar to warm you up, in the event you missed them:

1)  http://richardwiseman.wordpress.com/2013/12/02/answer-to-the-friday-puzzle-234/

2)  http://tinyurl.com/o8rufko

By the way, if you're into game theory, I notice that Presh has a new game theory eBook out, "The Joy of Game Theory" -- (Presh is great at finding interesting problems and explaining them well): http://ow.ly/rCtJ6  

3) As we approach the year-end, I realized I haven't re-run one of my all-time favorite Raymond Smullyan brain twisters lately (originally published by Smullyan in the "Annals of the New York Academy of Sciences" in 1979, Vol. 321). Apologies to long-time readers here, who didn't even like this puzzle the first time around! ;-) But what I love about it, is that it is rather involved, and requires some fairly heavy-duty math to prove the very counter-intuitive outcome, yet can be verbally explained so as to be comprehended logically without employing any real mathematics whatsoever. I've re-written it, from Martin Gardner's excellent treatment of it in his "The Colossal Book of Mathematics" (chapter 34)... without further adieu:

Imagine you have access to an infinite supply of ping pong balls, each of which bears a positive integer label on it, which is its 'rank.' And for EVERY integer there are an INFINITE number of such balls available; i.e. an infinite no. of "#1" balls, an infinite no. of "#523" balls, an infinite no. of "#1,356,729" balls, etc. etc. etc. You also have a box that contains some FINITE number of these very same-type balls. You have as a goal to empty out that box, given the following procedure:

You get to remove one ball at a time, but once you remove it, you must replace it with any finite no. of your choice of balls of 'lesser' rank. Thus you can take out a ball labelled (or ranked) #768, and you could replace it with 27 million balls labelled, say #563 or #767 or #5 if you so desired, just as a few examples. The sole exceptions are the #1 balls, because obviously there are no 'ranks' below one, so there are NO replacements for a #1 ball.

Is it possible to empty out the box in a finite no. of steps??? Or posing the question in reverse, as Gardner does: "Can you not prolong the emptying of the box forever?" And then his answer: "Incredible as it seems at first, there is NO WAY to avoid completing the task." [bold added]
Although completion of the task is "unbounded" (there is no way to predict the number of steps needed to complete it, and indeed it could be a VERY large number), the box MUST empty out within a finite number of steps!
This amazing result only requires logical induction to see the general reasoning involved:

Once there are only #1 balls left in the box you simply discard them one by one (no replacement allowed) until the box is empty --- that's a given. In the simplest case we can start with only #2 and #1 balls in the box. Every time you remove a #2 ball, you can ONLY replace it with a #1, thus at some point (it could take a long time, but it must come) ONLY #1 balls will remain, and then essentially the task is over.
S'pose we start with just #1, #2, and #3 balls in the box... Every time a #3 ball is tossed, it can only be replaced with  #1 or #2 balls. Eventually, inevitably, we will be back to the #1 and #2 only scenario (all #3 balls having been removed), and we already know that situation must then terminate.
The same logic applies no matter how high up you go (you will always at some point run out of the very 'highest-ranked' balls and then be working on the next rank until they run out, and then the next, and then the next...); eventually you will of necessity work your way back to the state of just #1 and #2 balls, which then convert to just #1 balls and game over (even if you remove ALL the #1 and #2 balls first, you will eventually work back and be using them as replacements).
Of course no human being could live long enough to actually carry out such a procedure, but the process must nonetheless amazingly conclude after some mathematically finite no. of steps. Incredible! (too bad Cantor isn't around to appreciate this intuition-defying problem).

Mind… blown….