IBM Research | Ponder This | November 2005 challenges
Skip to main content

Ponder This

November 2005

<<October November December>>

Ponder This Challenge:

Puzzle for November 2005.

This month's puzzle concerns random binary trees. Let p be a fixed parameter between 0 and 1. Starting with the complete infinite binary tree retain each edge randomly and independently with probability p. Our random binary tree is the portion connected to the root. So for example the binary tree consisting of the root alone will be selected with probability (1-p)**2 (ie when neither edge out of the root is retained).

Some of these random binary trees will contain an infinite number of vertices. Throw these out. Then we ask what is the expected number of vertices as a function of p of a random binary tree selected in this way. This is a problem for which it is possible to obtain the right answer in a non-rigorous way. We will not attempt to check the derivation of submitted solutions but you should think about what would be required to prove your answer rigorously.

Hints to the puzzle added on November 17th 2005:
A lot of wrong answers so perhaps a hint is in order. It may be helpful to compute the fraction of random binary trees which are infinite and therefore thrown out. And remember you are computing the expected size over the remaining trees after throwing out the infinite trees (or to put it another way the expected size given that the tree is finite).

The first 100 people who answer correctly will be listed. The answer will be posted a week after the 100th is received, or at the end of the month.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

  

Challenge: 11/01/2005 @ 08:30 AM EST
Solution: 12/01/2005 @ 08:30 AM EST
List Updated: 11/30/2005 @ 09:00 PM EST

People who answered correctly:

Eugene Vasilchenko (11.01.2005 @12:38:03 PM EDT)
Dan Dima (11.01.2005 @05:41:44 PM EDT)
Mark Perkins (11.01.2005 @07:27:05 PM EDT)
Dan Bernstein (11.02.2005 @09:25:46 AM EDT)
Christopher Howe (11.02.2005 @11:35:25 AM EDT)
Xiaoyang Guan (11.03.2005 @12:33:27 AM EDT)
Luke Pebody (11.03.2005 @06:24:58 PM EDT)
Chuck (11.04.2005 @06:38:01 PM EDT)
Lukas A Saul (11.04.2005 @10:54:25 PM EDT)
Michael Brand (11.05.2005 @03:41:20 AM EDT)
Itsik Horovitz (11.05.2005 @08:00:43 AM EDT)
Franco Bassi (11.06.2005 @04:20:26 PM EDT)
Patrick J. LoPresti (11.07.2005 @01:15:40 PM EDT)
Roberto Tauraso (11.07.2005 @07:10:47 PM EDT)
Ameet Deshpande (11.09.2005 @11:05:26 AM EDT)
Ken Bateman (11.09.2005 @12:16:54 PM EDT)
Evgeni (11.15.2005 @09:40:37 PM EDT)
Tomáš Jurík (11.16.2005 @11:13:10 AM EDT)
David Friedman (11.16.2005 @02:31:40 PM EDT)
Dharmadeep Muppalla (11.20.2005 @01:30:30 AM EDT)
Wolfgang Kais (11.21.2005 @03:11:18 AM EDT)
David McQuillan (11.23.2005 @06:20:25 AM EDT)
Huicheng Guo (11.29.2005 @10:53:27 PM EDT)
Vishal Mamania (12.01.2005 @02:31:10 AM EDT)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.