Category Archives: puzzles

Algorithm puzzles

I love algorithms. I'm not good at them, but I think they're a wonderful expression of human creativity. An algorithm is a formal procedure which - in simple terms - works out the answer to a problem. A good algorithm has few frills, is general and is usually beautiful and can be proved to give the right answer.

So here are two algorithms which I think are beautiful and slightly mystical. Each carries the author's name. I'm going to leave you to work out what each does. I have created meaningless variables and names so as to give few hints. I have written them in Java, but you should be able to follow them (int means integer;
The original version of the first algorithm (using iteration) (!= means notEqual):

int foo(int a, int b) {
while (a != b) {
if (a > b) {
a = a - b
} else {
b = b - a
return a

"To Iterate is Human, to Recurse, Divine" wrote James O. Coplien of the legendary Bell Labs. Here is the same algorithm using recursion (a mod b means the integer remainder after dividing a by b):

int foo(int a, int b) {
return (b == 0) ? a : foo(b, a mod b)

Isn't that beautiful? Even if you're not a programmer you can see that it's very clever to create an algorithm with only one line.

If you don't recognize this algorithm you can probably work out what it does by running a few trial variables throuh it. But what about this one...

void foo(int c, int d, int e) {
int a = 0;
int b = c;
int sum = 3 - 2 * c;
while(a <= b) {
outputProcedure(a, b, d, e);
if (sum <= 0) {
sum = sum + 4 * a + 6;
} else {
sum = sum + 4 * (a - b) + 10;
b = b - 1;
a = a + 1;

(* means multiply; <= means lessThanOrEqual).  Here we pass 3 integers (c, d, e) into a routine which runs through a loop and outputs something each time. What does it output? What are c,d,e?

The numbers 2, 3, 4, 6, 10 are fundamental parts of the algorithm - I find this remarkable!

PS  If any of you are still struggling with the mystery molecule, the answer is completely contained within - just save the picture.

Density and mystery

Carsten Niehaus (of the Blue Obelisk) has posed a puzzle - it must be catching. It's about finding the ordering of density of three liquids with only two weightings. I don't know whether there is an answer... I suecpt the question isn't well defined.

But it reminded me of when I used to meaure the density of crystals - such as the mystery molecule (I hope you know what the answer is now - maybe I'll give some hints below)...

So how do you measure the density of a crystal almost smaller than you can see? You can't weigh it and measure the volume... You do it by flotation. Just find two liquids of different densities - say chloroform and hexane. Chloroform is denser than hexane. Assume the crystal has a density somewhere in between. Mix the liquids and drop the crystal in. Does it float? If so, add some more hexane until it neither floats nor sinks. Then find the density of the liquid by measuring some liquid and weighing it. The density of the liquid is the same as the density of the crystal.

Why should we do that? Well the density is an intrinsic property - it is the same throughout the crystal. So even if we chop it into chunks with a few atoms the density is the same. So if you know the size of the unit cell (amd hence the volume) - from X-ray crystallography - you can find the mass of the unit cell. That's a simple integer multiple of the molecular weight - that's how I determined it was "about 250".

I mentioned the problem to my colleague Jonathan Goodman and he knew in 3 seconds..

The answer is actually contained in the post Mystery Molecule - more clues… just inspect it very carefully.

I'm feeling generous - Here's an important part of the mass spec of the molecule. It might give some hints. (The x-axis is hamburgered - but no worse than some of the supplemental data that gets deposited.)


God's golf club

The golf club problem was a throwaway - I didn't expect it to have a long duration. I can't resist the following plea and will give a formal answer (there is a much simpler way of doing it)

  1. Russ Says:
    November 15th, 2006 at 12:02 am eI was hoping someone would pipe up with the answer, because now it’s kind of bugging me. It would seem the standard high school physics doesn’t apply to infinitely massive golf clubs wielded by superbeings. Or if it does, the golf ball flies off at infinite speed and/or blows up in a blinding flash of energy (amounting to it’s mass times the speed of light squared).Put a nerd out of his misery here - what’s the answer?

Assume the club has mass M and velcity V and the ball is mass m and velocity v. Momentum must be conserved and, for an elastic collision, so must energy.


Momentum: MV

Energy 0.5 M V*V


Momentum MV' + mv

Energy 0.5 M*V'*V' + 0.5 m * v * v

We have the equations:

MV = MV' + mv

M*V*V = M*V'*V' + m*v*v

We can reduce the variables by using the ratio of masses (A=M/m) :

A(V - V') = v

A*(V*V - V'*V') = v*v

Two equations, 3 unknowns - you will come out with a ratio of velocities. Bit messy. Then let A tend to infinity. You should get a simple answer. Then see if you can find a simpler approach - look at it with a fresh viewpoint -