Wednesday, August 13, 2008

A Brainteaser

Say there are a bunch of different types of things. Apple, Banana, Car, Door, etc. The different possible combinations of those things can easily be mapped to whole numbers by using binary. For example, maybe 1 means Apple and 1010 (binary) means Door and Banana. If you give me the list of different types of things (with the order of the list implying which binary digit represents each one) and a number, I can tell you exactly which set of things that number represents. "3", given the above list, maps to Banana and Apple, because 3 written in binary is 11.

OK, so that works.

Now what if you introduce the idea that there could be any number of all those things, not just 1 or 0? Like, maybe I have 12 Apples and 44,392,105 Doors. How do you map the non-negative integers to that space, 1 to 1? This is a bit trickier because Base Two works better than Base Arbitrarily-Many.

See if you can figure out a way. It's quite doable.