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.
You have been contributing nicely to this forum. 清儿 and I would like to invite you, seriously, to think about joining us as co-BanZhu now, or, sooner or later. In the future, we will have at least 3 co-BanZhus, and possibly 4, at any time, so each guy's duty will not be too heavy. Please think about this seriously. Thanks a lot, as always. |
Thanks a lot for your kind invitation. But I have to say that I cannot accept it, at least not now. As you can see I am not very patient. To be a qualified moderator one needs to be much nicer than I ever could be. Also as of now I have another job. Although I did not take it very seriously, it would still be a kind of conflicts of interest if I also work here. I am also wondering why you asked me, since there is some one who is smarter and nicer. |
This seems easy by induction (sorry constant), some trap I didn't see? L = p^2(1+2L)+2p(1-p)(1+L)+(1-p)^2, L = 1/(1-2p) |
This is not exactly induction, but recursion. (And I love it .) I guess the trap is the expected number cannot be negative. |
I guess that means, for p>=1/2, the expected number of nodes is infinity. |
因为 Hu 斑竹知道我从来不想当斑竹，WXC是这样，华闻的脑坛和基督人生论坛也都是这样，这也是我不如你们的地方，我的奉献精神远不如你们，所以我对你们都很佩服，也心存感谢，有时也会良心发现，来加一两把柴。另外我也知道我的能力很差, 这是真话，请你们原谅！ |
You are all excellent candidates, much better than me. 野菜花 is not lacking of our invitation also. Ah, ah, I wish some day you guys all can agree to join us. --- I'm looking forward to that day's coming. Okay, constant, just bear in mind our invitation is valid indefinitely. Whenever you feel like accepting it, please just indicate so. |
重要意义是在于心理上的： 对原版主来说，有多一些“同伙”站在一起，心里踏实一些； 对众网友来说，有多一些领班，也比少一些领班更能鼓舞士气一些。 这个心理上的意义非常巨大：说“四两拔千斤”都不为过。 至于在“责任”和“奉献”上，实在没那么严重。更谈不上“能力”。你们看： 我这个版主的出题答题，远没如菜花，constant，Jenny等诸位多； 我做版主，再怎么努力，也比不上Jenny和ob的贡献； 即便我当初不做这个版主，在老版主们的领导下本坛也是可以发展的。 但是，我的站出来(继而是清儿的站出来)，“功不可没”哦！这个“功”就是对老版主们和对众网友的心理上的支持。 所以，我认为，只要站出来，这版主的“责任”和“奉献”就完成了50%以上了。 非常、非常、非常希望大家理解做版主的这一重意义；希望有越来越多的网友能自告奋勇加入co-版主的行列，不管你是老的，还是新的。你花“四两”力气，拔一个“千斤”，何不乐而为之呢？ |
我昨天没注意到 constant 的 post 里 "smart", "nice" 还有比较级，虽然我并不认为我是 "smart" "nice"，但别人说说也就算了，但 constant 说 "smarter" "nicer" 绝对不是指我，我在他的题目里出的洋相也够多的了。 |
但是乱弹已经是WXC的坛主了。所以还是你最合适。 When I talk about being smart, I mean over all ability, not just solving some silly math problems. Even on that you are as good as anybody. |
我地上挖个洞钻下去吧!
还有很多错解没贴出来
| 欢迎光临 珍珠湾ART (http://66.160.158.134/) | Powered by Discuz! X3 |