...a companion blog to "Math-Frolic," specifically for interviews, book reviews, weekly-linkfests, and longer posts or commentary than usually found at the Math-Frolic site.

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty – a beauty cold and austere, like that of sculpture, without appeal to any part of our weaker nature, without the gorgeous trappings of painting or music, yet sublimely pure, and capable of a stern perfection such as only the greatest art can show." ---Bertrand Russell (1907) Rob Gluck

"I have come to believe, though very reluctantly, that it [mathematics] consists of tautologies. I fear that, to a mind of sufficient intellectual power, the whole of mathematics would appear trivial, as trivial as the statement that a four-legged animal is an animal." ---Bertrand Russell (1957)

******************************************************************** Rob Gluck

Wednesday, June 1, 2016

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.

No comments:

Post a Comment