?

Log in

The Rise and Fall of a PoMo Space Messiah

Σημειον εστιν, ου μερος ουθεν

Geoff

Horsey

God is a comedian playing to an audience too afraid to laugh.
- Voltaire

Σημειον εστιν, ου μερος ουθεν

Previous Entry Share Next Entry
Mu!

So I have been thinking about a couple of logic problems. Both are original as far as I know. I haven't worked out either of them at time of writing.

Beans in Boxes
I have six boxes of equal weight. The boxes contain beans of equal weight. A box weighs the same as a substantial number of beans. One box contains one bean, one contains two, one three and so on up to six beans. I also have a pair of scales. The challenge is to find how many beans are in each box, weighing as few times as possible.

Some observations... there is a good guesstimate of the minimum number of trials required. There is probably more than one solution. Most solutions are likely to be labyrinthine. What we are after is a reasonably elegant solution.

Magic Beans
Magic beans work like this: They are either white or black. Every day there is probability p that a bean will change colour. Every night there is probability q that a bean will split into two beans of the same colour as the 'parent'. You start with one white bean on the morning of the first day.

The question is this: After an unknown length of time you have n beans. What is the expected difference in the numbers of black and white beans as a function of p, q and n? We are talking about the absolute value of the difference here.

An explanation... The question as it is, is pretty straightforward, I'm sure. What I'm really after is an expression for the expected (Shannon) entropy over the maximal entropy (i.e. the entropy of the same number of beans, each having 50% chance of being either colour). The absolute difference is a plausible inverse proxy for this. You can assume that p is less than 50%. Anyone who has been on the wrong end of a teleological argument will understand the use of this.

ETA: The ultimate goal is to find a (reasonably simple) system where the ratio of the entropy and the maximal entropy (as defined above) decreases while the actual entropy increases.

  • Beans in boxes sounds awfully like a sort algorithm.
    • Yes, ultimately it is, in that you're trying to define an order relationship on a set. But I'm not sure it's that helpful a way to think about the problem.

      It was inspired by the 12 ball problem, which has a tendency to crop up in interviews round these parts, were anyone actually interviewing.
Powered by LiveJournal.com