Coffee and Coconuts

I’ve been playing with word puzzles lately – I want to add some more games to another website I have: Dr Mike’s Word Games for Kids. I don’t talk much about it, because it’s only got two games on it so far … that’s clearly not enough!

Now, I have a third game in progress – a collection of Word Morph puzzles. Those are puzzles where you transform a word into another, one letter at a time. ¬†For example, MATH could become MATE, then MARE, MORE, WORE and WORD. I’ve put over 100000 word morph puzzles online. Each one was chosen so that:

  • The puzzles can be filtered by how hard the words you need are – so you can pick puzzles suitable for grade 2 kids, or for linguistics professors.
  • If the site says a puzzle with “vocabulary level 5” needs 6 steps to solve, it can’t be solved in fewer steps using harder words.
  • The shortest solution for each puzzle doesn’t involve any rude or possibly offensive words. Hopefully!

It’s not possible to avoid rude words completely. Almost any four letter word can be transformed, changing one letter at a time, into a “four letter word”. That’s because each word with four letters has quite a lot of “neighbors” that are also words – neighbors that differ from it by just one letter.

Imagine a huge piece of paper, with all these words printed on it in a tiny, tiny font size. Now, imagine joining each pair of words with a small line if and only if they differ by exactly one letter. What you’ll have drawn is called a “graph”. (Not the graph of a function, this is a different meaning for the same word.)
Graphs are really useful for modeling situations where you have a bunch of things, each one related to some of the others. A facebook user and his or her friends, for example. Or a web page with link to other pages.

A useful question in many of these situations is this: how far can information travel through the graph? If you like a page on Facebook, could that page potentially reach everyone through you and your contacts? Could a 100% infectious zombie plague potentially reach everyone? Can almost any five-letter word be transformed into almost any other?

The branch of mathematics that tries to answer these question is called “Percolation Theory”. Imagine hot water percolating through coffee grounds. The gaps between the particles of ground coffee are the dots in the graph. Dots are connected if the gaps are joined. Can the hot water make it all the way through your grounds and into the cup?

The main result of Percolation Theory is that you’ll get your coffee if “enough” of the gaps are connected. Literally, there’s some critical “density” of links, that determines whether the chance of percolation is 0 or 1. Make your coffee grounds just loose enough, and the coffee is guaranteed to flow. Pack them just a little too tightly, and there’s zero percent chance of Monday Morning Coffee. Percolation theory says there’s no middle ground – the chance that you can travel all the way through a sufficiently large network is either 0% or 100%, never in between.

For English four and five letter words, the link densities are above that critical threshold density, and it’s possible to transform almost any word of those lengths into another (although I still haven’t figured out how to change BREAD into TOAST). For six letter words, the density of words is too low. Write down two random six-letter words, and if you can transform one into the other, you were really, really lucky.

My Word Morph web page isn’t complete yet – you still can’t hunt down puzzles in all the ways I plan. However, you might like to drop by anyway, and follow the link on the page to a random Word Morph puzzle.

In the meantime, here’s a math puzzle to try:

Three men were stranded on a desert island, with a monkey. They spent the day gathering coconuts. At the end of the day, they were tired, and agreed to share the coconuts in the morning.

The first man woke up about midnight. Not quite trusting his companions, he stole over to the coconuts and shared them into three piles. There was one coconut left over, which he gave to the monkey. He hid his share, and went back to sleep.

The second man woke at about 2am. Not quite trusting his companions, he also stole over to the coconuts that were left, and shared them into three piles. There was one coconut left over, which he gave to the monkey. He hid his share, and went back to sleep.

The third man woke just before dawn. He also did not quite trust his companions, so he stole over to the still smaller pile of coconuts, and shared it into three piles. There was one coconut left over, which he gave to the monkey. He hid his share, and went back to sleep.

In the morning, the three men went to the greatly diminished pile of coconuts. Nobody commented on why some coconuts had vanished, since they were all guilty. They shared it into three equal piles, but there was one coconut left over, which they gave to the monkey.

What’s the smallest number of coconuts that they might have collected, that makes this story possible? And how many did each man get?

Answer (or at least a clue) next week!