My favorite kind of puzzles are those which sound like they’re going to be an absolute nightmare, but turn out to have a particularly beautiful solution. They’re even better if you don’t really need to know any math to solve them. Here’s such an example, which absolutely delighted me when I first solved it.

I presented it to two of my friends on a long train journey — one of them is a mathematician (in fact he’s a research fellow at Queens’ College, Cambridge) and the other works for a pharmaceuticals company. The non-mathematician got it first. It really is a problem that anyone can have a crack at.

First, I’ll describe a warm-up puzzle. It’s kind of a barometer for the real puzzle.

The challenge: produce a deck of cards, each with a whole number painted on it, with which you can make any number between 1 and 1 million, by picking out some of your cards and adding together the values. You should do this with the least number of cards possible.

Got that? You may want to stop reading and think about it for a second, because the solution is coming up in the next paragraph. I’ve found that computer scientists and programmers tend to get this one faster than most people — often with less than a second’s thought.

The answer is that you should label your cards with the powers of two, so that your deck starts 1, 2, 4, 8 … If you didn’t come up with this solution, the way to think about it is to figure out what cards you’d need to make each of the numbers from 1 up to 1 million. You need to be able to make 1, so you’d better have a card labeled ‘1’. Similarly you need a card labeled ‘2’. But with those two cards you can already make 3, so the next card that needs to be added to your deck is labeled ‘4’. After a while you should spot the pattern, and come up with an argument for why this will work for every number up to a million.

Now here’s the real puzzle, which is a bit more tricky, but fun to think about. I’m not going to give the answer now — I’ll post it in a couple of days.

Produce a deck of cards with which you can make any number between 1 and a million by picking cards and adding together their values, *even if you have lost one of the cards in the deck*.

The requirement that your deck is insensitive to the loss of a card makes the problem tricker to think about, but a similar approach to that described for the easier problem can work. For example, you know that you need to include two cards labeled ‘1’, so that even if you lose one of them you can still pick cards that add up to give 1.

For those inclined to a challenge, there are three levels of answer:

- Describe the deck of cards that solves the puzzle (easy, requires almost no math.)
- Prove that you can make any number between 1 and a million, even if you lose a card (not too hard, requires a little bit of math.)
- Prove that this is the minimal deck of cards that solves the puzzle (difficult, but still needs no math beyond high school.)

I learned this from my office mate, Toby Wood, but I’m not certain where he got it from. If you know, please leave a comment!

## 2 comments

Comments feed for this article

January 27, 2010 at 9:30 am

Deborah ChenHmmm, the fibonacci sequence? So around 30?

July 21, 2010 at 10:56 pm

Chris TaylorExactly that. Nice work! The really hard part is to prove that the Fibonacci sequence works, & then to prove that it’s the optimal solution…