...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

Tuesday, December 10, 2013

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….

No comments:

Post a Comment