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.

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.

It’s been a while since I posted a puzzle and happened upon a nice one today.

You find yourself babysitting a friend’s marble collection while he’s away at a conference of collectors.  The housekeeper, being an honest type, admits to having disturbed one of the displays.  She assures you that she returned all the marbles and shows you ten marbles laid out thus:

* * * * *

* * * * *

That looks fine, but the note to the side of it says five lines of four marbles each.  Since this is two lines of five marbles, must there be marbles missing or can they be laid out in a manner consistent with the note?

You and other party-goers are lead to different places in a wood blind-folded.  You’re instructed to remove your blindfold at the sound of a horn and read a letter you’ve been provided.  When the bell sounds, you remove the blindfold and the letter reads thus:

You’ll notice around you that there are lengths of rope tied between hundreds of trees around you.  You may notice that any tree with any rope tied to it has exactly two ends tied to it, each stretching to a different tree.  In fact, these hundreds of treees form a giant concave polygon.  Some of you are inside that polyon and others are outside.  To win the game, you must be the first to reach the clubhouse at the top of the hill (which is outside of the polygon!) and report correctly whether you were initially inside the polygon or outside of it.  You can pass under the ropes, but please don’t change them in any way.  Good luck!

What strategy might you employ to determine your status and require as little time as possible to get back to the clubhouse?

A woodworker has a disc of wood, perfectly round, an inch thick and ten inches in diameter.  He wants to make it a wheel and so prepares to drill a one inch hole in the exact center.  Sadly, an ill-timed catastrophic sneeze causes him to drill the hole two inches off-center.  Undaunted, he pulls out his mathematically perfect laser saw (which can make perfect, zero-width cuts in wood) and his mathematically perfect glue (which can glue surfaces together with zero distance between them).  He cuts a piece of the wheel away, glues it back in a different position, and he has exactly the wheel he wanted to begin with.  How does he accomplish this?

Our band of intrepid pirates, having resolved previous squabbles over distributing booty amongst themselves and other issues have come across a treasure map fragment.  The picture has been destroyed, but the following text can be read:

Stand upon the gravesite and you’ll see two great palms towering above all others on the island.  Count paces to the tallest of them and turn 90 degrees clockwise and count the same number of paces and mark the spot with a flag.  Return to the gravesite and count paces to the second-tallest of the trees, turn 90 degrees counter-clockwise and count off that number of paces, marking the spot with a second flag.  You’ll find the treasure at the mid-point between the two flags.

Fortunately, our pirates knew which island the map referred to.  Sadly, upon arriving at the island, the pirates discovered that all evidence of a gravesite had faded.  The captain was preparing to order his men to dig up the entire island to find the fabled treasure when one of the more geometrically inclined pirates walked over to a particular spot and began to dig.  The treasure was quickly unearthed on that very spot.

How did the pirate know where to dig?

I’m overdue to post a puzzle, but I’m momentarily tapped out. Here’s a curiosity in the meantime: You can provide a very good estimate of a conversion from miles to kilometers by choosing sequential Fibonacci numbers.  The conversion rate is 1.609344 kilometers to a mile. So this gives us:

This leaves you in pretty good shape if you need to get from Cincinnati, OH to Destin, FL at 610 Miles, but what if you need to convert some distance that doesn’t happen to be a Fibonacci number?  Just build it up from parts!

100 miles is 89+8+3.  So in kilometers, that’s 144 + 13 + 5 or 162 kilometers.  (160.9344 by conversion…)

OK.  Here’s a puzzle, sort of.  I found this interesting set of numbers recently:

{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 53, 371, 5141, 99481 }

The series doesn’t continue.  That’s all of them.  What’s special about those numbers?

In Living With Crazy Buttocks, Stephen Morris told us of a rather interesting party. The story continues…

After winning their trip to Paris, the guests became elated and celebrated with the consumption of some adult beverages. Ever responsible, the host confiscated the keys to all cars to ensure that no one drove home drunk. Later on, when things started to calm down, party-goers started to request the return of their keys claiming to be sober enough for the drive home.

Having once been out-done by the guests, our host took another whack. He distributed all of the keys, but did so randomly. He then presented a challenge he felt sure they’d only be able to satisfy if they were indeed sober enough to drive. They were allowed to exchange keys, but only in rounds. During each round, each party-goer could either do nothing or pair up with another party-goer and exchange the sets of keys each was holding. (Each party-goer could be part of at most one pairing per round.) No one would be allowed to drive home unless everyone recovered their own keys.

The host wished to allow only a fixed number of rounds. To be fair, he wanted to be sure that it would indeed be possible to make the change. However, he also wanted to make it as difficult as possible for the party-goers. What is the minimum number of rounds must allow them to ensure that an exchange would be possible?

For clarity, all key recipients can discuss, share information such as who has the keys of whom, and agree upon a strategy. Also, careful readers will realize that there were 20 guests at the party originally. Sadly, it was a rather disorderly party and some guests did leave early, but many more appeared. Everyone present at the key ceremony had a key confiscated, and everyone with a key confiscated received a key for this challenge, but neither you nor the host knows just how many there are.

{ Hi, Steve here. Jeff asked me to post a solution and I’m more than happy to oblige. It’s a fun puzzle with some nice maths to explore. I learnt a lot about graph theory and a new theorem (new to me), Turan’s theorem. More on that later. }

In Yoak: Batteries, and the Problem-of-the Week Jeff posed a great problem from Stan Wagon’s Problem of the Week.

You have eight batteries, four good and four dead. You need two good batteries to work the device; if either battery is dead then the device shows no sign of life. How many tests using two batteries do you need to make the device work?

Read the rest of this entry »

Recently I discovered Stan Wagon’s Problem of the Week.  This is a delightful mailing list / site and some of the problems are in the vein of puzzles I post here.  Recent problem 1125 captured the attention of several Math Factor authors so I thought I’d post the puzzle here as an excuse to introduce you all to that list.

You have eight batteries and know that four are good and four are dead, but don’t know which are which.  Your only method of testing them is to insert two into a device that will work if you’ve put in two good batteries and not otherwise.  How many such “tests” are required in order to be sure that you’ve located two good batteries?

As of this posting, the answer to this question is not yet on the POTW website, but if you come to this later, the spoiler may be there, so be careful to avoid spoilers if you want to work this through.