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

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

## HJ. Strange Suitor

We’ll have some pursuit puzzles over the next couple of weeks; this segment’s puzzle has a simple and elegant solution, but it might take a while to work it out!

In the meanwhile, here’s a little discussion about the glass of water problem.

Each time we add or subtract 50%, we are multiplying the quantity of water by 1/2 or 3/2. If we began with 1 glass’ worth, at each stage, we’ll have a quantity of the form 3m/2n with m,n>0  Of course that can never equal 1, but we can get very close if m/n is very close to log3 2 = 0.63092975357145743710…

Unfortunately, there’s a serious problem: m/n has to hit the mark pretty closely in order for 3m/2n to get really close to 1, and to get within “one molecule”s worth, m and n have to be huge indeed.

How huge? Well, let’s see: an 8 oz. glass of water contains about 1025 molecules; to get within 1/1025 of 1, we need m=31150961018190238869556, n=49373105075258054570781 !!  One immediate problem is that if you make a switch about 100,000 times a second, this takes about  as long as the universe is old!

But there’s a more serious issue.

In a glass of water, there’s a real, specific number of molecules. Each time we add or subtract 50%, we are knocking out a factor of 2 from this number. Once we’re out of factors of 2, we can’t truly play the game any more, because we’d have to be taking fractions of water molecules. (For example, if we begin with, say, 100 molecules, after just two steps we’d be out of 2’s since 100=2*2*some other stuff.

But even though there are a huge number of water molecules in a glass of water, even if we arrange it so that there are as many 2’s as possible in that number, there just can’t be that many: 283 is about as good as we can do (of course, we won’t have precisely 8 ounces any more, but still.)

If we are only allowed 83 or so steps, the best we can do is only m= 53, n = 84 (Let’s just make the glass twice as big to accommodate that), and, as Byon noted, 3^53/2^84 is about 1.0021– not that close, really!

## HH. Corpuscle Candies

In which we continue our contest for SOME interesting fact about the number 2012, describe Newton’s Law of Cooling, and ask another puzzle on the mixing liquids.

We HAVEN’T yet fully answered the coffee and cream question: a follow up post will be coming soon!

## HG. Two Love

In which we confess further delight in arithmetic…

1) Send us your candidates for an interesting fact about the number 2012; the winner will receive a handsome Math Prize! As mentioned on the podcast, already its larger prime factor, 503, has a neat connection to the primes 2,3,5, and 7.

2) So what is it about the tetrahedral numbers, and choosing things? In particular, why is the Nth tetrahedral number (aka the total number of gifts on the Nth day of Christmas) is exactly the same as the number of ways of choosing 3 objects out of (N+2)? Not hard, really, to prove, but can you find a simple or intuitive explanation?

3) Finally, about those M&M’s. Maybe I exaggerated a little bit when I claimed this problem holds all the secrets of the thermodynamics of the universe, but I don’t see how! Many classic equations, such as Newton’s Law of Cooling or the Heat Equation, the laws of thermodynamics, and fancier things as well, can all be illustrated by shuffling red and blue M&M’s around. What I don’t understand is how anything got done before M&M’s were invented!