## A Quick Puzzle From OSCON

I recently returned from the O’Reilly Open Source Convention in Portland Oregon. In the final talk of the event, Paul Fenwick, always an amazing presenter, offered a puzzle during his talk that I thought I’d share.

I will offer the puzzle below, but the best way to experience it is to watch Paul’s talk, Mindware Upgrades For Fun And Profit.  No special technical or other background is necessary to enjoy it.

Albert is looking at Betty.  Betty is looking at Charlie.  Albert is a computer programmer.  Charlie is not.  Is there a computer programmer looking at a non-computer programmer?

What was most interesting to me is that the audience of about a thousand really smart people is then invited to raise their hands for “Yes” “No” or “Not Enough Information” and all but fewer than 10 people raised their hand for the same wrong answer!  I failed along with the vast majority, and the other wrong answer outweighed the right answer (which might have had zero votes… I don’t remember.)

If no one posts the right answer here after a while, I’ll come back with an explanation, but I do encourage you to go watch Paul explain.

## Yoak: Denominations of money

A friend posed this to me today:

Devise an alternate set of denominations for coins and bank notes requiring a minimum number of denominations and such that any amount from \$0.01 to \$100 could be paid with four units of currency.

I’ve looked at this from another perspective before after it was discussed on Freakonomics but that has to do with minimizing the average number of coins needed and doesn’t go too much into the math.

What’s remarkable is that my friend nearly instantly came to an upper bound that isn’t huge and after hours five of us have failed to improve upon it.  I’ll avoid stating that bound here for now, but will come back and add it to the comments in a bit if there is no traction.

Another interesting tidbit is that unlike U.S. denominations where a greedy algorithm can verify a minimal number of units that are required (take as many of the largest as you can, then as many of the next largest, etc.) denominations where the denominations aren’t multiples of each other don’t allow this.  Making 15 in 12-5-1 shouldn’t be 12-1-1-1 — it should be 5-5-5.  Even doing verification requires dynamic programming solutions.

## HR. CardColm

Colm Mulcahy, of Spelman College in Atlanta,  joins us to share his ice cream trick from his CardColm mathematical card trick column on the MAA website! You’re invited to explain how this works in the comments below.

Colm also shares a quick puzzle, tweeted on his What Would Martin Gardner Tweet feed @WWMGT. And finally we touch on the Gathering For Gardner and the Celebration of Mind, held all over the world around the time of Martin Gardner’s birthday, October 21.

And at last we get around to answering our quiz from a few weeks ago. There are indeed two solutions for correctly filling in the blanks in:

The number of 1’s in this paragraph is ___; the number of 2’s is ___; the number of 3’s is ____; and the number of 4’s is ___.

[spoiler] namely (3,1,3,1) and (2,3,2,1) [/spoiler]

We can vary this puzzle at will, asking

The number of 1’s in this paragraph is ___; the number of 2’s is ___; …..  and the number of N’s is ___.

For N=2 or 3, there are no solutions (Asking that all the numbers we fill in are between 1 and N); for N=4 there are two. For N=5 there is just one, for N=6 there are none and beyond that there is just one. I think we’ll let the commenters explain that.

But here’s the cool thing.

One way to approach the problem is to try filling in any answer at all, and then counting up what we have, filling that in, and repeating. Let’s illustrate, but first stipulate that we’ll stick with answers that are at least plausible– you can see that the total of all the numbers we fill in the blanks has to be 2N (since there are 2N total numbers in the paragraph).

So here’s how this works. Suppose our puzzle is:

There are ___ 1’s;___ 2’s; ___ 3’s; ___ 4’s; ___ 5’s

Let’s pick a (bad) solution that totals 10, say, (2,4,1,2,1). So we fill in:

There are __2_ 1’s;   __4_ 2’s;    _1__ 3’s;      __2_ 4’s;     _1__ 5’s

That’s pretty wrong! There are actually three 1’s in that paragraph, three 2’s; at least there is just one 3, and two 4’s and one 5. In any case this gives us another purported solution to try: (3,3,1,2,1). Let’s fill that in:

There are __3_ 1’s;   __3_ 2’s;    _1__ 3’s;      __2_ 4’s;     _1__ 5’s

That attempt actually does have three 1’s; but has only two 2’s;  it does have three 3’s but only  one 4 and one 5. So let’s try (3,2,3,1,1):

There are __3_ 1’s;  __2_ 2’s;  _3__ 3’s;  __1_ 4’s;  _1__ 5’s

Lo and behold that works! We do in fact have three 1’s;  two 2’s; three 3’s and yes, one 4 and one 5.

So we can think of it this way: filling in a purported solution and reading off what we actually have gives another purported solution.

In this case (2,4,1,2,1) -> (3,3,1,2,1) -> (3,2,3,1,1) -> (3,2,3,1,1) etc,

We can keep following this process around, and if we ever reach a solution that gives back itself, we have a genuine answer, as we did here.

So here’s an interesting thing to think about.

First, find, for N>=7, a correct solution; and a pair of purported solutions A,B  that cycle back and forth A->B->A->B etc.

Second, find a proof that this is all that can happen (unless I’m mistaken)–  any other purported solution eventually leads into  the correct one or that cycle.

## Pictures from the Gathering

Farewell Tom Rodgers, founder, visionary and force behind the Gathering For Gardner. He has added a lot to the world and his legacy will go on and spread. In that spirit, we all hope you’ll join in the Celebration of Mind, maybe hosting your own event sometime around Martin Gardner’s birthday each year on October 21!

I, like so many others, am deeply indebted to Tom; through his generosity (and a fair amount of his typical forceful prodding!) he enabled me and my collaborator Eugene Sargent to begin working together making large mathematical sculptures. Here are a few pictures of those creations. Until we next meet, Tom, thank you.

## HQ. Newton v Leibnitz

A break from puzzling to discuss the history of the great Newton-Liebnitz dispute over the invention of Calculus, with the playwright Todd Taylor.

## HP. Happy Root 10 Day!

For procrastinators only, we celebrate √10 day! And we pose a new puzzle:

The number of 1’s in this quiz is ____

The number of 2’s in this quiz is ____

The number of 3’s in this quiz is ____

The number of 4’s in this quiz is ____

There are actually two solutions to this one, but more generally, what happens with more lines in the quiz?

Finally, here’s the link to the special issue of Nature with essays on the great Alan Turing.

## HO. Crazies on the Plane

We all know this feeling: someone’s in your seat, and now you’re the nutcase who’s going to take someone else’s seat. After all that what’s the probability the last person on the plane will be able to sit in the correct seat?

The three number trick is just a simple version of this one (but here it is quicker and simpler).

## HN. Barbette

In which we discuss still more 2012 facts—Matt Zinno points out that we are emerging from a spell of years with repeated digits, and in fact this is just about the longest run in the last 1000 years!  (So, folks, enjoy working out other long spells!)

Ben Anderman shares his online Princess-and-Suitor app.

And Kyle and I discuss some bar bets, including the great Barbette, shown here in a photo by Man Ray:

The challenge this week is to work out a strategy for the following game, that works 50% of the time on average:

The Victim believes you will lose twice as often as you win, so in order to make money, you should somehow get The Victim to bet a little bit more than you do, say \$1.50 for each \$1 you put up.

The Victim writes any three numbers on three pieces of paper, turns them over, and mixes them up.

One by one you flip over a card, and then either stop, selecting that one, or discard it and move on. If you select the highest number overall, you win!

We discussed this in more generality a long time ago, but this version has the merit that it’s simple enough to demonstrate quickly, work out precisely why it works and on top of all that, of all the cases has the single highest probability of winning per round.

## HM. Five Cards

Let’s see: First, the “Big News“, a discussion of Carlos May, and another puzzle (a pretty easy one)

And still more 2012 facts! From Primepuzzles.net, we learn that

2012 =  (1+2-3+4)*(5-6+7*8*9)

and there’s still more amazing stuff there that we didn’t try to read on the air.

## HL. Bear Hunt

Happy Palindrome Day! (For some of us)

Many listeners will have heard about the hunter who walks one mile south, one mile east, then one mile north—and is right back where he started. But in fact there are infinitely many places on the Earth where he could be, and in at least a couple of different ways!

And what is the deal with Carlos May?